高中必修三算法案例

算法案例一、辗转相除法（求正整数最大公约数算法）1、设两数为a、b(ab)，求a和b最大公约数(a，b)的步骤如下：用a除以b，得a÷b=q......r1(0≤r1)。若r1=0，则(a，b)=b；若r1≠0，则再用b除以r1，得b÷r1=q......r2(0≤r2）.若r2=0，则(a，b)=r1，若r2≠0，则继续用r1除以r2，……如此下去，直到能整除为止。其最后一个为被除数的余数的除数即为(a,b)。程序框图表示例如：a=25,b=15，a/b=1......10,b/10=1......5,10/5=2.......0,最后一个为被除数余数的除数就是5,5就是所求最大公约数。2、求三个或三个以上数的最大公约数，可以先求前两个数的最大公约数，再求所得公约数与第三个数的最大公约数，最后求的最大公约数就是这三个数字的最大公约数。例：求三个数324，243，135的最大公约数。解：辗转相除法：∵324=243×1+81，243=81×3+0，∴324与243的最大公约数为81，又135=81×1+54，81=54×1+27，54=27×2+0，∴81与135的最大公约数为27，∴三个数324，243，135的最大公约数为27。二、更相减损术（求正整数最大公约数算法）第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。则第一步中约掉的若干个2与第二步中等数（最大公约数）的乘积就是所求的最大公约数。例：用更相减损术求98与63的最大公约数解：由于63不是偶数，把98和63以大数减小数，并辗转相减：98-63=3563-35=2835-28=728-7=2121-7=1414-7=7所以，98和63的最大公约数等于7。三、秦九韶算法（多项式化简算法）一般地，一元n次多项式的求值需要经过[n（n+1）]/2次乘法和n次加法，而秦九韶算法只需要n次乘法和n次加法。在人工计算时，一次大大简化了运算过程。把一个n次多项式改写成如下形式：求多项式的值时，首先计算最内层括号内一次多项式的值，即然后由内向外逐层计算一次多项式的值，即这样，求n次多项式f(x)的值就转化为求n个一次多项式的值。程序框图：例：用秦九韶算法求出当X=5时多项式结果四、进位制1、概念：进位制也就是进制，是人们规定的一种进位方法。对于任何一种进制---X进制，就表示某一位置上的数运算时是逢X进一位。十进制是逢十进一，十六进制是逢十六进一，二进制就是逢二进一，以此类推，x进制就是逢x进位。2、进位制的性质：⑴在k进制中，具有k个数字符号，它们是0,1,2，···，（k-1）；⑵在k进制中，由低位到高位是按“满k进一”的规则进行计数的；⑶不同进位制都是按位置原则计数的3、进位转化⑴将十进制数转化为k进制数第一步：将给定的十进制整数除以基数k.余数便是所求k进制的最低位；第二步：将上一步的商再除以基数k，余数便是所求k进制数的次低位；第三步：重复第二步，直到所得的商为0，将每步的余数依次从右到左排列，便是k进制各位上的数，最后一步的余数是最高位。例：将2013转化为8进制数解：2013÷8=251······5251÷8=31······331÷8=3······73÷8=0······3则3735（8）即为2018的八进制数⑵将k进制数转化为十进制数第一步：把k进制数写成不同数位上的数字与k的幂的乘积之和形式；第二步：按十进制的运算规则算出结果例：将127（8）转化为十进制数。解：127（8）=7×80+2×81+1×82=87故答案为87分析：把8进制数字转化成十进制数字，用所给的数字最后一个数乘以8的0次方，依次向前类推，相加得到十进制数字。