1.3 算法案例　　教案2

《1.3 算法案例　　教案2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.3算法案例［学习目标导航］学习提示1.通过对中国古代算法研究的学习，了解中国古代伟大的文化成就，增强民族自豪感.2.通过对算法案例的学习，进一步理解算法的思想，能够用程序来解决生活中常见的数学问题.3.理解进位制，能进行各种进位制之间的相互转化.重点是进位制，用算法设计程序；难点是在程序设计中用好三种基本的逻辑结构.［教材优化全析］全析提示我们通过程序框图形象、直观地表示算法，因此，在编制程序前，先绘出程序框图，能使思路清晰，并且对于三种基本的逻辑结构：顺序结构、条件结构、循环结构的脉络表达准确，有助于我们准确写出程序语言.（一）教材上介绍了

2、辗转相除法（欧几里得算法），求两个数的最大公约数，其基本步骤是带余除法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.故最大公约

3、数为18.两个数a，b的最大公约数一般写成（a，b），如90与36的最大公约数为18，写成（90，36）=18.“更相减损术”是我国古代求最大公约数的方法，反映了我国古代劳动人民的伟大智慧，让我们感到无比的光荣与自豪.其程序语言是：INPUT“请输入两个正整数a，b：”；a，bPRINTa；b；WHILEa＜＞bIFa＞=bTHENa=a－bELSEb=b－a如求78与36的最大公约数，简单写成：（78，36）→（42，36）→（36，6）→（30，6）→（24，6）→（18，6）→（12，6）→（6，6）故（78，36）=6.如两个数都为偶数，

4、也可以先提取2，再用此法.PRINTa；bENDIFWENDPRINT“的最大公约数为：”；aEND；表示与下一个输出语句不换行.（二）秦九韶算法求多项式的函数值，在算法上减少了求乘法的次数，使计算量减少，并且逻辑结构简单.这种算法避免了对自变量单独作幂的计算，转而与系数一起逐次增长幂次，从而提高了计算精度.这也是我国古代劳动人民智慧的结晶，是我国伟大国库中的瑰宝.例如，求五次多项式f（x）=a5x5+a4x4+a3x3+a2x2+a1x+a0，当x=x0（x0为任意实数）时的值的程序语言是：INPUT“请输入自变量x0的值：”；x0直到今天，秦

5、九韶算法仍是世界上多项式求值的最先进的方法.这钟一成就比西方同样的算法早五、六百年.这种算法容易在计算器或计算机上实现.INPUT“请输入最高次项系数a5的值：”；a5V=a5n=1WHILEn＜=5INPUT“请输入下一次的系数的值：”；bV=V*x0+bn=n+1WENDPRINT“函数值是：”；VEND分步写成：V0=a5，V1=V0x+a4，V2=V1x+a3，V3=V2x+a2，V4=V3x+a1，V5=V4x+a0.（三）排序是日常生活中最常见的一项活动，就是按照一定的规则，对数据加以排列整理，从而提高查找效率.教材上介绍的直接插入排

6、序是人们最容易想到，也是最容易实现的方法.排序的方法与技巧多种多样，在不同的时间，不同的场合可以用不同的技巧.教材上介绍的冒泡排序法，非常形象地描述了较小的数像气泡一样逐趟向上飘浮，一直到最小的数浮到最上面，然后是逐渐增大的数.在这里要特别理解“一趟”的意义，它可能有多次交换.如果一趟排序交换次数为0，说明排序已经完成.每一趟都从头开始，且两个两个地比较，一直到最后一个数，每一趟可有多个交换.（四）进位制是人们为了计数和运算方便而约定的记数系统，约定满二进一，就是二进制；满十进一，就是十进制，等等.即“满几进一”就是几进制，几进制的基数就是几.常

7、用的是十进制，用0~9这十个数字，计数时，几个数字排成一行，从右起向左分别是个位、十位、百位、千位、万位……它可以用10的幂的形式写成，如67890可以写成6×104+7×103+8×102+9×101+0×100.其他进位制也可以类似地用基数的幂的形式，如：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.上述方法实质上是将不同进制的数转化成了十进制的数，这类问题可统一由程序来实现.日常生活中和普遍数学中用的都是十进制.日常生活中有七进

8、制（一周7天）、十二进制（一年12个月）、六十进制（1小时60分，1分钟60秒），等，基数一般标在右下角.基数不同，选用的数字也不同，如