1.3 中国古代数学中的算法案例（一）课件（22张PPT）

课件22张PPT。1.3 中国古代数学中的算法案例（一）人教B版必修三研究如何求二个正整数的最大公约数。
你记得在小学里是如何求最大公约数吗？短除法。例如求18和30的最大公约数：所以，18与30的最大公约数是2×3=6。更相减损之术 以较大的数减去较小的数，接着把所得的差与较
小的数比较，并以大数减小数。继续这个操作，直
到它们相等为止，则这个“相等的数”就是所求的最
大公约数更相减损之术例如：求78和36的最大公约数。解：（78，36）（6，36）（42，36）（6，30）（6，18）（6，12）（6，24）（6，6）所以，78和36的最大公约数为6。更相减损之术理论依据：
在表达式 a－b=r 中，a、b、r三个数有
相同的约数，即 (a, b)与(b, r)有相同
的公约数.更相减损之术算法如下：S1 输入两个不相等的正整数m, n ；
S2 若m>n，将m－n的值赋予m；否则把n-m的值赋予n，
S3 若m=n输出m，n；否则执行S2这种算法也叫等值算法。更相减损之术m=input("m=");
n=input("n=");
while m<>n
if m>n
m=m-n;
else
n=n-m;
end
end
print(%io(2),m,n);辗转相除法
用较大的数除以较小的数所得的余数和较小的
数构成新的一对数；继续做上面的除法，直到
大数被小数除尽，这个较小的数就是最大公约
数.（欧几里得算法）辗转相除法例如：求288和123的最大公约数。解：（288，123）（42，39）（42，123）（3，39）所以，288和123的最大公约数为3。两种算法对比更相减损做减法运算，辗转相除做除法运算，相比较减法运算更简单；
辗转相除法迭代速度更快一些；
更相减损之术两数相等终止，辗转相除两数整除终止；
两种算法都是计算最大公约数的算法。
已知 求当 时的函数值，要用多少次乘法，多少次加法？ 乘法： 次
加法： 次乘法和加法的次数能减少吗？ 这种思想记述在我国南宋时期数学家秦九韶（约1202—1261）的代表作《数书九章》中，并总结了一套完整的算法，我们称之为秦九韶算法。直到今天这种算法仍是多项式求值比较先进的算法。105 用刚才的方法，计算 共用4次乘法，乘上它们的系数需要5次乘法，共需要9次乘法和5次加法。比如一个5次多项式为 求当 时的函数值，要用多少次乘法，多少次加法？ 用这种方法，计算共用5次乘法和5次加法。乘法运算次数再次减少。多项式的系数分别为：共用了5次乘法和5次加法，减少了4次乘法。秦九韶算法用于计算n次多项式的值。
特点是通过提取公因式的方法，减少运算过程中乘法运算的次数。
计算n次多项式的值至多需要n次乘法和n次加法。
利用秦九韶算法求多项式
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.对于多项式
f(x)=(…((anx+an-1)x+an-2)x+…+a1)x+a0，用秦九韶算法计算它的值，其算法步骤如何？ S1，v0=an
计算v1=anx+an-1. S2，计算v2=v1x+an-2.S3，计算v3=v2x+an-3.
…Sn，计算vn=vn-1x+a0.第k步的算式是什么呢？ vk=vk-1x+an-k
(k=1，2，…，n)秦九韶算法的算法设计 :S1，输入多项式的次数n，最高次项的系数an 和x的值. S2，令v=an，i=n-1. S3，输入i次项的系数ai. S4，v=vx+ai，i=i-1.S5，判断i≥0是否成立.若是，则返回S2 ；否则，输出多项式的值v. 秦九韶算法开始结束i=i-1 i=n-1输出v输入n，an，x输入ain=input("n=");
an=input("an=");
x=input("x=");
v=an;
i=n-1;
while i>=0
a=input("ai=");
v=v*x+a;i=i-1;
end
print(%io(2),v)课堂练习1．在秦九韶的算法中用到的一种方法是（ ）
A．消元 B．递推 C．回代 D．迭代2.在使用更相减损之术计算18和38的最大公约数时需要用到的减法次数是（ ）
A． 8 B. 9 C. 10 D. 11DCB课堂小结更相减损之术
辗转相除法
秦九韶算法课后作业课本第32页，习题1-3A，1，2，3，4
课本32页，习题1-3 B
谢谢