算法案例11.ppt

《算法案例11.ppt》由会员分享，可在线阅读，更多相关《算法案例11.ppt（33页珍藏版）》请在三一办公上搜索。

1、1.3算法案例,情境创设,韩信是秦末汉初的著名军事家.据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场,刘邦问韩信有什么方法,不要逐个报数,就能知道场上的士兵的人数,韩信先令士兵排成3列纵队,结果有2人多余,接着下令排成5列纵队,结果又多出3人,随后他又下令改为7列纵队,这次又剩下2人无法成整行.在场的人都哈哈大笑,以为韩信不能清点出准确的人数,不料笑声刚落,韩信高声报告共有士兵2333人.众人听了一楞,不知道韩信用什么方法这么快就能得到正确的结果的.今天,我们将以这些古典案例的思想,设计出适宜计算机的运行程序,提高我们对基本算法结构和算法语句在实际中的运用能力.,探究一,辗转相除法,思考1:在小

2、学中我们是如何求出两个正整数的最大公约数的呢?,算法案例之求最大公约数,求以下几组正整数的最大公约数。(注：若整数m和n满足n整除m，则（m,n）=n。用（m,n）来表示m和n的最大公约数。)（1）（18，30）（2）（24，16）（3）（63，63）（4）（72，8）（5）（301，133）,例、求18与24的最大公约数：,6；,8；,63；,8；,7；,短除法,想一想，如何求8251与6105的最大公约数？,穷举法（也叫枚举法）步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数。,穷举法,探究一,辗转相除法,思考2:当两个数的公有质因数较大时,我

3、们怎样去求两个数的最大公约数呢?辗转相除法:用于求两个正整数的最大公约数的一种算法,是由欧几里得在公元前300年左右首先提出的,因而又叫做欧几里得算法.定义:所谓的辗转相除法,就是对于给定的两个数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成新的数对,继续上面的除法,直到大数被小数除尽,则这是较小的数就是原来两个数的最大公约数.,定理：已知m,n,r为正整数，若m=nq+r（0rn）（即r=m MOD n）,则（m,n）=(n,r)。,辗转相除法的理论基础:,分析：m=nq+r r=m-nq,例1、求8251和6105的最大公约数。,148=37 4,=37,8251=6105

4、1+2146,（8251，6105）=（6105，2146）,6105=2146 2+1813,=（2146，1813）,2146=1813 1+333,=（1813，333）,1813=333 5+148,=（333，148）,333=148 2+37,=（148，37）,解：,练习：用辗转相除法求下列两数的最大公约数：（1）（225，135）（2）（98，196）（3）（72，168）（4）（153，119）,45,98,24,17,辗转相除法求两个数的最大公约数，其算法可以描述如下：,辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构,思考3：辗转相除直到何时结束？

5、主要运用的是哪种算法结构？,如此循环，直到得到结果。,输入两个正整数m和n；,求余数r：计算m除以n，将所得余数存放到变量r中；,更新被除数和余数：m=n，n=r。,判断余数r是否为0：若余数为0则输出结果，否则转向第步继续循环执行。,利用辗转相除法求最大公约数的步骤如下：,第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；(m=nq0+r0)第二步：若r00，则n为m，n的最大公约数；若r00，则用除数n除以余数r0得到一个商q1和一个余数r1；(n=r0q1+r1)第三步：若r10，则r0为m，n的最大公约数；若r10，则用除数r0除以余数r1得到一个商q2和一个余数r2；(

6、r0=r1q2+r2)依次计算直至rn0，此时所得到的rn-1 即为所求的最大公约数。,程序：INPUT“m，n=”;m,nDO r=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND,你能用当型循环结构来设计算法吗?,INPUT m,nr=1WHILE r0 r=m MOD n m=n n=rWENDPRINT mEND,思考4：你能根据辗转相除法的算法步骤画出它的程序框图以及相应的程序语句吗?,探究二,更相减损术,“可半者半之,不可半者,副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。”,同理：a,b,c为正整数，若a-b=c，则（a,b）=(b,c)。

7、,“更相减损术”（也是求两个正整数的最大公约数的算法）步骤：,第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。,第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。,例2、用更相减损术求98与63的最大公约数（自己按照步骤求解）,解：由于63不是偶数，把98和63以大数减小数，并辗转相减。,=7,所以，98和63的最大公约数等于7。,（98，63）=（63，35）,98-63=35,63-35=28,=（35，28）,35-28=7,=（28，7）,28-7

8、=21,=（21，7）,21-7=14,=（14，7）,14-7=7,=（7，7）,练习：用更相减损术求下列两数的最大公约数：（1）（225，135）（2）（98，196）（3）（72，168）（4）（153，119）,45,98,24,17,思考：更相减损直到何时结束？运用的是哪种算法结构？,更相减损是一个反复执行直到减数等于差时停止的步骤，这实际也是一个循环结构,讨论：你能根据更相减损术的算法步骤画出其程序框图并写出程序语句吗?,开始,输入：m,n,输出：m,结束,mn?,m=m-n,N,Y,Mn?,n=n-m,Y,N,INPUT m,nWHILE mn IF mn THEN m=m-n

9、ELSE n=n-m END IFWENDPRINT mEND,思考：辗转相除法与更相减损术有什么区别和联系？,区别：计算上辗转相除法以除法为主，更相减损术以减法为住；在计算次数上，辗转相除法计算次数相对较少，特别当两个数大小差别较大时计算次数的区别较明显；从结果输出的时候看，辗转相除法当余数为0时输出除数，更相减损术当差和减数相等时输出差。联系：都是求最大公约数的方法。因为做一次除法与做若干次减法效果相同，商就是减法的次数，余数就是最后的差，由此可知二者是完全统一的！,例3，求三个数319，377，116的最大公约数（计算，不编程）,辗转相除法,更相减损术,练习：,1，下列说法中正确的是（）

10、A 辗转相除法是中国古代数学中的算法B 更相减损术与辗转相除法的算理完全不同C 辗转相除法与更相减损术相比较，用辗转相除法求最大公约数最优越D 辗转相除法与更相减损术，在设计程序时，都要用到循环结构。,2，4830与3289的最大公约数为_3，用更相减损术求87与27的最大公约数时，反复相减，直至求出最大公约数，需要进行减法运算的次数是_4，用辗转相除法求87与27的最大公约数，需要进行除法运算的次数是_5，46，115，276的最大公约数是_,6，下面是求115与276的最大公约数的程序，把程序补充完整。a=115b=276DO r=_ a=b b=rLOOP UNTIL r=_PRINT

11、aEND,7，用辗转相除法求176与121的最大公约数，并写出其程序。8，用更相减损术求204与85的最大公约数，并写出其相应的程序。,探究三、秦九昭算法,思考1,在初中,我们是如何求一个多项式的值的?思考2,已知一个n 次多项式f(x)=anxn+an-1xn-1+a1x+a0当x=x0时，除了用代入法求解外是否还有更好的方法呢？,探究：以f(x)=a5x5+a4x4+a1x+a0为例,秦九昭算法问题：秦九昭（约12021261）是我国南宋时期享誉世界的数学家，在他的代表作数学九章中介绍了计算一个n次多项式值的算法，即“秦九昭算法”。它的特点是：通过一次式的反复计算，逐步得出高次多项式的值，

12、对于一个n次多项式，只需做n次乘法和n次加法即可。秦九昭算法是求一元多项式值的一种方法，现在它仍是世界上多项式求值最先进的方法，这一成就比西方同样的算法早五六百年，且该算法很容易在计算机上实现！,例题,例1，已知一个5次多项式为f(x)=4x5+2x4+3.5x3-2.6x2+1.7x-0.8用秦九昭算法求这个多项式当x=5时的值练习：用秦九昭算法计算多项式f(x)=2x4+3x3+5x-4当x=2时的函数值,探究、秦九昭算法分析,阅读书本P38-39思考：通过阅读秦九昭算法分析，你能说一说它有什么优点吗？减少了乘法的运算次数，提高了工作效率 易于计算机操作，提高了计算机的精确度,练习,1，用

13、秦九昭算法求多项式f(x)=x4+2x3+3x2+x+1,当x=2时的值时，第一次运算的步骤是（）A 12 B 24 C 2+2 D 12+22，用秦九昭算法求多项式f(x)=a3x3+a2x2+a1x+a0,当x=x0时的值最多要做_次乘法运算，_次加法运算。3，用秦九昭算法，求f(x)=3x5-2x3+2x2-1当x=2时的值。,5，用秦九昭算法计算多项式f(x)=12+35x-8x2+79x3+6x4+5x5+3x6在x=-4时的值时，v3的值为（）A-845 B 220 C-57 D 346，已知函数f(x)=x4-2x2-5x+6,用秦九昭算法求f（10）的值,探究四、进位制,情境创

14、设古时候，当边境有敌人来犯时，守边的官兵通过在烽火台上点火向国内报告，如图：烽火台上点火表示数字1，不点火表示数字0，约定二进制数对应的十进制数的单位是1000，请你计算一下，这组烽火台表示有多少敌人入侵？,这个问题中，提高了二进制的概念，那么什么是二进制呢？它与我们常用的十进制有什么关系呢？它们之间是否可以互相转化呢？请带着以上问题阅读书P40,探究一、进位制的概念,思考1，我们在学习过程中所处理的数据一般都是几进制的，你能说说它有什么规律吗？你还能举出哪些有关进位制的例子？谈谈你对进位制的认识！进位制是人们为了计算和运算方便而约定的记数系统，约定满二进一，就是二进制；满十进一，就是十进制等

15、。即“满几进一”就是几进制，几进制的基数就是几。,探究二、进位制之间的转换,思考1：根据十进制的表示方法，你能把k进制的数转化为十进制吗？例1，把二进制数101011（2）转化为十进制数例2，把五进制数10243（5）转化为十进制数思考2：通过上面的学习，已经知道如何将k进制数转化为十进制数，对于情境创设中的问题你能解决吗？思考3：根据例题，怎样改进算法让计算机来执行呢？（把k进制数a（共有n位）化为十进制数b）,思考4：怎样把十进制数转化为其他非十进制数呢？,例1把89转化为二进制数例2，把3147转化为八进制数思考5：你能根据上面的举例设计出把一个十进制的数转化为k进制数的算法吗？除k取余

16、法思考6：对于非十进制数之间如何进行转换呢？,练习,1，以下各数可能是七进制数的是（）A 7601 B 2138 C 2008 D 16322，将数30012（4）转化为十进制数为（）A 524 B 774 C 256 D 2603，把十进制数15转化为二进制数为_4，把11011011（2）转换为十进制数5，把67转化为二进制数6，二进制数算式1010（2）+10（2）的值是_,7，完成下列进位制之间的转化：（1）314（5）=_（10）=_(7)（2）325(6)=_(2)8，将四个数111111（2），210（6），1000（4），71（8），按从小到大排列为_9，把10110（4）转化为十进制数10，已知175（k）=125，求k的值,