参加steemit数学x程式大赛(第八回)

前一段时间参加了Steemit社区的两个活动，比如“接龙”创作大赛，五个人根据几张图片素材编出一篇小说，事先没有任何沟通，人员报名之后，顺序是随机指定的，我第一次参加活动，竟然被安排在第二个小组第一个出场，现在故事已经到达最后一轮，计划在整个活动完成时写一篇总结。

在几个活动中，我还是比较喜欢数学x程式编写比赛，这个比赛是由kenchung负责的，当前正在进行的是第八回比赛，为了大家阅读方便，我把原题从steemit网站上照抄过来。

原题网址：https://steemit.com/contest/@kenchung/question-mathematics-programming-competition-8

问题描述：

Ken有一部只能显示四位数的计算器，它使用七段显示器来显示数字。例如，159显示为

假设我们要使用非透明卡纸来表示从0000到9999所有可能的4位数字。每张卡纸将显示一个4位数字，而这些数字是使用七段显示器所写成的。当某些卡片旋转180°时，可以形成新的数字。例如当卡纸0159旋转180°时，它将变成6510。

这里的1显示在左侧亦可接受

考虑到将卡纸旋转180°的可能性，最少需要多少张卡纸才能表示出0000到9999所有可能的4位数字？

解题过程：

这类问题属于一种排列组合题，在10000种可能性中，要除去那些重复的卡片，需要缜密的思维，我还是用程序来解决吧。

在10000种可能性中，大多数卡纸旋转后没有意义，准备地说，含有3、4、7的卡纸旋转180度之后都是无效的。0、1、2、5、8旋转之后仍是自身。6、9互为旋转之后的结果。

用一个循环生成所有的10000个四位数，再用一个集合来存放已经生成的数字，对于每一个不在集合中的四位数，查看是否能够旋转180度，如果旋转无效，则该数放入集合，卡纸计数增一；如果旋转成功，则把两个数字一起放集合，卡纸计数也增一。

其中需要用到两个函数，r180()函数负责把四位数字旋转180度，rotate()函数只负责把0~9这个数字旋转180度。先用C#快速实现，这里面需要用到一个技巧，把四位数字中的千、百、十、个位分别取出，总体无难度。

// 把0~9数字旋转180度，如果旋转无效，则返回-1

public static int rotate(int d)

{

switch (d)

{

case 0:

case 1:

case 2:

case 5:

case 8:

return d;

case 6:

return 9;

case 9:

return 6;

}

return -1;

}

// 把一个四位数旋转180度，如果无效，返回-1

public static int r180(int dddd)

{

int a = rotate(dddd % 10);

int b = rotate((dddd % 100) / 10);

int c = rotate((dddd % 1000) / 100);

int d = rotate(dddd / 1000);

if (a == -1 || b == -1 || c == -1 || d == -1) return -1;

return a * 1000 + b * 100 + c * 10 + d;

}

因为使用C#，程序中有集合类可用，主程序代码也比较简单。

HashSet<int> set = new HashSet<int>();

int count = 0;

for (int i = 0; i <= 9999; i++)

{

if (set.Contains(i)) continue;

set.Add(i);

++count;

int r = r180(i);

if (r != -1) set.Add(r);

}

return count;

出差在外，电脑不在身边，在网吧里完成了这篇文章，交007作业。不是程序员的007战友们，用数学方法一样可以解决这个问题。