资源简介

(共16张PPT)
第10课
“韩信点兵”枚举法的实现
主要内容：
1.枚举法解决问题的一般过程。
2.枚举法的程序实现。
你知道“韩信点兵”的故事吗？韩信是怎么快速算出士兵的总人数的？
“韩信点兵”故事是一个有趣的猜数游戏。其求解的算法有多种，如枚举法。
一
问题描述
相传有一次，韩信带领1500名士兵去打仗。战后，死伤四五百人。剩下的士兵中，他命令士兵3人一排，结果多出2人：接着命令士兵5人一排，结果多出3人：又命令士兵7人一排，结果又多出2人。韩信马上算出人数：我军还有1073名勇士！
二
抽象与建模
韩信点兵的过程可表示为数的除法运算：
二
抽象与建模
“ ”指剩下的士兵总数，用变量X来表示。根据“死伤四五百人”可知，变量X的取值范围为1000-1100，且同时满足“X除以3余数为2、X除以5余数为3、X除以7余数为2”这三个条件。可建立如下模型：
枚举X在1000-1100范围内的每一个值，判断条件“X除以3余数为2、X除以5余数为3、X除以7余数为2”是否同时满足，满足条件的X就是要求的解。即：
二
抽象与建模
当X=1000时，条件“X除以3余数为2、X除以5余数为3、X除以7余数为2”是否同时满足？
当X=1001时，条件“X除以3余数为2、X除以5余数为3、X除以7余数为2”是否同时满足？
……
当X=1100时，条件“X除以3余数为2、X除以5余数为3、X除以7余数为2”是否同时满足？
三
算法设计
根据上述抽象与建模，解决“韩信点兵”问题可采用枚举法。X依次取1000-1100范围内的值，采用循环结构；判断条件“X除以3余数为2、X除以5余数为3、X除以7余数为2”可以采用分支结构。
三
算法设计
四
算法的程序实现
在Python中，余数的运算符为“%”，即表达式x%y的功能是“用x除以y，取余数”，如“5%2”的结果就是1。因此，条件“x除以3余2？”就可表示为x%3==2。
要判断多个条件是否同时满足，需要用“and”逻辑运算符，条件“X除以3余数为2、X除以5余数为3、X除以7余数为2”就可表示为：x%3==2 and x%5==3 and x%7==2。
四
算法的程序实现
上述算法用Python语言编写的程序如下：
x=1000
while x<1101:
if x%3==2 and x%5==3 and x%7==2:
print(“剩余的士兵数为：”,x)
x=x+1
假如“韩信点兵”的问题描述修改为：韩信带领1500名士兵去打仗。战后，死伤一二百人。剩下的士兵中，他命令士兵3人一排，结果多出1人；接着命令士兵5人一排，结果多出4人；又命令士兵7人一排，结果多出3人。问：剩下的士兵一共多少人？
请你利用枚举法解决上述问题。
x=1300
while x<1401:
if x%3==1 and x%5==4 and x%7==3:
print(“剩余的士兵数为：”,x)
x=x+1
谢谢聆听，
下节课再见！

展开更多......

收起↑