2020版高中数学第一章算法初步13算法案例第1课时1辗转相除法与更相减损术秦九韶算法课件新人教A版必修3

1、1.3 第第1课时课时 辗转相除法与辗转相除法与 更相减损术、秦九韶算法更相减损术、秦九韶算法 课前热身 1.辗转相除法是用于求_的一种方法，这 种算法由欧几里得在公元前300年左右首先提出的，因而又叫 _ 2所谓辗转相除法，就是对于给定的两个正整数，用_ 除以_，若余数不为零，则将_构成新的一对数， 继续上面的除法，直到大数被小数除尽，则这时_就是 原来两个数的最大公约数 3 更相减损术是我国古代数学专著_中介绍的一种求两数最大公约数的方法其基本过程是：对于给定的两个正整数，用_，接着把所得的_与_比较，并以大数减小数，继续这个操作，直到差与减数_为止，则这个数就是所求的最大公约数 4秦九韶

2、算法是我国南宋数学家_在他的代表作_中提出的一种用于计算一元 n 次多项式的值的方法. 自1.两个正整数的最大公约数 欧几里得算法 我2.较大的数 较小的数 除数与余数 除数 校3.九章算术 大数减小数 差 减数 相等 对 4.秦九韶 数书九章 名师讲解 1.辗转相除法 设m，n是两个正整数(不妨设mn)，用m除以n，若商为q1， 余数为r1(0 r1n)，则mnq1r1，显然若x是m和n的公约数， 即x能整除m和n， 则x也必然能整除r1， 这样x也是n和r1的公约数，故求m和n的公约数就是求n和r1的公约数；同理，用n除以r1， 得nr1q2r2(0 r2r1)， 所以n和r1的公约数就是

3、r1和r2的公约数，依次下去，由于mnr1r2，所以 到某一步必然有riri1qi2，即ri恰能被ri1整除，这时ri1是ri和ri1的公约数，它也必然是ri1和ri，ri2和ri1，r1与r2，n和r1，m和n的最大公约数 2更相减损术 对于给定的两个正整数(不都是偶数)，用较大的数减去较小的数，接着把得到的差与较小的数比较，用这时两个数中的较大的数减去较小的数，继续这样的操作(大数减小数)，直到所得的数相等为止，那么这个数(等数)就是所求的最大公约数 显然，上述过程中大数减去小数是一个重复执行的过程，因此只需将大数赋给变量m，小数赋给变量n，那么mn就可以通过循环结构实现算法 更相减损术求

4、最大公约数的程序设计： INPUT “a，b”；a，bWHILE ab IF ab THENaab ELSE bba END IFWENDPRINT aEND 3秦九韶算法 (1)秦九韶算法过程分析： 设Pn(x)anx an1xPn(x)(anx (anxn2n1nn1a1xa0，将其改写为 an1xn2a1)xa0 an1xn3a2)xa1)xa0 (anxan1)xan2)xa1)xa0 令v0an，则有公式 ?v0an，?vkvk1xank， 其中k1,2，n. 这样我们便可由v0依次求出v1，v2，vn： v1v0 xan1，v2v1xan2，v3v2xan3， vnvn1xa0.

5、显然，用秦九韶算法求n次多项式的值时只需做n次乘法和n次加法运算 (2)秦九韶算法程序框图： 以5次多项式f(x)a5x a4x a3x a2x a1xa0当xx0时为例，如图 5432 一 求两个数的最大公约数 【例1】 分别用辗转相除法和更相减损术逐步列出求 (1)98和63； (2)8 251和6 105的最大公约数的步骤，你有什么发现？对 优劣作出评判 【分析】 辗转相除法是做两个数的带余除法，更相减损术是做两个数的减法 解：(1)求98和63的最大公约数的步骤： 辗转相除法 S1 9863 135， S2 6335 128， S3 352817， S4 284 7， 所以，98和63

6、的最大公约数为7. 更相减损术 S1 986335， S2 633528， S3 35287， S4 28721， S5 21714， S6 1477， 故98和63的最大公约数为7. (2)求8 251和6 105的最大公约数的步骤： 辗转相除法 S1 8 2516 10512 146， S2 6 1052 14621 813， S3 2 1461 8131333， S4 1 8133335148， S5 333148237， S6 148374， 所以，8 251和6 105的最大公约数为37. 更相减损术 S1 8 2516 1052 146， S2 6 1052 1463 959， S

7、3 3 9592 1461 813， S4 2 1461 813333， S5 1 8133331 480， S6 1 4803331 147， S7 1 147333814， S8 814333481， S9 481333148， S10 333148185， S11 18514837， S12 14837111， S13 1113774， S14 743737， 所以，8 251和6 105的最大公约数为37. 辗转相除法和更相减损术本质是一致的，除法运算若用加法与减法运算定义，x(x0)除以y(y0)就是从x中一次又一次 地减去y，直至xy为止所减的次数即为商，所减的余数就是所求余数 因

8、此(1)中，S4 284 7，可作四次减法，即28中可减4 次7. (2)中，S4 1 8133335148，在1 813中可减5次333. 从形式上看更相减损术比辗转相除法复杂， 但计算机更“ 喜欢” 做加减法，加减法比乘除法快几百倍. 二 求三个数的最大公约数 【例2】 求三个数175、100、75的最大公约数 【分析】 求三个数的最大公约数时，可以先求出其中两个数的最大公约数，用这个最大公约数再与第三个数求最大公约数，所得结果就是这三个数的最大公约数 解： 解法1：(辗转相除法)： 先求175与100的最大公约数： 175100175， 10075125， 75253. 175与100的

9、最大公约数是25， 再求25与75的最大公约数： 75253 25和75的最大公约数是25. 故25是75和25的最大公约数，也就是175、100、75的最大公约数 解法2：(更相减损术)： 第一步，先从较大数中减去较小的数： 17510075,1007525，得75,25,75； 第二步，重复上面的算法：7525225,752 2525，得25,25,25， 25,25,25的最大公约数为25. 三个数175,100,75的最大公约数为25. 三 秦九韶算法的应用 【例3】 用秦九韶算法求多项式f(x)1x0.5 x 0.166 67x 0.041 67x0.008 33x在x0.2的值 【

10、分析】 可根据秦九韶算法原理，将所给多项式改写，然后由内到外逐次计算即可 2345解：f(x)1x0.5 x0.166 67x0.041 67x0.008 33x (0.008 33x0.041 67)x0.166 67)x0.5) x1) x1. 而x0.2，所以有v0a50.008 33， v1v0 xa40.040 00， v2v1xa30.158 67，v3v2xa20.468 27， v4v3xa10.906 35，v5v4xa00.818 73. 即f(0.2)0.818 73. 2345随堂训练 1.用辗转相除法计算60与48的最大公约数时，需要做的除法次数是( ) A1 B2

11、C3 D4 【解析】 6048112,481240， 仅需要两步运算 【答案】 B 2利用秦九韶算法计算函数f(x)x2 x 3 x4 x5 x2345 当xx0时的值时，需要做加法、乘法的次数分别为_、_. 【解析】将函数变形为 f(x)(5 x4)x3)x2) x1) x. 由此可知，共需要做4次加法，5次乘法 【答案】 4 5 3 用秦九韶算法计算f(x)3 x 2 xx4， 当x10时的值的过程中，v1的值为_ 42【解析】 v1v0 xa43 10030. 【答案】 30 4用辗转相除法求80和36的最大公约数，并用更相减损术检验所得结果 解：用辗转相除法：803628， 368 44， 84 20. 故80和36的最大公约数是4. 用更相减损术检验：803644， 44368， 36828， 28820， 20812， 1284， 844. 80和36的最大公约数是4. 5已知f(x)x 4 x2 x5 x1，求f(3