1、算法与程序综合应用1（第十九课时）课前准备课前准备2-12-1n 调出调出“自主学习任务单自主学习任务单”，以配合本节课的学习内容，完成相关的学习任务。以配合本节课的学习内容，完成相关的学习任务。n 打开打开AnacondaAnaconda管理器中管理器中Jupyter NotebookJupyter Notebook，并新建一个并新建一个Python3Python3脚本；脚本；课前准备课前准备2-22-2“物不知数”韩信是汉初著名军事家，传说他统计士兵数目韩信是汉初著名军事家，传说他统计士兵数目有个独特的方法。有个独特的方法。例如，先令士兵排成例如，先令士兵排成5 5列纵队，结果余列纵队，结
2、果余1 1人；接人；接着，命令士兵排成着，命令士兵排成6 6列纵队，结果余列纵队，结果余5 5人；再命令士人；再命令士兵排成兵排成7 7列纵队，结果余列纵队，结果余4 4人；最后命令士兵排成人；最后命令士兵排成1111列纵队，结果余列纵队，结果余1010人。这样他便知道士兵的总人数人。这样他便知道士兵的总人数了。这种计数的方法被后人称为了。这种计数的方法被后人称为“韩信点兵韩信点兵”。试编写程序计算士兵的数目。试编写程序计算士兵的数目。提出问题提出问题“物不知数”提出问题提出问题求不出来。求不出来。修改题目？修改题目？士兵的总数士兵的总数是多少？是多少？提提出出问问题题解解决决问问题题计算机解
3、决问题的一般过计算机解决问题的一般过程程计算机解决问题的一般过计算机解决问题的一般过程程提提出出问问题题分分析析问问题题设设计计方方案案编编程程调调试试解解决决问问题题计算机解决问题的一般过计算机解决问题的一般过程程提提出出问问题题分分析析问问题题设设计计算算法法编编程程调调试试解解决决问问题题物不知数。物不知数。提出问题提出问题物不知数。物不知数。提出问题 假设士兵总人数为假设士兵总人数为X X 分析问题分析问题 分析问题 设计算法设计算法计算机的特点之一：计算能力强、运算速度快计算机的特点之一：计算能力强、运算速度快算法一：枚举法算法一：枚举法 提出问题 设计算法设计算法算法一：枚举法算法
4、一：枚举法X 5 5 =a 1 1X 6 6 =b 5 5X 7 7 =c 4 4X 11 11=d 1010 设计算法设计算法算法一：枚举法算法一：枚举法输出输出X XX X：相应范围内：相应范围内依次取值依次取值是是否否同时满足：同时满足：X%5=1，X%6=5，X%7=4，X%11=10 设计算法 分析问题 编程调试编程调试 提出问题for X in range(4000,5000):语句语句1 1：循环结构：循环结构士兵人数的大致范围？士兵人数的大致范围？编程调试编程调试四千多人四千多人X%5=1语句语句2-12-1：表达式：表达式 编程调试编程调试X%5=1 and X%6=5 an
5、d X%7=4 and X%11=10语句语句2-22-2：条件限定：条件限定print(X)if:编程调试编程调试for X in range(4000,5000):X%5=1 and X%6=5 and X%7=4 and X%11=10print(X)if:编程调试编程调试运行程序运行程序 编程调试编程调试4421 编程调试 分析问题 解决问题解决问题 设计算法设计算法 提出问题程序的改进n 数据输入可否更灵活？数据输入可否更灵活？n 程序界面可否更友好？程序界面可否更友好？计算机解决问题的一般过计算机解决问题的一般过程程提提出出问问题题分分析析问问题题设设计计算算法法编编程程调调试试解
6、解决决问问题题程序的改进y5=int(input(排成5列纵队，余下的人数：)y6=int(input(排成6列纵队，余下的人数：)y7=int(input(排成7列纵队，余下的人数：)y11=int(input(排成11列纵队，余下的人数：)A=int(input(部队总人数有几千人左右？)for X in range(A-1000,A+1000):if y5=X%5 and y6=X%6 and y7=X%7 and y11=X%11:print(部队士兵总数应该是：,X,人)任务一任务一（“学习任务单学习任务单”）历史上的“韩信点兵”计算机解决问题的一般过计算机解决问题的一般过程程提提出
7、出问问题题分分析析问问题题设设计计算算法法编编程程调调试试解解决决问问题题 分析问题分析问题X 3 3 =a 1 1X 5 5 =b 1 1X 7 7 =c 1 1士兵人数（士兵人数（X X）的大致范围）的大致范围:600:600余人余人 设计算法设计算法算法一：枚举法算法一：枚举法简便简便 设计算法设计算法算法二：解析法算法二：解析法提升算法的效率提升算法的效率 设计算法设计算法X 3 3 =a 1 1X 5 5 =b 1 1X 7 7 =c 1 1算法二：解析法算法二：解析法X-1=3 3 aX-1=5 5 bX 1=7 7 c 同余问题同余问题X-1X-1同时满足被同时满足被3 3、5
8、5、7 7整除。整除。设计算法设计算法算法二：解析法算法二：解析法X=105*n+1同余问题同余问题Xmin=357+1 =105+1 =106n=(600+100)/105任务二任务二（“学习任务单学习任务单”）解析式：解析式：X=105 X=105*n+n+余数余数尝试画出流程图尝试画出流程图A=int(input(士兵约有几百来人？)y=int(input(排好3列、5列、7列纵队后，所余人数为：)n=(A+100)/105X=105*n+yprint(这群士兵有：,X,人。)编程调试编程调试同余问题同余问题 编程调试编程调试 解决问题解决问题新问题n 如果不同余？如果不同余？X 3 3
9、 =a y1y1X 5 5 =b y2y2X 7 7 =c y3y3 设计算法设计算法算法二：解析法算法二：解析法“物不知数物不知数”（孙子算经孙子算经）“孙子歌诀孙子歌诀”（明（明程大位）程大位）设计算法设计算法算法二：解析法算法二：解析法孙子歌诀孙子歌诀除百零五便得知。除百零五便得知。三人同行七十稀，三人同行七十稀，五树梅花廿一支，五树梅花廿一支，七子团圆正半月，七子团圆正半月，X+y1y1 =3 3 a X+y2y2 =5 5 b X+y3y3 =7 7 c 设计算法设计算法算法二：解析法算法二：解析法除百零五除百零五便得知。便得知。三三人同行人同行七十七十稀，稀，五五树梅花树梅花廿一廿
10、一支，支，七七子团圆子团圆正半月正半月，y170y221y315y170+y221+y315-105n70=2(57）21=3715=35A=int(input(士兵约有几百人？)y1=int(input(排3列纵队，所余人数为：)y2=int(input(排5列纵队，所余人数为：)y3=int(input(排7列纵队，所余人数为：)for n in range(A-100)/105,(A+100)/105):X=y1*70+y2*21+y3*15-105*n if X A-100 and X A-100 and X A-100 and X A-100 and X A-100 and X A-
11、100 and X A+100:print(这群士兵有：,X,人。)任务三任务三（“学习任务单学习任务单”）提示：提示：X=y1*70+y2*21+y3*15-105*nX=y1*70+y2*21+y3*15+105*n新程序要实现的功能如下：新程序要实现的功能如下：（1 1）输入输入士兵人数的士兵人数的大约数量（整百值）大约数量（整百值）；（2 2）输入输入士兵排成士兵排成3 3、5 5、7 7列纵队后分别得到的余数；列纵队后分别得到的余数；（3 3）程序运行后，）程序运行后，输出输出士兵准确的人数。士兵准确的人数。课堂小结课堂小结韩信点兵韩信点兵体验体验计算机解决计算机解决问题的过程问题的
12、过程提提出出问问题题分分析析问问题题设设计计算算法法编编程程调调试试解解决决问问题题综合应用综合应用1 1数值计算数值计算课堂小结课堂小结实践实践算法算法枚举法枚举法解析法解析法提提出出问问题题分分析析问问题题设设计计算算法法编编程程调调试试解解决决问问题题综合应用综合应用1 1数值计算数值计算韩信点兵韩信点兵体验体验计算机解决计算机解决问题的过程问题的过程课后练习课后练习 “鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？”算经算经（北魏（北魏张丘建）张丘建）【译文】公鸡每只五文钱，母鸡每只三文钱，小鸡每只一文钱。用一百文钱买了100只鸡，公鸡、母鸡、小鸡各买了多少只？要求：编写程序，解决此问题。要求：编写程序，解决此问题。注意：算法注意：算法执行执行的效率；的效率；交互交互界面界面的的友好。友好。
