[C#解答]第八回数学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;
最后运行结果8824。
出差在外,电脑不在身边,匆忙在网吧里完成了这篇文章,回去再改格式。
数学都如此的好
厉害!大家的数学和编程都这么棒!
我看不懂申老师好棒