（苏教版）溧水县第二高级中学数学教学案必修3：第09课时（算法案例）

总 课 题 算法案例 总课时 第 9 课时
分 课 题 算法案例 分课时 第 1 课时
教学目标 通过了解中国古代算法案例，体会中国古代数学对世界数学发展的贡献．
重点难点 通过案例分析，体会算法思想，熟练算法设计．
例题剖析
【案例1】
韩信是秦末汉初的著名军事家，据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场，刘邦问韩信有什么办法，不要逐个报数，就能知道场上士兵的人数．
韩信先令士兵排成3列纵队，结果有2人多余；接着他立刻下令将队形改为5列纵队，这一改，又多出3人；随后他又下令改为7列纵队，这一次又剩下2人无法成整行．韩信看此情形，立刻报告共有士兵2333人．
众人都愣了，不知韩信用什么办法清点出准确人数的．
这个故事是否属实，已无从查考，但这个故事却引出一个著名的数学问题，即闻名世界的“孙子问题”．
这种神机妙算，最早出现在我国《算经十书》之一的《孙子算经》中，原文是：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰：二十三．”
所以人们将这种问题的通用解法称为“孙子剩余定理”或“中国剩余定理”．
【算法设计思想】
“孙子问题”相当于求关于的不定方程组的整数解．
设所求的数为，根据题意，应同时满足下列三个条件：
（1）被除后余，即；
（2）被除后余，即；
（3）被除后余，即；
首先，从开始检验条件，若个条件中有任何一个不满足，则递增，当同时满足个条件时，输出．
【流程图】 【伪代码】
【案例2】
写出求两个正整数的最大公约数的一个算法．
公元前3世纪，欧几里得介绍了求两个正整数的最大公约数的方法，即求出一列数：，这列数从第三项开始，每一项都是前两项相除所得的余数（即），余数等于的前一项，即是和的最大公约数，这种方法称为“欧几里得辗转相除法”．
【算法设计思想】
欧几里得展转相除法求两个正整数的最大公约数的步骤是：计算出的余数，若，则即为的最大公约数；若，则把前面的除数作为新的被除数，把余数作为新的除数，继续运算，直到余数为，此时的除数即为的最大公约数．
求的最大公约数的算法为：
输入两个正整数；
如果，那么转，否则转；
；
；
，转；
输出．
【流程图】 【伪代码】
【案例3】
写出方程在区间内的一个近似解（误差不超过）的一个算法．
【算法设计思想】
如下图：如果设计出方程在某区间内有一个根，就能用二分搜索求得符合误差限制的近似解．
算法步骤可表示为：
取的中点，将区间一分为二；
若，则就是方程的根，否则判断根在的左侧还是右侧；
若，则，以代替；
若，则，以代替；
若，计算终止，此时，否则转．
【流程图】 【伪代码】
巩固练习
1．下面一段伪代码的目的是______________________________________________．
注明：案例3的图
2．在直角坐标系中作出函数和的图像，根据图像判断方程的解的范围，再用二分法求这个方程的近似解（误差不超过），并写出这个算法的伪代码，画出流程图．
课堂小结
通过案例分析，体会算法思想，熟练算法设计，进一步理解算法的基本思想，在分析案例的过程中设计规范合理的算法．
课后训练
班级：高二（ ）班 姓名：____________
一　基础题
1．一种放射性物质不断变化为其它物质，每经过一年剩留下来的物质的质量约为原来，那么，约经过多少年，剩留的质量是原来的一半？试写出运用二分法计算这个近似值的伪代码．
2．设计一个算法，计算两个正整数的最小公倍数．
二　提高题
3．判断某年份是否为闰年，要看此年份数能否被整除．若不能被整除则是平年，月是天；若能被整除但不能被整除，则该年是闰年，月是天；若能被整除又能被整除，还要看能否被整除，若能则为闰年，否则为平年． 画出上述算法的流程图，并写出伪代码．
4．我国古代劳动人民对不定方程的研究作出过重要贡献，其中《张丘建算经》中的“百鸡问题”就是一个很有影响力的不定方程问题，今有鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一，凡百钱买百只，问鸡翁、鸡母、鸡雏各几何．
其意思是：
一只公鸡的价格是钱，一只母鸡的价格是钱，三只小鸡的价格是钱，想用钱买只鸡，问公鸡、母鸡、小鸡个买几只．设分别代表公鸡、母鸡、小鸡的只数，我们可以大致确定的取值范围：若钱全买公鸡，则最多可买只，即的取值范围是；若钱全买母鸡，则最多可买只，即的取值范围是；当在各自的范围内确定后，小鸡的只数也就确定了．
根据上述算法思想，画出求解的流程图，并写出相应的伪代码．
.精品资料。欢迎使用。 ( http: / / www.21cnjy.com / " \o "欢迎登陆21世纪教育网 )
，
While
c EMBED Equation.3 EMBED Equation.3
m
n
While