(新课程中的现代数学算法拓展辅助材料.docVIP

新课程中的现代数学—算法的拓展 辅助学习材料 一、辗转相除法： 求最大公约数的方法就是辗转相除法．也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的．利用辗转相除法求最大公约数的步骤如下： 第一步：用较大的数除以较小的数得到一个商和一个余数； 第二步：若，则为的最大公约数；若，则用除数除以余数得到一个商和一个余数； 第三步：若，则为的最大公约数；若，则用除数除以余数得到一个商和一个余数； …… 依次计算直至，此时所得到的即为所求的最大公约数． 例1 用辗转相除法求8610和6300的最大公约数。 解 为了简洁，我们把8610和6300的最大公约数计作（8610，6300）。 8610 = 6300×1 + 2310 我们来看一下（8610，6300）和（6300，2310）之间的关系。 它们有相同的公约数，因此也有相同的最大公约数。难道这只是巧合吗？ 我们设k是8610和6300的一个公约数，则有 因为k是8610和2300的公约数，所以均为整数，所以为整数，所以k也是2310的公约数。因此，8610和6300的公约数是6300和2300的公约数，反过来，6300和2310的公约数也是8610和6300的公约数。 我们可以总结为： （被除数，除数）=（除数，余数） 据此，我们可以用如下办法求8610和6300的最大公约数： 被除数 除数 余数 （8610，6300） 8610 = 6300×1 + 2310 =（6105，2146） 6300 = 2310×2 + 1680 =（2146，1813） 2310 = 1680×1 + 630 =（1813，333） 1680 = 630×2 + 420 =（333，148） 由除法的性质可知，对于任意两个正整数，上述除法步骤总可以在有限步之后完成，从而总可以用辗转相除法求出最大公约数。 二、更相减损术 我国早期也有解决求最大公约数问题的算法，就是更相减损术． 更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母之数，以少减多，更相减损，求其等也，以等数约之．翻译出来为： 第一步：任意给出两个正数；判断它们是否都是偶数．若是，用2约简；若不是，执行第二步． 第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数． 程序语句如下： 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 例2 用更相减损术球98与63的最大公约数。 解 98-63=35 63-34=28 35-28=7 28- 7=21 21- 7=14 14- 7=7 所以98和63的最大公约数等于7。 三、秦九韶算法 应用秦九韶算法完成一般的多项式求值问题 ， 然后由内向外逐层计算一次多项式的值，即 时要用到的值，若令，我们可以得到下面的递推公式： 这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现。 若直接计算一般的多项式的求值问题。直接法乘法运算的次数最多可到达，加法最多n次。秦九韶算法通过转化把乘法运算的次数减少到最多n次，加法最多n次。 例3已知多项式函数f(x)=2x5－5x4－4x3+3x2－6x+7x=5时的函数的值。 解 把多项式变形为：f(x)= 2x5－5x4－4x3+3x2－6x+7 =((((2x－5)x－4)x+3)x－6)x+7 x系数 2 －5 －4 3 －6 7 运算 运算所得的值 10 25 105 540 2670 + 变形后x的系数 2 5 21 108 534 2677 *5 最后的系数2677即为所求的值。 算法过程： v0=2 v1=2×5－5=5 v2=5×5－4=21 v3=21×5+3=108 v4=108×5－6=534 v5=534×5+7=2677 请注意，如果多项式函数中有缺项的话，要以系数为0的项补齐后再计算。 四、进位制 进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制。现在最常用的是十进制，通常使用10个阿