参加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战友们,用数学方法一样可以解决这个问题。

原文发布于微信公众号 - 申龙斌的程序人生(slbGTD)

原文发表时间:2017-10-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

回溯算法入门及经典案例剖析(初学者必备宝典)

前言 基于有需必写的原则,并且当前这个目录下的文章数量为0(都是因为我懒QAQ),作为开局第一篇文章,为初学者的入门文章,自然要把该说明的东西说明清楚,于是。。...

3284
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

SSE图像算法优化系列一:一段BGR2Y的SIMD代码解析。

     一个同事在github上淘到一个基于SIMD的RGB转Y(彩色转灰度或者转明度)的代码,我抽了点时间看了下,顺便学习了一些SIMD指令,这里把学习过程...

1998
来自专栏CDA数据分析师

深入对比数据科学工具箱:Python和R之争

概述 在真实的数据科学世界里,我们会有两个极端,一个是业务,一个是工程。偏向业务的数据科学被称为数据分析(Data Analysis),也就是A型数据科学。偏向...

1937
来自专栏机器之心

机器学习时代的哈希算法,将如何更高效地索引数据

1735
来自专栏CVer

小米开源自研移动端深度学习框架MACE

Mobile AI Compute Engine (MACE) 是一个专为移动端异构计算平台优化的神经网络计算框架。MACE 支持 TensorFlow 和 C...

1164
来自专栏FreeBuf

干货 | 黑客带你还原韩剧《幽灵》中出现的隐写术

0x00 前言 最近有一部剧人气非常高,据说是将军官和医生的浪漫故事。咦?!!这不是好几年前的老片子了么。 后来有人告诉我,是一部韩剧,里面的欧巴超帅妹子超靓。...

2357
来自专栏华章科技

Python爬虫新手进阶版:怎样读取非结构化网页、图像、视频、语音数据

导读:常见的数据来源和获取方式,你或许已经了解很多。本文将拓展数据来源方式和格式的获取,主要集中在非结构化的网页、图像、视频和语音。

653
来自专栏大数据文摘

三分钟 学会 “信息图表” !

2409
来自专栏北京马哥教育

掌握这7种Python数据图表的区别,你就是大牛数据分析师!

Python 的科学栈相当成熟,各种应用场景都有相关的模块,包括机器学习和数据分析。数据可视化是发现数据和展示结果的重要一环,只不过过去以来,相对于 R 这样的...

46913
来自专栏程序员互动联盟

【专业技术】Android平台下使用OpenGL

存在问题: 安卓平台下如何使用opengl? 解决方案: 1、GLSurfaceView GLSurfaceView是Android应用程序中实现OpenGl画...

3566

扫描关注云+社区