课时辗转相除法与更减损术算法.pptx

1.3算法案例

第1课时辗转相除法与更相减损术、秦九韶算法;1.通过辗转相除法与更相减损术、秦九韶算法的学习,进一步体会算法思想;

2.通过古代著名的算法,理解掌握辗转相除法与更相减损术、秦九韶算法的含义;(重点)

3.了解其计算过程;(重点)

4.了解其算法程序框图和程序．(难点);1.回顾算法的三种表述：

自然语言

程序框图（三种逻辑结构）

程序语言（五种基本语句）;2.小学学过的求两个数最大公约数的方法.

先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.;辗转相除法（欧几里得算法）;第二步,对6105和2146重复第一步的做法，

6105=2146×2，

同理6105和2146的最大公约数也是2146和1813的最大公约数.;完整的过程:;

所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数.若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数.;（2）算法步骤

第一步,输入两个正整数m,n(mn).

第二步,计算m除以n所得的余数r.

第三步,m=n,n=r.

第四步,若r＝0,则m,n的最大公约数等于m；否则转到第二步.

第五步,输出最大公约数m.;（3）程序框图;更相减损术

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

第一步：任意给定两个正整数，判断它们是否都是偶数.若是，则用2约简；若不是则执行第二步.

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数（等数）或其与约简的数的乘积就是所求的最大公约数.;更相减损术

（1）算理：所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤，直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数.;（2）算法步骤

第一步,输入两个正整数a,b(ab);

第二步,若a不等于b,则执行第三步；否则转到第五步；

第三步,把a-b的差赋予r;

第四步,如果br,那么把b赋给a,把r赋给b;否则把r赋给a，执行第二步；

第五步,输出最大公约数b.;（3）程序框图;（4）程序;例1用更相减损术求98与63的最大公约数.

解：由于63不是偶数，把98和63以大数减小数，并辗转相减,

98－63＝35

63－35＝28

35－28＝7

28－7＝21

21－7＝14

14－7＝7

所以，98和63的最大公约数等于7.;秦九韶算法的基本思想

对于求n次多项式的值，在我国古代数学中有一个优秀算法，即秦九韶算法，我们将对这个算法作些了解和探究.

思考1:对于多项式f(x)=x5+x4+x3+x2+x+1，求f(5)的值.若先计算各项的值，然后再相加，那么一共要做多少次乘法运算和多少次加法运算？

4+3+2+1=10次乘法运算，5次加法运算.;思考2:在上述问题中，若先计算x2的值，然后依次计算x2·x，(x2·x)·x，((x2·x)·x)·x的值，这样每次都可以利用上一次计算的结果，再将这些数与x和1相加，那么一共做了多少次乘法运算和多少次加法运算？

4次乘法运算，5次加法运算.;思考3:利用后一种算法求多项式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.;思考4:对于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.;思考5:上述求多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值的方法称为秦九韶算法，利用该算法求f(x0)的值，一共需要多少次乘法运算，多少次加法运算？

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

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

思考1:用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法？其算法步骤如何设计？

第一步:输入多项式的次数n，最高次项的系数an和x的值.

第二步:令v=