(程序框图案例.docVIP

算法案例 (一)辗转相除法与更相减损术 1.短除法 求两个正整数的最大公约数的步骤:先用两个数公有的质因数连续去除,一直除到所有的商是两个互质的数为止,然后把所有的处暑连乘起来. 2.穷举法(也叫枚举法) 穷举法求两个正整数的最大公约数的解题步骤:从两个较小的数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数. 3.辗转相除法 (1)辗转相除法:该算法又称欧几里得算法,就是对于给定的两个正整数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成一对新数,继续上面的除法,直到余数为零,此时处暑就是所求两正整数的最大公约数. (2)算法步骤:以求正整数的最大公约数为例. 第一步,输入两个正整数. 第二步,判断的大小,让表示较大的数,表示较小的数. 第三步,计算除以的余数. 第四步,让. 第五步,如果,则的最大公约数等于;否则返回第三步. (3)辗转相除法的程序框图及程序 程序框图： 程序： INPUT “m=”;m INPUT “n=”;n IF mn THEN x=m m=n n=x END IF r=m MOD n WHILE r0 r=m MOD n m=n n=r WEND PRINT n END (4)程序1为: INPUT “m,n=”;m,n IF mn THEN t=m m=n n=t END IF DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END 程序2为: INPUT “m,n=”;m,n IF mn THEN t=m m=n n=t END IF r=1 WHILE r0 r=m MOD n m=n n=r WEND PRINT m END 4.更项减损术 (1)更项减损术:我国早期也有解决求最大公约数问题的算法,就是更相减损术.《九章算术》是中国古代的数学专著,其中的“更相减损术”也可以来用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子子之数,以少减多,更相减损,求其等也.以等数约之.” (2)算法步骤: 第一步,任意给定两个正整数,判断它们是否都是偶数,若是,用约简之;若不是,执行第二步. 第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减去小数,继续这个操作,直到所得的数相等为止.则这个数(等数)或这个数与约简数的乘积就是所求的最大公约数. (3)程序框图为:略 (4)程序为: INPUT “m,n=”;m,n IF mn THEN t=m m=n n=t END IF k=0 WHILE (m MOD 2=0) AND (n MOD 2=0) m=m/2 n=n/2 k=k+1 WEND d=m-n WHILE dn IF dn THEN m=d ELSE m=n n=d END IF d=m-n WEND d=2^k*d PRINT d END (二)秦九韶算法 1.怎么求多项式当时的值? 一个自然的做法是把代入多项式,急速各项的值,然后把它们加起来,这时,我们一共做了次乘法运算,次加法运算. 另一种算法是先计算的值,然后计算的值,这样每次都可以利用上一次计算的结构,这时,我们一共做了次乘法运算,次加法运算. 第二种做法与第一种做法相比,乘法的运算此时减少了,因而能够提高运算效率,对于计算机来说,做一次乘法运算所用的时间比做一次加法运算要长得多,所以采用第二种算法,计算机能更快地得到结果. 2.求多项式的值时,常用秦九韶算法,这种算法的运算次数较少,是多项式求值比较先进的算法,其实质是转化为求个一次多项式的值,共进行次乘法运算和次加法运算. 3.秦九韶算法 (1)改写多项式: 设, , , .