《算法案例》教案（1）

算法案例教学目标通过了解中国古代算法案例，体会中国古代数学对世界数学发展的贡献．重点难点通过案例分析，体会算法思想，熟练算法设计．例题剖析【案例1】韩信是秦末汉初的著名军事家，据说有一次汉高祖刘邦在

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