算法案例(完整版)

必修3-1.3算法案例算法案例（一）辗转相除法&更相减损术知识回顾思考：（1）57与120的最大公约数是多少？你是怎样得到的？你的方法可以一般化吗？（2）8251与6105的最大公因数呢？

知识回顾旧方法：先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数.有没有什么新方法？对8251与6105这两个数：进行以下步骤2146÷1813=1…333，148÷37=4…0.333÷148=2…37，1813÷333=5…148，6105÷2146=2…1813，8251÷6105=1…214637为8251与6105的最大公因数！上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？

第一步，给定两个正整数m，n(m>n).第二步，计算m除以n所得的余数r.第三步，m=n，n=r.第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步.

思考:该算法的程序框图如何表示？开始输入m，n求m除以n的余数rm=nn=rr=0？是输出m结束否知识:更相减损术

思考1:求98与63的最大公约数为多少？98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，“更相减损术”在中国古代数学专著《九章算术》中记述为：

可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之.

例1分别用辗转相除法和更相减损术求168与93的最大公约数.辗转相除法：168=93×1+75， 93=75×1+18， 75=18×4+3， 18=3×6.更相减损术:168-93=75，93-75=18，75-18=57，57-18=39，39-18=21，21-18=3，18-3=15，15-3=12，12-3=9，9-3=6，6-3=3.例2.求325，130，270三数的最大公约数

因为325=130×2+65，130=65×2，所以325与130的最大公约数是65.

因为270=65×4+10，65=10×6+5，10=5×2，所以65与270最大公约数是5.故325，130，270三个数的最大公约数是5.1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数.

小结小结2.更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.算法案例2秦九韶算法思考:对于多项式f(x)=x5+x4+x3+x2+x+1，求f(5)的值.若先计算各项的值，然后再相加，那么一共要做多少次乘法运算和多少次加法运算？4+3+2+1=10次乘法运算，5次加法运算.思考:利用后一种算法求多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值，这个多项式应写成哪种形式？f(x)=anxn+an-1xn-1+…+a1x+a0=(anxn-1+an-1xn-2+…+a2x+a1)x+a0=((anxn-2+an-1xn-3+…+a2)x+a1)x+a0=…=(…((anx+an-1)x+an-2)x+…+a1)x+a0.思考:在上述问题中，若先计算x2的值，然后依次计算x2·x，(x2·x)·x，((x2·x)·x)·x的值，这样每次都可以利用上一次计算的结果，再将这些数与x和1相加，那么一共做了多少次乘法运算和多少次加法运算？

4次乘法运算，5次加法运算.思考:对于f(x)=(…((anx+an-1)x+an-2)x+…+a1)x+a0，由内向外逐层计算一次多项式的值，其算法步骤如何？

第一步，计算v1=anx+an-1.第二步，计算v2=v1x+an-2.第三步，计算v3=v2x+an-3.

…第n步，计算vn=vn-1x+a0.思考:上述求多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值的方法称为秦九韶算法，利用该算法求f(x0)的值，一共需要多少次乘法运算，多少次加法运算？

思考:在秦九韶算法中，记v0=an，那么第k步的算式是什么？

vk=vk-1x+an-k(k=1，2，…，n)秦九韶算法的程序设计

思考1:用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，输入多项式的次数n，最高次

项的系数an和x的值.

第二步，令v=an，i=n-1.

第三步，输入i次项的系数ai.第四步，v=vx+ai，i=i-1.第五步，判断i≥0是否成立.若是，则返回第

二步；否则，输出多项式的值v.思考2:该算法的程序框图如何表示？开始输入n，an，x的值v=anv=vx+ai输入aii≥0？i=n-1i=i-1结束是输出v否理论迁移

练习：用秦九韶算法求f(5)的值.f(x)=((((5x+2)x+3.5)x-2.6)x+1.7)x-0.8.v1=5×5+2=27；v2=27×5+3.5=138.5；v3=138.5×5-2.6=689.9；v4=689.9×5+1.7=3451.2；v5=3451.2×5-0.8=17255.2.所以f(5)==17255.2.算法案例3K进位制知识探究(一):进位制的概念

进位制是为了计数和运算方便而约定的记数系统。你知道生活中有哪些进位制吗？如逢十进一，就是十进制；每七天为一周，就是七进制；每十二个月为一年，就是十二进制；每六十秒为一分钟，每六十分钟为一个小时，就是六十进制；等等.一般地，“满k进一”就是k进制，其中k称为k进制的基数.问：k是一个什么范围内的数？

思考:十进制使用0～9十个数字，那么二进制、五进制、七进制分别需要使用哪些数字？

思考:在十进制中10表示十，

在二进制中10表示2.一般地，若k是一个大于1的整数，则以k为基数的k进制数可以表示为一串数字连写在一起的形式：

anan-1…a1a0(k).其中各个数位上的数字an，an-1，…，a1，a0的取值范围如何？意义是什么？思考:十进制数4528表示的数可以写成4×103+5×102+2×101+8×100，依此类比，二进制数110011（2）,八进制数7342（8）分别可以写成什么式子？

110011（2）=1×25+1×24+0×23+0×22+1×21+1×20

7342（8）=7×83+3×82+4×81+2×80.结论:一般地，如何将k进制数anan-1…a1a0(k)写成各数位上的数字与基数k的幂的乘积之和的形式？（十进制）思考:在二进制中，0+0，0+1，1+0，1+1值分别是多少？知识探究(二):k进制化十进制的算法

思考:二进制数110011（2）化为十进制数是什么数？

110011（2）=1×25+1×24+0×23+0×22+1×21+1×20=32+16+2+1=51.知识探究(二):k进制化十进制的算法

结论：二进制数右数第i位数字ai化为十进制数是

问题：运用以下循环结构，设计算法把二进制数

化为十进制数b？第二步，令b=0，i=1.第四步，判断i>n是否成立.若是，则输

出b的值；否则，返回第三步.第一步，输入a和n的值.第三步，

，i=i+1.同样地，把k进制数

化为十进制数b的算法和程序框图如何设计？第四步，判断i>n是否成立.

若是，则输出b的值；

否则，返回第三步.第一步，输入a，k和n的值.第二步，令b=0，i=1.第三步，

，i=i+1.程序框图：开始输入a，k，nb=0i=1把a的右数第i位数字赋给tb=b+t·ki-1i=i+1i>n?结束是输出b否

例1将下列各进制数化为十进制数.（1）10303（4）

；

（2）1234（5）.理论迁移10303（4）=1×44+3×42+3×40=307.1234（5）=1×53+2×52+3×51+4×50=194.

例2已知10b1（2）=a02（3）,求数字a，b的值.所以2b+9=9a+2，即9a-2b=7.10b1（2）=1×23+b×2+1=2b+9.a02（3）=a×32+2=9a+2.故a=1，b=1.1.k进制数使用0～（k-1）共k个数字，但左侧第一个数位上的数字（首位数字）不为0.

小

结2.用

表示k进制数，其中k称为基数，十进制数不标注基数.3.把k进制数化为十进制数的一般算式是：1.3算法案例4十进制数化为k进制数

问题提出1.“满几进一”就是几进制，k进制使用哪几个数字，k进制数化为十进制数的一般算式是什么？2.k进制数化十进制数的一般算式，可以构造算法，设计程序，通过计算机就能把任何一个k进制数化为十进制数.在实际应用中，我们还需要把任意一个十进制数化为k进制数的算法。知识探究(一):除k取余法二进制数101101（2）化为十进制数是什么数？十进制数89化为二进制数是什么数？101101（2）=25+23+22+1=45.89=2×（2×（2×（2×（2×2+1）+1）+0）+0）+1=1×26+0×25+1×24+1×23+0×22+0×21+1×20=1011001（2）.思考：上述化十进制数为二进制数的算法叫做除2取余法，转化过程有些复杂，观察下面的算式你有什么发现吗？

21222502112222442891001101余数思考3:上述方法也可以推广为把十进制数化为k进制数的算法，称为除k取余法，那么十进制数191化为五进制数是什么数？0515753851911321余数191=1231（5）若十进制数a除以2所得的商是q0，余r0，

即a=2·q0+r0；q0除以2所得的商是q1，余数是r1，

即q0=2·q1+r1；……qn-1除以2所得的商是0，余数是rn，

即qn-1=rn，那么十进制数a化为二进制数是什么数？a=rnrn-1…r1r0(2)知识探究(二):十进制化k进制的算法

思考1:根据上面的分析，将十进制数a化为二进制数的算法步骤如何设计？第四步，若q≠0，则a=q，返回第二步；

否则，输出全部余数r排列得到

的二进制数.第一步，输入十进制数a的值.第二步，求出a除以2所得的商q，余数r.第三步，把所得的余数依次从右到左排列.思考:利用除k取余