《算法案例》学案

　　此资源为用户分享，在本站免费下载，只限于您用于个人教学研究。

约1720字。

　　总 课 题 算法案例 总课时 第 9 课时
　　分 课 题 算法案例 分课时 第 1 课时
　　教学目标 通过了解中国古代算法案例，体会中国古代数学对世界数学发展的贡献．
　　重点难点 通过案例分析，体会算法思想，熟练算法设计．
　　例题剖析
　　【案例1】
　　韩信是秦末汉初的著名军事家，据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场，刘邦问韩信有什么办法，不要逐个报数，就能知道场上士兵的人数．
　　韩信先令士兵排成3列纵队，结果有2人多余；接着他立刻下令将队形改为5列纵队，这一改，又多出3人；随后他又下令改为7列纵队，这一次又剩下2人无法成整行．韩信看此情形，立刻报告共有士兵2333人．
　　众人都愣了，不知韩信用什么办法清点出准确人数的．
　　这个故事是否属实，已无从查考，但这个故事却引出一个著名的数学问题，即闻名世界的“孙子问题”．
　　这种神机妙算，最早出现在我国《算经十书》之一的《孙子算经》中，原文是：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰：二十三．”
　　所以人们将这种问题的通用解法称为“孙子剩余定理”或“中国剩余定理”．
　　【算法设计思想】
　　“孙子问题”相当于求关于 的不定方程组 的整数解．
　　设所求的数为 ，根据题意， 应同时满足下列三个条件：
　　（1） 被 除后余 ，即 ；
　　（2） 被 除后余 ，即 ；
　　（3） 被 除后余 ，即 ；
　　首先，从 开始检验条件，若 个条件中有任何一个不满足，则 递增 ，当 同时满足 个条件时，输出 ．
　　【流程图】                           【伪代码】
　　【案例2】
　　写出求两个正整数 的最大公约数的一个算法．
　　公元前3世纪，欧几里得介绍了求两个正整数 的最大公约数的方法，即求出一列数： ，这列数从第三项开始，每一项都是前两项相除所得的余数（即 ），余数等于 的前一项 ，即是 和 的最大公约数，这种方法称为“欧几里得辗转相除法”．
　　【算法设计思想】
　　欧几里得展转相除法求两个正整数 的最大公约数的步骤是：计算出 的余数 ，若 ，则 即为 的最大公约数；若 ，则把前面的除数 作为新的被除数，把余数 作为新的除数，继续运算，直到余数为 ，此时的除数即为 的最大公约数．
　　求 的最大公约数的算法为：
　　输入两个正整数 ；
　　如果 ，那么转 ，否则转 ；
　　；
　　；
　　，转 ；
　　输出 ．
　　【流程图】                            【伪代码】