6.10 韩信点兵枚举法的实现（课件）-信息技术六年级上册同步备课（浙教版）

第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 and y 的功能是“当 x 和 y 的值都为真时，表达式的值为真”。因此，条件“x 除 3 余 2 且 x 除 5 余 3 且 x 除 7 余 2 ？”就可表示为：x % 3==2 and x % 5==3 and x % 7==2。 四、算法的程序实现 上述算法用 Python 语言编写的程序如下： 练一练 假如“韩信点兵”的问题描述修改为：秦朝末年，楚汉相争。有一次， 韩信带领 1500 名士兵打仗。战后，死伤一二百人。剩下的士兵中，他命令士兵 3 人一排，结果多出 1 名；接着命令士兵 5 人一排，结果多出 4 名；又命令士兵 7 人一排，结果又多出 3 名。 请你利用枚举算法解决上述问题。 谢谢聆听！ INTERNET OF THINGS $$