高中数学第1章算法初步1.4算法案例互动课堂学案.pdf

《高中数学第1章算法初步1.4算法案例互动课堂学案.pdf》由会员分享，可在线阅读，更多相关《高中数学第1章算法初步1.4算法案例互动课堂学案.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、小学+初中+高中+努力=大学小学+初中+高中+努力=大学1.4 算法案例互动课堂例 1 求 1 734,816,1 343的最大公约数.【分析】三个数的最大公约数分别是每个数的约数,因此也是任意两个数的最大公约数的约数,也就是说三个数的最大公约数是其中任意两个数的最大公约数与第三个数的最大公约数.【解】用“辗转相除法”.先求 1 734 和 816 的最大公约数,1 734=8162+102；816=1028；所以 1 734 与 816 的最大公约数为102.再求 102 与 1 343 的最大公约数,1 343=10213+17；102=176.所以 1 343 与 102 的最大公约数为

2、17,即 1 734,816,1 343的最大公约数为17.【点 评】求 两 个 正 整 数a、b（a b）的 最 大 公 约 数,可 以 归 结 为 求 一 数 列：a,b,r1,r2,rn-1,rn,rn+1,0,此数列的首项与第二项是a 和 b,从第三项开始的各项,分别是前两项相除所得的余数,如果余数为 0,它的前项rn+1即是 a 和 b 的最大公约数,这种方法叫做“欧几里得辗转相除法”.例 2 猴子吃桃问题：有一堆桃子不知数目,猴子第一天吃掉一半,觉得不过瘾,又多吃了一只,第二天照此办法,吃掉剩下桃子的一半另加一个,天天如此,到第十天早上,猴子发现只剩一只桃子了,问这堆桃子原来有多少

3、个？【分析】此题粗看起来有些无从着手的感觉,那么怎样开始呢？假设第一天开始时有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的下标而已.由此,

4、我们引入循环的处理方法,并统一用a0表示前一天的桃子数,a1表示后一天的桃子数.【解】本题的算法如下：第一步：a11；第 10 天的桃子数,a1的初值第二步：i 9；计数器初值为9第三步：a02（a1+1）；计算当天的桃子数第四步：a1a0；将当天的桃子数作为下一次计算的初值第五步：i i-1；第六步：若i 1,转第三步；第七步：输出a0的值.伪代码如下：小学+初中+高中+努力=大学小学+初中+高中+努力=大学a11i 9If i1 Thena02（a1+1）a1a0i i-1 End If Print a0流程图如下图所示：【点评】这类题的解法是一个从具体到抽象的过程,具体方法是：（1）弄清

5、如果由人来做,应该采取哪些步骤；（2）对这些步骤进行归纳整理,抽象出数学模型；（3）对其中的重复步骤,通过使用相同变量等方式求得形式的统一,然后简练地用循环解决.例 3 古今中外,许多人致力于圆周率的研究与计算.为了计算出圆周率的越来越好的近似值,一代代的数学家为这个神秘的数贡献了无数的时间与心血.我国东汉的数学家刘徽利用“割圆术”计算圆的面积及圆周率.“割圆术”被称为千古绝技,它的原理是用圆内接正多边形的面积去逼近圆的面积,具体计算如下：在单位圆内作内接正六边形,其面积记为A1,边长记为 a1,在此基础上作圆内接正12边形,面积记为A2,边长为 a2一直作下去,记该圆的内接正62n-1边形面

6、积为An,边长为 an.由于所考虑的是单位圆,计算出的An即为圆周率 的近似值,n 越大,An与 越接近.你能设计这样计算圆周率的一个算法吗？【分析】应首先推导出an,an-1,An,An-1的关系.如右图所示,设 PQ为圆内接正62n-1边形的一边,即 PQ=an-1,OR为与 PQ垂直的半径,R 为 PQ弧的平分点,显然 PR=an.a1=1,an=PR=221212222)2(11)2()(nnaaOTORPTRTPT小学+初中+高中+努力=大学小学+初中+高中+努力=大学=212221na（n=2,3,4）,A1=621123=233,An=62n-121|OR|PT|=3 2n-2a

7、n-1（n=2,3,4）.通过上面两式,从 a1=1 开始进行迭代,可逐步计算出an与 An.由于所考虑的是单位圆,计算出的 An即为圆周率 的近似值,n 越大,An与 越接近.算法和流程图如下：Read n 1aFor I From 2 To n A32n-2aaSqrt 2-2Sqrt 1-a2/4 End For Print I,A,a 流程图（如下图所示）：例 4 据我国古书唐阙史记载,公元 855 年前后,有一次,青州府要从两个办事员中选拔一人当官,但是这两个办事员的职务、资历、能力和成绩,表现并无显著的差异,而名额只有一个,提升谁？负责提升的官员感到十分为难,就去请教青州的地方官杨

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

9、吗？小学+初中+高中+努力=大学小学+初中+高中+努力=大学【分析】中国古代的 九章算术 一书中搜集了许多这类问题,各题都有完整的解法,后人称这种算法为“盈不足术”.这种算法可以概括为两句口诀：有余加不足,大减小来除.公式：（盈不足）两次所得之差=人数,每人所得数人数盈=物品总数,求得强盗有（85）（7-6）=13（人）,布匹有 613 5=83（匹）.伪代码：Read a,b,c,d x（a+b）/（d-c）ycx+aPrint x,y 流程图（如下图所示）：除此之外,这个问题可看作二元一次方程组问题.问题的特点是给出两种分配方案,一种分法分不完,一种分法不够分.所以,本题还有一种方法,就是利用二元一次方程组的方法来解题.首先,根据题意设有强盗x 个,布匹 y 匹,则可列出二元一次方程如下：7.y7x5,-y6x然后再根据解二元一次方程组的算法写出该题的算法即可.