高二数学算法案例2

1.3 算法案例［学习目标导航］学习提示1. 通过对中国古代算法研究的学习，了解中国古代伟大的文化成就，增强民族自豪感.2.通过对算法案例的学习，进一步理解算法的思想，能够用程序来解决生活中常见的数学问题.3.理解进位制，能进行各种进位制之间的相互转化.重点是进位制，用算法设计程序；难点是在程序设计中用好三种基本的逻辑结构.［教材优化全析］全析提示我们通过程序框图形象、直观地表示算法，因此，在编制程序前，先绘出程序框图，能使思路清晰，并且对于三种基本的逻辑结构：顺序结构、条件结构、循环结构的脉络表达准确，有助于我们准确写出程序语言.（一）教材上介绍了辗转相除法（欧几里得算法），求两个数的最大公约数，其基本步骤是带余除法m=nq+r（0≤r＜n），反复执行，直到余数r=0为止.求任意两个数的最大公约数的算法是：程序框图比自然语言的描述更容易理解.一般说来，设计程序时，先画程序框图比较好.第一步：输入两个正整数a，b（a＞b）；第二步：求出a÷b的余数r；第三步：令a=b，b=r，若r≠0，重复第二步；第四步：输出最大公约数a. 举例说明.m=90，n=36，m=2n+18，r=18. 令m=36，n=18.相应的程序框图是：又有36=18×2，即m=2n，此时r=0.令m=18，n=0.故最大公约数为18.两个数a，b的最大公约数一般写成（a，b），如90与36的最大公约数为18，写成（90，36）=18.“更相减损术”是我国古代求最大公约数的方法，反映了我国古代劳动人民的伟大智慧，让我们感到无比的光荣与自豪.其程序语言是：INPUT “请输入两个正整数a，b：”；a，bPRINT a；b；WHILE a＜＞bIF a＞=b THENa=a－b如求78与36的最大公约数，简单写成：（78，36）→（42，36）→（36，6）→（30，6）→（24，6）→（18，6）→（12，6）→（6，6）故（78，36）=6.如两个数都为偶数，也可以先提取2，再用此ELSEb=b－aEND IFWENDPRINT “的最大公约数为：”；a END 法.PRINT a；b；表示与下一个输出语句不换行.（二）秦九韶算法求多项式的函数值，在算法上减少了求乘法的次数，使计算量减少，并且逻辑结构简单.这种算法避免了对自变量单独作幂的计算，转而与系数一起逐次增长幂次，从而提高了计算精度.这也是我国古代劳动人民智慧的结晶，是我国伟大国库中的瑰宝.例如，求五次多项式f（x）=a5x5+a4x4+a3x3+a2x2+a1x+a0，当x=x0（x0为任意实数）时的值的程序语言是：INPUT “请输入自变量x0的值：”；x0直到今天，秦九韶算法仍是世界上多项式求值的最先进的方法.这钟一成就比西方同样的算法早五、六百年.这种算法容易在计算器或计算机上实现.INPUT “请输入最高次项系数a5的值：”；a5 V=a5n=1WHILE n＜=5INPUT “请输入下一次的系数的值：”；bV=V*x0+bn=n+1 分步写成：V0=a5，V1=V0x+a4，V2=V1x+a3，V3=V2x+a2，V4=V3x+a1，V5=V4x+a0.WENDPRINT “函数值是：”；V END（三）排序是日常生活中最常见的一项活动，就是按照一定的规则，对数据加以排列整理，从而提高查找效率.教材上介绍的直接插入排序是人们最容易想到，也是最容易实现的方法.排序的方法与技巧多种多样，在不同的时间，不同的场合可以用不同的技巧.教材上介绍的冒泡排序法，非常形象地描述了较小的数像气泡一样逐趟向上飘浮，一直到最小的数浮到最上面，然后是逐渐增大的数.在这里要特别理解“一趟”的意义，它可能有多次交换.如果一趟排序交换次数为0，说明排序已经完成.每一趟都从头开始，且两个两个地比较，一直到最后一个数，每一趟可有多个交换.（四）进位制是人们为了计数和运算方便而约定的记数系统，约定满二进一，就是二进制；满十进一，就是十进制，等等.即“满几进一”就是几进制，几进制的基数就是几.常用的是十进制，用0~9这十个数字，计数时，几个数字排成一行，从右起向左分别是个位、十位、百位、千位、万位……它可以用10的幂的形式写成，如67890可以写成6×104+7×103+8×102+9×101+0×100.其他进位制也可以类似地用基数的幂的形式，如：日常生活中和普遍数学中用的都是十进制.日常生活中有七进制（一周7天）、十二进制（一年12个月）、六十进制（1小时60分，1分钟60秒），等，基数一般标在右下角.111111（2）=1×25+1×24+1×23+1×22+1×21+1×20，654321（7）=6×75+5×74+4×73+3×72+2×71+1×70. 上述方法实质上是将不同进制的数转化成了十进制的数，这类问题可统一由程序来实现.基数不同，选用的数字也不同，如二进制用0和1，六进制用0，1，2，3，4，5.我们也能把十进制的数转化为其他进制的数，用除K 取余法.方法是：用K 连续去除这个数，或所得的商，一直到商为0止，然后取其余数，把这些余数顺次排起来，就是K 进制的数.如，将1285化为16进制的数： 任何一种进位制的数都可以写成不同位上的数字与基数的幂的乘积之和的形式.1285805161616505余数最后一个余数写在首位，其次是倒数第二个余数，依次递推.故1285=505（16）在实际生活中的数学知识很多，只要我们留心，世界上到处充满着数学的气息，我国古代劳动人民在这方面积累了大量的知识和经验，有兴趣的同学不妨上网查阅一下有关资料.验证：505（16）=5×162+0×161+ 5×160=5×256+5=1285.［典型例题探究］规律发现【例1】 我国《算经十书》之一《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二.问物几何？答曰：二十三.”你能用程序解决这个问题吗？这个问题的通用解法称为“孙子剩余定理”或“中国剩余定理”.著名的“韩信点兵问题”即分析：设物共m 个，被3，5，7除所得的商分别为x 、y 、z ，则这个问题相当于求不定方程为此例的应用. ⎪⎩⎪⎨⎧+=+=+=27,35,23z m y m x m 的正整数解.m 应同时满足下列三个条件：（1）m MOD 3=2；（2）m MOD 5=3；（3）m MOD 7=2.因此，可以让m 从2开始检验，若3个条件中有任何一个不成立，则m 递增1，一直到m 同时满足三个条件为止.考虑到m 被7除余数为2，故m 至少是9，也可以从m =9开始验证. 解：m =2 f =0WHILE f =0IF m MOD 3=2 AND m MOD 5=3 AND m MOD 7=2 THEN PRINT “物体的个数为：”；m f =1 ELSE 设置f =0，f =1的目的是让循环进行或结束，否则循环无法停下来.此处让f =0时进行循环，f =1时中止循环.m =m +1 END IF WEND END实际上按此法求出来的只是符合条件的最小正整数.【例2】我国古代数学家张邱建编《张邱建算经》这个问题在数学上中记有有趣的数学问题：“今有鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一凡百钱，买鸡百只，问鸡翁、母、雏各几何？”你能用程序解决这个问题吗？分析：设鸡翁、母、雏各x 、y 、z 只，则称为“百鸡问题”. ⎪⎩⎪⎨⎧=++=++②，①，100100335z y x z y x由②，得z =100－x －y ，③把三元一次方程组转化为二元一次不定方程.③代入①，得5x +3y +3100y x --=100，即7x +4y =100. ④求方程④的解，可由程序解之. 解：x =1 y =1WHILE x ＜=14 WHILE y ＜=25IF 7*x +4*y =100 THEN z =100－x －yPRINT “鸡翁、母、雏的个数别为：”；x ，y ，z END IF y =y +1从x 的最小值开始验证，循环进行.由于7x +4y =100，且x 、y ∈Z ，故x ≤14，y ≤25.WENDx=x+1y=1WENDEND实际上，该题可以不对方程组进行化简，通过设置多重循环的方式得以实现.由①、②可得x最大值为20，y最大值为33，z最大值为100，且z为3的倍数.程序如下：x=1y=1z=3WHILE x＜=20WHILE y＜=33WHILE z＜=100IF 5*x+3*y+z/3=100 ANDx+y+z=100 THENPRINT “鸡翁、母、雏的个数分别为：”；x、y、zEND IFz=z+3WEND对于多重循环或条件嵌套，要注意每一重都有开头和结尾，程序本身也有一个结尾，不能丢掉任何一个.y=y+1z=3WENDx=x+1y=1WENDEND【例3】写出用二分法求方程x3－x－1=0在区间［1，1.5］上的一个解的算法（误差不超过0.001）.分析：教材P23练习第1题已研究过求x2－2=0的近似根的方法.本例与上述方法类似，只是方程稍微复杂了些.由于f（1）=13－1－1=－1＜0，f（1.5）=1.53－1.5－1=0.875＞0，所以取［1，1.5］中点25.11 =1.25研究，以下同求x2－2=0的根的方法.解：a=1b=1.5c=0.001DOx=（a+b）/2f（a）=a∧3－a－1f（x）=x∧3－x－1IF f（x）=0 THEN用二分法求方程的近似值一般取区间［a，b］具有以下特征：f（a）＜0，f（b）＞0.相应的程序框图是：PRINT “x =”；x ELSEIF f （a ）*f （x ）＜0 THEN b =x ELSE a =x END IF END IFLOOP UNTIL ABS （a －b ）＜=c PRINT “方程的一个近似解x =”；x END【例4】 （1）将101111011（2）转化为十进制的数； （2）将53（8）转化为二进制的数.分析：（1）将各位上的数字与基数的幂的积求和. （2）先转化为十进制的数，再利用除2取余法. 解：（1）101111011（2）=1×28+0×27+1×26+1×25+1×24+1×23+0×22+1×21+1=379.（2）53（8）=5×81+3=43.余数432110521222222110101不同进位制之间的转化是一种通法，必须熟练掌握.∴53（8）=101011（2）.注意取余数的顺序：【例5】用冒泡排序法将下列各数排成一列：8，6，3，18，21，67，54.并写出各趟的最后结果及各趟完成交换的次数.分析：每一趟都从头开始，两个两个地比较，若前者小，则两数位置不变；否则，调整这两个数的位置.从下向上.解：第一趟的结果是：6 3 8 18 21 54 67完成3次交换.第二趟的结果是：3 6 8 18 21 54 67完成1次交换.第三趟交换次数为0，说明已排好次序，即3 6 8 18 21 54 67.【例6】用秦九韶算法写出求f（x）=1+x+0.5x2+0.16667x3+0.04167x4+0.00833x5在x=－0.2时的值的过程.分析：先把函数整理成注意“一趟”的意义：每一趟都从头开始，每两个两个地比较，一直到最后一个数.f（x）=（（（（0.00833x+0.04167）x+0.16667）x+0.5）x+1）x+1，按照从内向外的顺序依次进行.解：x=－0.2a5=0.00833 V0=a5=0.008333a4=0.04167 V1=V0x+a4=0.04相当于用提公因式法分解因式.a3=0.016667 V2=V1x+a3=0.15867 a2=0.5 V3=V2x+a2=0.46827a1=1 V4=V3x+a1=0.90635a0=1 V5=V4x+a0=0.81873∴f（－0.2）=0.81873.通过分解步骤看出作乘法的次数少，比直接代入求幂的运算速度要快得多.［教材习题研讨］P21思考答案：当计算机遇到UNTIL语句时，先执行一次循环体，再判断是否满足条件，若不满足，再执行循环体，然后再检查是否满足条件，如此反复.当满足条件时，将不执行循环体，转而执行LOOP UNTIL后的语句. 方法点拨WHILE语句称为前测试型，UNTIL语句称为后测试型.P22思考答案：课本上的算法可以改进.将循环条件“WHILE d＜=n－1 AND flag=1”改为“WHILE d＜=SQR（n）AND flag=1”即可.改进后循环次数少了，提高了解题速度.P23练习1.解：a=1b=2c=0.005若改为INPUT“请输入a、b的值：”；a、bINPUT “请输入误DOx=（a+b）/2f（a）=a∧2－2f（x）=x∧2－2IF f（x）=0 THENPRINT “方程根为：”；x ELSEIF f（a）*f（x）＜0 THENb=x 差范围c：”；c则该题的区间范围、误差范围还可以改变、限制.ELSEa=xEND IFEND IFLOOP UNTIL ABS（a－b）＜=c PRINT “方程的近似根为：”；x END|a－b|＜=c不成立时循环，成立时则停止循环.2.解：x=1WHILE x＜=20y=x∧2－3*x+5PRINT “x=”；xPRINT “y=”；yx=x+1计算一个、输出一个，再计算、输出下一个，如此反复.WEND END3.解：t=1i=1INPUT “请输入n的值：”；n DOt=t*ii=i+1LOOP UNTIL i＞nPRINT “这个数的阶乘为：”；t END也可以用WHILE语句WHILE i＜=nt=t*ii=i+1WEND输出语句可写成PRINT n；“！=”；tP23习题1.2A组1.解：（1）输入你的名字，输出你的名字.（2）A=1 A=1×2=2 A=2×3=6 A=6×4=24 A=24×5=120 输出5! 是120正确理解输入语句、输出语句和赋值语句.2.解：INPUT “梯形的上底、下底、高分别为：”；a，b，hc=（a+b）/2S=c*hPRINT “梯形的面积S=”；SENDa，b，h可分别输入，写成三个INPUT语句.3.解：INPUT “请输入两个整数a ，b ：”；a ，b IF a MOD b =0 THEN PRINT “a 能被b 整除” MOD 表示取余数，整除即余数为0.输出语句可以写成 ELSEPRINT “a 不能被b 整除” END IF END4.解：INPUT “请输入加数的个数n ：”；nt =1 i =2 PRINT a ；“能被”；b ；“整除”sum=0 DOsum=sum+i t =t +1 i =tt 1s um=s um+i 是累加求和，t =t +1表示计数器.LOOP UNTIL t ＞n PRINT “和s =”；sum END 可以用WHILE 语句，条件是t ＜=n .5.解：s =1t =1 p =1 i =1设置三个计数器，三j=1k=1INPUT “请输入n，m的值：”；n，mDOs=s*ii=i+1LOOP UNTIL i＞n个独立的循环结构.DOt=t*jj=j+1LOOP UNTIL j＞mDOp=p*kk=k+1LOOP UNTIL k＞n－ma=t*pb=s/aPRINT “组合数的值为：”；b END可以写成WHILE语句，同学们自己写出.B组1.解：R=0.5a=10002008年底资金总额为1000（1+0.5）6万i=1DOa=a*（1+R）i=i+1LOOP UNTIL i＞6PRINT “2008年底的资金总额为：”；a END 元，设计成累乘的形式，用循环结构.如用INPUT 语句输入a、R的值，则具有一般意义.2.解：INPUT “请输入x的值：”；x IF x＜1 THENy=xPRINT “y=”；yELSEIF x＜10 THENy=2*x－1PRINT “y=”；yELSEy=3*x－11PRINT “y=”；yEND IFEND IFEND分段函数对应于条件结构，用条件语句的形式，可以形成嵌套.3.解：INPUT “请输入数字a和加数的个数n：”；实数aaaa=a×a，ns=0b=ai=1DOs=s+bb=b*10+ai=i+1LOOP UNTIL i＞nPRINT “s=”；sEND 103+a×102+a×10+a，aaaa=aaa×10+a，类推.［知识应用自测］思路导引1.写出下列程序运行的结果.（1）a=2 （2）x=100i=1 i=1WHILE i＜=6 DOa=a+1 x=x+10PRINT i，a PRINT i，xi=i+1 i=i+1 ←理解当型语句和直到型语句的不同，理解循环体的执行步骤.WEND LOOP UNTIL x=200END END答案：（1）1，3；2，4；3，5；4，6；5，7；6，8.（2）1，110；2，120；3，130；4，140；5，150；6，160；7，170；8，180；9，190；10，200.←用UNTIL语句.2.求小于100的所有正偶数的和，设计一个算法的程序.解：s=2i=4DOs=s+ii=i+2LOOP UNTIL i＞=100PRINT “2+4+6+…+98=”；sEND←用WHILE语句.3.计算100×（1+0.02）8，用循环语句写出算法.解：a=100R=0.002i=1WHILE i＜=8a=a*（1+R）i=i+1WENDPRINT “100*（1+0.002）∧8=”；aEND←用UNTIL语句.4.求平方值小于1000的最大正整数，写出一个算法的程序.解：i=1DOs=i∧2i=i+1LOOP UNTIL s＞=1000i=i－2PRINT “平方值小于1000的最大正整数为：”；iEND5.计算1+2+22+23+24+…+263，写出算法的程序.←用WHILE语句.解：s=1n=2i=1WHILE i＜=63s=s+n∧ii=i+1WENDPRINT “1+2+2∧2+2∧3+…+2∧63=”；s END6.1，1，2，3，5，8，13，21，…这一列数的规律是：从第三个数开始，每个数为其前面两个数的和，写出计算这列数前20个数的和的算法程序.解：A=1B=1s=A+Bi=1WHILE i＜=18C=A+Bs=s+CA=BB=Ci=i+1WENDPRINT “前20个数的和为：”；sEND ←用WHILE语句，设置累加项.7.设计0°~180°间隔为10°的角的正弦值的求法程序.解：A=0DO←用t=t+10的形式.C=3.14159265*A/180B=sin（C）PRINT “角和它的正弦值分别为：”；A，BA=A+10LOOP UNTIL A＞180END←用UNTIL语句.8.2000年我国人口为13亿，如果人口每年的自然增长率为7‰，那么多少年后我国人口将达到15亿？设计一个算法的程序.解：A=13R=0.007i=1DOA=A*（1+R）i=i+1LOOP UNTIL A＞=15i=i－1PRINT “达到或超过15亿人口需要的年数为：”；iEND←用UNTIL语句.9.编写求乘积为399的两个相邻奇数的程序.解：i=1DOt=i+2s=i*ti=i+2LOOP UNTIL s=399 PRINT t－2，tEND。

1.3.1 算法案例---辗转相除法与更相减损术教学要求：理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析； 基本能根据算法语句与程序框图的知识设计出辗转相除法与更相减损术完整的程序框图并写出它们的算法程序.教学重点：理解辗转相除法与更相减损术求最大公约数的方法.教学难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言.教学过程：一、复习准备：1. 回顾算法的三种表述：自然语言、程序框图（三种逻辑结构）、程序语言（五种基本语句）.2. 提问：①小学学过的求两个数最大公约数的方法？（先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.）口算出36和64的最大公约数. ②除了用这种方法外还有没有其它方法？6436128=⨯+，36∴和28的最大公约数就是64和36的最大公约数，反复进行这个步骤，直至842=⨯，得出4即是36和64的最大公约数.二、讲授新课：1. 教学辗转相除法：例1：求两个正数1424和801的最大公约数.分析：可以利用除法将大数化小，然后逐步找出两数的最大公约数. （适用于两数较大时）①以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的. 利用辗转相除法求最大公约数的步骤如下：（1）用较大的数m 除以较小的数n 得到一个商0S 和一个余数0R ；（2）若0R ＝0，则n 为m ，n 的最大公约数；若0R ≠0，则用除数n 除以余数0R 得到一个商1S 和一个余数1R ；（3）若1R ＝0，则1R 为m ，n 的最大公约数；若1R ≠0，则用除数0R 除以余数1R 得到一个商2S 和一个余数2R ；……依次计算直至n R ＝0，此时所得到的1n R -即为所求的最大公约数.②由上述步骤可以看出，辗转相除法中的除法是一个反复执行的步骤，且执行次数由余数是否等于0来决定，所以我们可以把它看成一个循环体，它的程序框图如右图：（师生共析，写出辗转相除法完整的程序框图和程序语言）练习：求两个正数8251和2146的最大公约数. （乘法格式、除法格式）2. 教学更相减损术：我国早期也有求最大公约数问题的算法，就是更相减损术. 在《九章算术》中有更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母•子之数，以少减多，更相减损，求其等也，以等数约之.翻译为：（1）任意给出两个正数；判断它们是否都是偶数. 若是，用2约简；若不是，执行第二步.（2）以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数. 继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数.例2：用更相减损术求91和49的最大公约数.分析：更相减损术是利用减法将大数化小，直到所得数相等时，这个数（等数）就是所求的最大公约数. （反思：辗转相除法与更相减损术是否存在相通的地方）练习：用更相减损术求72和168的最大公约数.3. 小结：辗转相除法与更相减损术及比较①都是求最大公约数的方法，辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少；②结果上，辗转相除法体现结果是以相除余数为0得到，而更相减损术则以减数与差相等而得到.三、巩固练习：1、练习：教材P35第1题四、作业：教材P38第1题。

高二数学算法案例试题答案及解析1. 两个二进制数101(2)与110(2)的和用十进制数表示为( ) A ．12 B ．11 C ．10D ．9【答案】B【解析】101(2)＝22＋0×21＋1×20＝5,110(2)＝1×22＋1×21＋0×20＝6. 【考点】二进制数与十进制数的互相转化．2. 用辗转相除法求294和84的最大公约数时，需要做除法的次数是 A ．1 B ．2 C ．3D ．4【答案】B【解析】由辗转相除法可知：，所以需要做除法的次数是2.【考点】算法的应用.3. 将十进制数102转化为三进制数结果为：【答案】10210.【解析】将十进制数转化为3进制数的方法为除3取余法，再把各步所得的余数从下到上排列即得10210.【考点】算法的应用.4. 设、、为整数（），若和被除得的余数相同，则称和对模同余，记为（）。

已知，则的值可以是（ ） A ．2015 B ．2011 C ．2008 D ．2006【答案】B 【解析】因为的余数为1, 的值可以是2011，故选B. 【考点】新定义的应用点评：主要是理解同余的概念，然后借助于二项式定理来得到结论，属于基础题。

5. （本题满分12分）将101111011（2）转化为十进制的数； 【答案】379【解析】解： 101111011（2）=1×28+0×27+1×26+1×25+1×24+1×23+0×22+1×21+1=379. 【考点】本试题考查了进位制的转换运算。

点评：将k 进位制转化内十进制，只要将各个数位上的数乘以k 的次幂即可，注意n 位数的最好次幂为n-1次幂，然后依次类推相加得到结论。

属于基础题。

6. 阅读上图的程序框图, 若输出的值等于,那么在程序框图中的判断框内应填写的条件是（ ）A．?B．?C．?D．?【答案】A【解析】第一次循环：S=1+1=2，i=2，不满足条件，执行循环；第二次循环：S=2+2=4，i=3，不满足条件，执行循环；第三次循环：S=4+3=7，i=4，不满足条件，执行循环；第四次循环：S=7+4=11，i=5，不满足条件，执行循环；第五次循环：S=11+5=16，i=6，满足条件，退出循环体，输出S=16，故判定框中应填i＞5或i≥6，故选：A。