141算法案例韩信点兵学案苏教版必修3

1、第 11 课时 5.4 算法案例重点难点 重点：通过案例分析，体会算法思想，熟练算法设计，进一步理解算法的基本思想，发展有条理的思考和 表 达能力，提高逻辑思维能力。难点：在分析案例的过程中设计规范合理的算法学习要求1. 理解剩余定理的内涵2. 能利用剩余定理解决“韩信点兵一孙子问题”【课堂互动】 历史背景：韩信是秦末汉初的著名军事家，据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场，刘邦问韩信有什么办法，不要逐个报数，就能知道场上士兵的人数。韩信先令士兵排成 3列纵队，结果有2人多余；接着他立刻下令将队形改为5列纵队，这一改，又多岀3人；随后他又下令改为7列纵队，这一次又剩下 2人无法成整行。韩

2、信看此情形，立刻报告共有士兵2333人。众人都愣了，不知韩信用什么办法清点岀准确人数的。这个故事是否属实，已无从查考，但这个故事却引出一个著名的数学问题，即闻名世界的“孙子问题”。这种神机妙算，最早岀现在我国算经十书之一的孙子算经中，原文是：“今有物不知其数，二二数之剩二，五五数之剩二，七七数之剩二，问物几何？答門：二I二。”所以人们将这种问题的通用解法称为“孙子剩余定理”。【解析】“孙子问题”相当于求关于x, y, z的不定方程组m = 3x + 2< m = 5y + 3的正整数解。=7 z + 2根据题意，m应该满足三个条件:m被3除后余2,即Mod (m3) = 2m被5除后余3

3、,即Mod(m,5) = 3m被7除后余2,即Mod (mJ) = 2在自然数中可能存在满足条件的数，首先让m=2开始检验条件，若三个条件中有任何一个不满足，检验下一个数，即 m递增1,如此循环下去，一直到 m满足三个条件为止。这种解决问题的方法也称为“穷举法”，这种方法在利用计算机解决问题时非常有效，因为计算机最擅长重复机械的操作【流程图】【伪代码】m*-2End WhilePrint m【思考】上述算法只能求岀最小的满足条件的数，如果要求岀10个满足条件的数，程序要做何修改？你能否用数学上最小公倍数的知识分析岀解决该问题的方法吗？可以这样考虑：5和7的公倍数中能被 3除余2的最小的公倍数是

4、 35 ; 3和7的公倍数中能被 5除余3 的最小的公倍数是 63; 3和5的公倍数中能被 7除余2的最小的公倍数是 30;因此满足条件的其中 的一个数 就应是35+63+30,为128,若减去3、5、7的最小公倍数105得23, 23就是满足题目要求的最 小的数。你能画岀这种算法的流程图吗？【解】算法流程图如下：经典范例例古今中外，许多人致力于圆周率的研究与计算。我国东汉的数学家刘徽利用“割圆术”计算圆的面积及圆周率”。“割圆术”被称为千古绝技，它的原理是用圆内接正多边形的面积去逼近圆的面积。具体计算如下：在单位圆内作正六边形，其面积记为Aj,边长为在此基础上作圆内接十二边形，面积记为A?,

5、边长为a2,，一直做下去，记该圆的内接正6x2n-'边形面积为 A,边长为山于所考虑的是单位圆，计算岀的人口的值即是圆周率”的一个近似值，且 n越大，人口与圆周率疋越接近。你能否设计一个算法，计算圆周率的近似值？思路点拨:01 图可知 an+i =-2 - -A4 - an2 , An = 3 - 2n_2an_i , aj=l,【解n算法步骤如下：【追踪训练】1. m是一正整数，对两个正整数 a,b，若a-b是加的倍数，则称模 m同余,用符号a = b(Modm)表示.则a三5(Mod27)中，a的取值可能为()A.ll B.22C.27D.322. 有一堆围棋子，五个五个地数，最后余下2个；七个七个地数，最后余下3个；九个九个地数，最后余下4个.请设计一种算法.求出这堆棋子至少有多少个.【解】算法如下：3.（ 李白买酒 ） 无事街上走，提壶去买酒，遇店加一倍，见花喝一斗，二遇店和花，喝光壶中酒. 设计求