高中数学第1章算法初步1.4算法案例名师导航学案苏教版必修

《高中数学第1章算法初步1.4算法案例名师导航学案苏教版必修》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.4　算法案例名师导航三点剖析一、“韩信点兵——孙子问题”的算法在“韩信点兵”的问题中，当士兵排成3列纵队，结果多余2人说明士兵的总人数除以3之后余数是2，所以算法步骤就是将所有除以3之后余数是2的正整数找出来，按照从小到大的顺序排成一列数；当士兵排成5列纵队，结果多余3人说明士兵的总人数除以5之后余数是3，所以算法步骤就是将所有除以5之后余数是3的正整数找出来，按照从小到大的顺序排成一列数；当士兵排成7列纵队，结果多余2人说明士兵的总人数除以7之后余数是2，所以算法步骤就是将所有除以7之后余数是2的正整数找出来，按

2、照从小到大的顺序排成一列数.这样完成上述步骤之后，就找到了“韩信点兵”问题的一个算法，从而也得出了解决“孙子问题”的算法.我国古代数学的发展有着自己的鲜明特色，走着与西方完全不同的道路，即使今天看来，这条路仍然有很大的优越性.这条道路的一个重要特色就是“寓理于算”，即把要解决的问题“算法化”.本节中案例1直接体现了我国古代算法在数学和计算机程序设计中的广泛应用.二、求两个正整数最大公约数的算法.求两个正整数的最大公约数的算法常见的有“欧几里得辗转相除法”和“更相减损术”.1.“欧几里得辗转相除法”求两个正整数a、b（a

3、>b）的最大公约数，可以归结为求一数列：a，b，r1，r2，…，rn－1，rn，rn+1，0.此数列的首项与第二项是a和b，从第三项开始的各项，分别是前两项相除所得的余数，如果余数为0，它的前项rn+1即是a和b的最大公约数.其步骤是：计算出a除以b的余数r，若r=0,则b为a、b的最大公约数；若r≠0,则把b作为被除数，把余数r作为除数，继续运算，直到余数为0，此时的除数即为自然数a、b的最大公约数.2.“更相减损术”“更相减损术”是我国的《九章算术》中提到的一种求两个正数最大公约数的算法，它与“辗转相除法”相似

4、.它的基本思想是：让两个数中较大的数减去较小的数，以差和较小的数组成一对新数，再比较两数的大小，然后让两数中较大的数减去较小的数，以同样的操作一直做下去，直到产生一对相等的数为止，这个数就是两个数的最大公约数.从某种意义上说，“更相减损术”就是“欧几里得辗转相除法”.问题探究问题1:古今中外，许多人致力于圆周率的研究与计算.为了计算出圆周率的越来越好的近似值，一代代的数学家为这个神秘的数贡献了无数的时间与心血.我国东汉的数学家刘徽利用“割圆术”计算圆的面积及圆周率π.“割圆术”被称为千古绝技，它的原理是用圆内接正多边形

5、的面积去逼近圆的面积，具体计算如下：在单位圆内作内接正六边形，其面积记为A1，边长记为a1，在此基础上作圆内接正12边形，面积记为A2，边长为a2……一直作下去，记该圆的内接正6×2n－1边形面积为An，边长为an.由于所考虑的是单位圆，计算出的An即为圆周率π的近似值，n越大，An与π越接近.你能设计这样计算圆周率的一个算法吗？图5-31探究：应首先推导出an，an－1，An，An－1的关系.如图531所示，设PQ为圆内接正6×2n－1边形的一边，即PQ=an－1，OR为与PQ垂直的半径，R为PQ弧的平分点，显然PR

6、=an.a1=1，通过上面两式，从a1＝1开始进行迭代，可逐步计算出an与An.由于所考虑的是单位圆，计算出的An即为圆周率π的近似值，n越大，An与π越接近.算法和流程图如下：Readn1←aForIfrom2ton　　A←3×2I－2×a　　a←Sqrt［2－2×Sqrt［1－a2/4］］；PrintI，A，aEndforEnd流程图（如图5-32所示）：图5-32问题2:据我国古书《唐阙史》记载，公元855年前后，有一次，青州府要从两个办事员中选拔一人当官，但是这两个办事员的职务、资历、能力和成绩、表现并无显著的

7、差异，而名额只有一个，提升谁？负责提升的官员感到十分为难，就去请教青州的地方官杨埙.杨埙考虑了很久，想出了一个主意，他说：“官员应该能写会算，你把他们叫来，我出一道题当场考考他们，谁先算出就提升谁.”同时，杨埙让人把他出的题抄成两份，负责提升的官员找来两位办事员，给每人一袋算筹，一声令下两个人开始解题，不一会儿，其中一个先算出了正确答案，杨埙当场宣布提升他.大家都认为杨埙这种办法比较公允.在古代，像这样用“数学竞赛”来决定官员晋升是为数不少的.题目的大意如下:一天夜里，有一个人在林中散步，无意中听到几个强盗在商量怎样分

8、配抢来的布匹，只听见他们说：“如果每人分6匹，就剩5匹；如果每人分7匹，就差8匹.”问有强盗几个？布匹多少？能用一个简单算法求出强盗个数和布匹数吗？探究：中国古代的《九章算术》一书中搜集了许多这类问题，各题都有完整的解法，后人称这种算法为——“盈不足术”.这种算法可以概括为两句口诀：有余加不足，大减小来除.公式：（盈＋不足）÷两次