全国青少年信息素养大赛(原全国青少年电子信息智能创新大赛)是“世界机器人大会青少年机器人设计与信息素养大赛”赛事之一,由中国电子学会主办,包含很多赛项,大赛自2013年举办,已连续成功举办八届,已正式入围“2022-2025学年面向中小学生的全国性竞赛活动名单”。
大赛旨在激发广大青少年的科学兴趣和想象力,培养钻研探究、创新创造的科学精神和实践能力,促进青少年科技创新活动的广泛开展,发现和培养一批具有科研潜质和创新精神的青少年科技创新后备人才。
大赛主要竞赛类别包括电子科技、智能机器人、软件编程三类,全国青少年Python编程挑战赛就属于其中的软件编程类。
一.赛事说明
2021-2022年(第8届)Python挑战赛赛程分为初赛、复赛和总决赛三个阶段。初赛是资格赛,复赛是地方选拔赛,总决赛是全国各地选拔的精英汇聚在一起进行PK。2021-2022年全国青少年Python编程挑战全国总决赛于2022年8月27日正式举行。一共是10道编程题,每道题100分,满分1000分,考试时间是120分钟。
10道编程题分别如下:
- 分苹果
- 韩信点兵
- 借书
- 四位数密码
- 邮票面值
- 取球
- 统计连续字符
- n的n次方
- 海盗搜身
- 父与子
超平老师将分10讲对每道题进行详细的解读和剖析,今天要解读的是第2题,韩信点兵。
二.题目描述
题目背景:
韩信点兵又称为中国剩余定理,相传汉高祖刘邦问大将军韩信统御士兵多少,韩信答说,每3人一列余2人、5人一列余4人、7人一列余6人。
输入任意一个数字n(0<=n<=10000)表示刘邦总共的兵力,计算韩信可能统御的士兵数量并依次输出。
输入描述:
输入任意一个数字n(0<=n<=10000)表示刘邦总共的兵力
输出描述:
计算韩信可能统御的士兵数量并依次输出,每行一个,从小到大
样例输入:
500
样例输出:
104
209
314
419
注意:
input()内不添加任何参数
只有完全正确才可提交,若无法点击提交说明答题存在错误,可及时进行检查并修改
三.思路分析
韩信是我国古代杰出的军事家,兵家四圣之一,被后人奉为“兵仙”、“神帅”。同时,他也是西汉的开国功臣,他的一生充满了传奇色彩,他的一生留下了很多脍炙人口的故事,如“背水一战”、“暗渡陈仓” 、“ 十面埋伏”等。
在这其中,“韩信点兵” 这个故事包含一个非常著名的数学问题。
在一次战斗中,韩信率1500名将士与楚王大将李锋交战。苦战一场,楚军不敌,败退回营,于是,韩信整顿兵马也返回大本营。
当行至一山坡,忽有后军来报,说有楚军骑兵追来。只见远方尘土飞扬,杀声震天,汉军本来已十分疲惫,这时队伍大哗,韩信兵马到坡顶,见来敌不足五百骑,便急速点兵迎敌。
他命令士兵3人排成一排整队,结果多出2名,接着韩信又命令士兵5人排成一排整队,结果多出3名,他又命令士兵7人排成一排整队,结果又多出2名。
于是韩信马上说道:“ 我军有1073名士兵,追兵不过区区500人,我们一定能够打败敌人。”
本题描述和上面的故事有所不同,但计算方法是一样的。
解决问题的核心是余数概念,余数是小学二年级的数学知识点。所谓余数是指整数除法中被除数未被除尽的部分, 例如:23除以5,商数为4,余数为3。
在Python编程中,取余数运算使用%,针对本题的描述,假设士兵为n人,有如下三种排队方式:
- 每3人一列余2人,意味着 n % 3 = 2
- 每5人一列余4人,意味着 n % 5 = 4
- 每7人一列余6人,意味着 n % 7 = 6
所以,对于输入的数字n,只需要判断从1-n之间的每一个数字是否同时满足上述3个条件即可,这是典型的枚举算法。
接下来,我们进入具体的编程实现环节。
四.编程实现
根据上面的思路分析,我们使用枚举算法,对1到n之间的每一个数字进行判断即可,对应的代码如下:
# 将输入的数字转成整数
n = int(input())
# 使用枚举算法,判断每个数字是否同时满足3个条件
for i in range(n + 1):
if i % 3 == 2 and i % 5 == 4 and i % 7 == 6:
print(i)
需要说明两点:
1). range函数的特点是虎头蛇尾,如果要包含n的话,需要写成n+1;
2). if语句中,出现了3种运算符,按优先级依次是%、==和and,所以无需增加小括号。
五.总结与思考
本题比较简单,考查的知识点主要包括:
- 输入和输出语句;
- 类型转换;
- 循环结构,主要是for语句和range函数的使用;
- 运算符,包括%、==和and;
- 枚举算法;
作为国赛的第2题,题目还算简单,本题的关键是对余数知识的理解,然后结合枚举算法,就可以很轻松地写出程序。给你留一道思考题,韩信点兵的经典问题,简单描述如下:
韩信带1500名士兵去打仗,战死四五百人,3人一排多出2人,5人一排多出4人,7人一排多出6人,请编程计算机剩下士兵的人数,有兴趣的赶紧来试一下吧。