[导读]:超平老师的Scratch蓝桥杯真题解读系列在推出之后,受到了广大老师和家长的好评,非常感谢各位的认可和厚爱。作为回馈,超平老师计划推出《Python蓝桥杯真题解析100讲》,这是解读系列的第27讲。
判断完全数,本题是2020年6月20日举办的第11届蓝桥杯青少组Python编程省赛编程部分第2题,题目要求编程输出小于正整数N的完全数并统计其数量。
先来看看题目的要求吧。
一.题目说明
时间限制:4000Ms
内存限制:589824K3
背景信息:
因子:也叫做因数,例如3*5=15,那么3和5是15的因子,同时15*1=15,那么1和15也是15的因子。1,3,5,15这四个因子是15的所有因子。
完数:如果一个数等于不含它本身的其他因子之和,则称该数为“完数”。如6的因子有1,2,3,6且1+2+3=6,因此6是完数。
编程实现:
输入一个正整数N,输出小于N的所有完数及个数(个数前加"*",例 如:*2)
输入描述:
输入一个正整数N
输出描述:
输出小于N的所有完数及个数
样例输入:
100
样例输出:
6
28
*2
评分标准:
-
10分:能正确输出一组数据;
-
20分:能正确输出两组数据;
-
20分:能正确输出三组数据;
-
20分:能正确输出四组数据。
二.思路分析
这是一道数论题,考查的知识点主要包括循环、条件、模运算和枚举算法。
公元前6世纪,古希腊的毕达哥拉斯首先发现,有的自然数,具有一种奇异的性质:把它所有的除数(本身不包括在内)加起来,正好等于这个自然数自己。
例如,6的除数有1、2、3(6不包括在内),且有 6=1 + 2 + 3。又如,28的所有的除数为1、2、4、7、14(28不包括在内),且有28=1+2+4+7+14。
像这样的数,我们就称之为完全数(完数),意思就是完美的数。
根据题目的描述,我们可以将问题拆分成两个小问题:
-
判断单个数字是否为完美数
-
从1到N逐个判断
这里的重点是问题1,要判断某个数字是否为完全数,首先需要找到所有的因数(不包括本身),将其进行累加,再判断总和是否和该数字相等,这是一个典型的枚举算法。
所谓因数,就是指能被该数字整除的数字,所以我们只需要使用模运算就可以了,为了方便,我们可以将判断完数的过程定义成函数。
一旦有了判断完数的函数,问题2就变得非常简单了,再次使用枚举算法,逐个进行判断即可。
思路有了,接下来,我们就进入具体的编程实现环节。
三.编程实现
根据上面的思路分析,我们分两步来编写程序:
-
定义函数判断完数;
-
从1到N逐个判断;
1. 定义函数判断完数
根据前面的思路分析,定义函数如下:
传入一个数字,如果是完美数,则返回True,否则返回False。
2. 从1到N逐个判断
有了上面的函数,就可以使用枚举算法,逐个判断1~N之间的数字,并统计完数的个数,代码如下:
测试程序,输入100,结果如下:
输入1000,结果如下:
输入10000,结果如下:
至此,整个程序就全部完成了,你也可以输入不同的日期来测试效果。
四.总结与思考
本题的分数为70分,代码在15行左右,涉及到的知识点包括:
-
循环语句,主要for…in循环;
-
条件语句;
-
模运算符的应用;服务器托管网
-
函数的定义及使用;
-
枚举算法;
题目难度一般,重点是如何找出给定数字的所有因数(不包括自身),解决思路就是枚举算法,判断依据就是整除,需要用到取模运算符。
实际上,取模运算符%在编程中应用非常的广泛,比如常见的整除问题、周期问题等。
通过上面的测试数据,我们可以发现完全数并不多,在个位数中只有一个6,十位数中也只有一个28,百位数中只有一个496,千位数也只有一个812服务器托管网8。
它们具有一致的特性:尾数都是6或8,而且永远是偶数。
你知道第5个完全数是多少吗?
可能比你想象的要大得多,它居然藏在千万位数的深处,它是33550336。
要寻找完全数并不是一件容易的事情,17世纪,法国数学家、哲学家笛卡尔曾经公开预言:“能找到的完全是不会多的,好比人类一样,要找一个完美人亦非易事。”
历史也证实了他的预言,完美数稀少而优美,所以被人们称为数论宝库中的钻石。
今天,我们有了计算机,要找出完全数就容易多了,这也是编程的魅力所在。
超平老师给你留一道思考题,当输入的N越来越大时,程序执行的时间也会增加,如何优化我们的程序,从而提高算法的效率呢?
你还有什么好的想法和创意吗,也非常欢迎和超平老师分享探讨。
如果你觉得文章对你有帮助,别忘了点赞和转发,予人玫瑰,手有余香
需要源码的,可以移步至“超平的编程课”gzh。
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
序言 github 时有打不开的情况,为此很是烦恼,这里分享一下如何解决这种问题,其实问题的本质是在访问github网页时无法通过github.com的二级域名进行动态域名解析。 解决方案 手动配置静态文件hosts,将该域名和IP的映射关系添加到静态文件中,…