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

1.4　算法案例

名师导航

三点剖析

一、“韩信点兵——孙子问题”的算法

在“韩信点兵”的问题中，当士兵排成3列纵队，结果多余2人说明士兵的总人数除以3之后余数是2，所以算法步骤就是将所有除以3之后余数是2的正整数找出来，按照从小到大的顺序排成一列数；当士兵排成5列纵队，结果多余3人说明士兵的总人数除以5之后余数是3，所以算法步骤就是将所有除以5之后余数是3的正整数找出来，按照从小到大的顺序排成一列数；当士兵排成7列纵队，结果多余2人说明士兵的总人数除以7之后余数是2，所以算法步骤就是将所有除以7之后余数是2的正整数找出来，按照从小到大的顺序排成一列数.这样完成上述步骤之后，就找到了“韩信点兵”问题的一个算法，从而也得出了解决“孙子问题”的算法.

我国古代数学的发展有着自己的鲜明特色，走着与西方完全不同的道路，即使今天看来，这条路仍然有很大的优越性.这条道路的一个重要特色就是“寓理于算”，即把要解决的问题“算法化”.本节中案例1直接体现了我国古代算法在数学和计算机程序设计中的广泛应用.

二、求两个正整数最大公约数的算法.

求两个正整数的最大公约数的算法常见的有“欧几里得辗转相除法”和“更相减损术”.

1.“欧几里得辗转相除法”

求两个正整数a、b（a>b）的最大公约数，可以归结为求一数列：a，b，r1，r2，…，r n－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.“更相减损术”

“更相减损术”是我国的《九章算术》中提到的一种求两个正数最大公约数的算法，它与“辗转相除法”相似.它的基本思想是：让两个数中较大的数减去较小的数，以差和较小的数组成一对新数，再比较两数的大小，然后让两数中较大的数减去较小的数，以同样的操作一直做下去，直到产生一对相等的数为止，这个数就是两个数的最大公约数.从某种意义上说，“更相减损术”就是“欧几里得辗转相除法”.

问题探究

问题1:古今中外，许多人致力于圆周率的研究与计算.为了计算出圆周率的越来越好的近似值，一代代的数学家为这个神秘的数贡献了无数的时间与心血.我国东汉的数学家刘徽利用“割圆术”计算圆的面积及圆周率π.“割圆术”被称为千古绝技，它的原理是用圆内接正多边形的面积去逼近圆的面积，具体计算如下：

在单位圆内作内接正六边形，其面积记为A1，边长记为a1，在此基础上作圆内接正12边形，面积记为A2，边长为a2……一直作下去，记该圆的内接正6×2n－1边形面积为An，边长为a n.由于所考虑的是单位圆，计算出的An即为圆周率π的近似值，n越大，An与π越接近.

你能设计这样计算圆周率的一个算法吗？

图5-31

探究：应首先推导出a n，an－1，An，An－1的关系.如图531所示，设PQ为圆内接正6×2 n－1边形的一边，即PQ=an－1，OR为与PQ垂直的半径，R为PQ弧的平分点，显然PR=a n.

a1=1，

通过上面两式，从a1＝1开始进行迭代，可逐步计算出an与An.由于所考虑的是单位圆，计算出的An即为圆周率π的近似值，n越大，A n与π越接近.算法和流程图如下：

Read n

1←a

For I from 2 to n

　　A←3×2I－2×a

　　a←Sqrt［2－2×Sqrt［1－a2/4］］；

Print I，A，a

End for

End

流程图（如图5-32所示）：

图5-32

问题2:据我国古书《唐阙史》记载，公元855年前后，有一次，青州府要从两个办事员中选拔一人当官，但是这两个办事员的职务、资历、能力和成绩、表现并无显著的差异，而名额只有一个，提升谁？负责提升的官员感到十分为难，就去请教青州的地方官杨埙.杨埙考虑了很久，想出了一个主意，他说：“官员应该能写会算，你把他们叫来，我出一道题当场考考他们，谁先算出就提升谁.”同时，杨埙让人把他出的题抄成两份，负责提升的官员找来两位办事员，给每人一袋算筹，一声令下两个人开始解题，不一会儿，其中一个先算出了正确答案，杨埙当场宣布提升他.大家都认为杨埙这种办法比较公允.在古代，像这样用“数学竞赛”来决定官员晋升是为数不少的.题目的大意如下:

一天夜里，有一个人在林中散步，无意中听到几个强盗在商量怎样分配抢来的布匹，只听见他们说：“如果每人分6匹，就剩5匹；如果每人分7匹，就差8匹.”问有强盗几个？布匹多少？能用一个简单算法求出强盗个数和布匹数吗？

探究：中国古代的《九章算术》一书中搜集了许多这类问题，各题都有完整的解法，后人称这种算法为——“盈不足术”.

这种算法可以概括为两句口诀：有余加不足，大减小来除.

公式：（盈＋不足）÷两次所得之差＝人数，

每人所得数×人数＋盈＝物品总数，

求得强盗有（8＋5）÷（7－6）＝13（人），布匹有6×13＋5＝83（匹）.

伪代码：

Read a，b，c，d

x←（a+b）/（d－c）

y←cx+a

print x，y

流程图（如图5-33所示）：

图5-33

除此之外，这个问题可看作二元一次方程组问题.问题的特点是给出两种分配方案，一种分法分不完，一种分法不够分.所以，本题还有一种方法，就是利用二元一次方程组的方法来解题.首先，根据题意设有强盗x个，布匹y匹，则可列出二元一次方程如下：6x=y-5, 7x=y+7.

然后再根据解二元一次方程组的算法写出该题的算法即可.

精题精讲

例1．求1 734，816，1 343的最大公约数.

思路解析

三个数的最大公约数分别是每个数的约数，因此也是任意两个数的最大公约数的约数，也就是说三个数的最大公约数是其中任意两个数的最大公约数与第三个数的最大公约数.

解：用“辗转相除法”.

先求1 734和816的最大公约数，

1 734=816×2+102；

816=102×8；

所以1 734与816的最大公约数为102.

再求102与1 343的最大公约数，

1 343=102×13+17；

102=17×6.

所以1 343与102的最大公约数为17，即1 734，816，1 343的最大公约数为17.

绿色通道

求两个正整数a、b（a>b）的最大公约数，可以归结为求一数列：a，b，r1，r2，…，r n－1，rn，rn+1，0,

此数列的首项与第二项是a和b，从第三项开始的各项，分别是前两项相除所得的余数，如果余数为0，它的前项rn+1 即是a和b的最大公约数，这种方法叫做“欧几里得辗转相除法”.

例2．猴子吃桃问题：有一堆桃子不知数目，猴子第一天吃掉一半，觉得不过瘾，又多吃了一只，第二天照此办法，吃掉剩下桃子的一半另加一个，天天如此，到第十天早上，猴子发现只剩一只桃子了，问这堆桃子原来有多少个？

思路解析

此题粗看起来有些无从着手的感觉，那么怎样开始呢？假设第一天开始时有a1只桃子，第二天有a2只,…,第9天有a9只，第10天有a10只.在a1，a2，…，a10中，只有a10=1是知道的，现要求a1，而我们可以看出a1，a2，…，a10之间存在一个简单的关系：

a9=2×（a10+1），

a8=2×（a9+1），

…

a1=2×（a2+1）.

也就是：ai=2×（ai+1+1）,i=9，8，7，6，…，1.

这就是此题的数学模型.

再考察上面从a9，a8直至a1的计算过程，这其实是一个递推过程，这种递推的方法在计算机解题中经常用到.另一方面，这九步运算从形式上完全一样，不同的只是ai的下标而已.由此，我们引入循环的处理方法，并统一用a0表示前一天的桃子数，a1表示后一天的桃子数.

解：本题的算法如下：

S1　a1←1；｛第10天的桃子数，a1的初值｝

S2　i←9；｛计数器初值为9｝

S3　a0←2×（a1+1）；｛计算当天的桃子数｝

S4　a1←a0；｛将当天的桃子数作为下一次计算的初值｝

S5　i←i－1；

S6　若i≥1，转S3；

S7　输出a0的值.

伪代码如下：

10　a1←1

20　i←9

30　a0←2×（a1+1）

40　a1←a0

50　i←i－1

60　If i≥1 then Goto 30

70　Else

80　Print a0

流程图如图5-34所示：

图5-34

绿色通道

这类题的解法是一个从具体到抽象的过程，具体方法是：

（1）弄清如果由人来做，应该采取哪些步骤；

（2）对这些步骤进行归纳整理，抽象出数学模型；

（3）对其中的重复步骤，通过使用相同变量等方式求得形式的统一，然后简练地用循环 解决.

本文来源：https://www.2haoxitong.net/k/doc/403a6ea3a88271fe910ef12d2af90242a895abad.html