算法案例(基础)算法案例(础)基础).doc

算法案例 A 一、目标与策略 明确学习目标及主要的学习方法是提高学习效率的首要条件，要做到心中有数！ 学习目标：学习策略： 二、学习与应用 要点一、辗转相除法 也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的.利用辗转相除法求最大公约数的步骤如下： 第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0； 第二步：若r0=0，则n为m，n的最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1； 第三步：若r1=0，则r1为m，nr1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2； …… 依次计算直至rn=0，此时所得到的rn－1 程序： 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 要点诠释： 辗转相除法的基本步骤是用 的数除以 的数，考虑到算法中的赋值语句可以对同一变量多次赋值，我们可以把较大的数用变量m表示，把较小的数用变量n表示，这样式子就是一个反复执行的步骤，因此可以用 结构实现算法. 要点二、更相减损术 我国早期也有解决求最大公约数问题的算法，就是更相减损术. 更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之. 翻译出来为： 第一步：任意给出两个正整数；判断它们是否都是偶数.若是，用2约简；若不是，执行第二步. 第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数. 理论依据： 由，得与有相同的公约数 更相减损术一般算法： 第一步，输入两个正整数； 第二步，如果，则执行，否则转到； 第三步，将的值赋予； 第四步，若，则把赋予，把赋予，否则把赋予，重新执行； 第五步，输出最大公约数. 程序： INPUT “a=”，a INPUT “b=”，b WHILE ab IF a=b a=a-b; ELSE b=b-a WEND END PRINT b 或者 INPUT “请输入两个不相等的正整数”；a，b i=0 WHILE a MOD 2=0 AND b MOD 2=0 a=a/2 b=b/2 i=i+1 WEND DO IF ba THEN t=a a=b b=t END IF c=a－b a=b b=c LOOP UNTIL a=b PRINT a^i END 要点诠释： 用辗转相除法步骤较少，而更相减损术虽然有些步骤较长，但运算简单. 要点三、秦九韶计算多项式的方法 令，则有，其中.这样，我们便可由依次求出； 要点诠释： 显然，用秦九韶算法求n次多项式的值时只需要做n次乘法和n次加法运算 要点四、进位制 进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值.可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制.现在最常用的是十进制，通常使用10个阿拉伯数字0-9进行记数. 对于任何一个数，我们可以用不同的进位制来表示.比如：十进数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的. 表示各种进位制数一般在数字右下脚加注来表示,如111001(2)表示二进制数,34(5)表示5进制数. 1.k进制转换为十进制的方法： ，把k进制数a转化为十进制数b的算法程序为： INPUT “ a,k,n=”;a,k,n i=1 b=0 WHILE i=n t=GET a[i] b=b+t*k^(i-1) i=i+1 WEND PRINT b END 2.十进制转化为k进制数b的步骤为： 第一步，将给定的十进制整数除以基数k，余数便是等值的k进制的最 位； 第二步，将上一步的 再除以基数k，余数便是等值的k进制数的 位； 第三步，重复第二步，直到最后所得的商等于 为止，各次所得的余数，便是k进制各位的数，最后一次余数是最 位，即除k取余法. 要点诠释： 1.在k进制中，具有 个数字符号.如二进制有0，1k进制中，由低位向高位是按“逢 进一”的规则进行计数. 3.非k进制数之间的转化一般应先转化成十进制，再将这个十进制数转化为另一种进制的数，有的也可以相互转化. 类型一：辗转相除法与更相减损术 例1．用辗转相除法求下列两数的最大公约数，并且用更相减损术检