(
课件网) 第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 谢谢聆听， 下节课再见！ ... ...
