算法案例—辗转相除、更相减损、秦九韶

算法案例（讲义）➢ 知识点睛典型算法举例： 1. 辗转相除法①方法概述：两数相除，较大数除以较小数，得商和余数，继而较小数除以余数，重复操作，直至除尽，此时除数即为最大公约数．②原理：在a =bq +r 中，除数b 和余数r 能被同一个数整除，那么被除数a 也能被这个数整除．或者说，除数与余数的最大公约数，就是被除数与除数的最大公约数． 2. 秦九韶算法把一个n 次多项式改写成如下形式：1110121102312101210()()(())((()))n n n n n n n n n n n n n n n f x a x a x a x a a x a x a x a a x a x a x a x a a x a x a x a x a ----------=++++=++++=+++++==+++++……………… 记0n v a =，11n n v a x a -=+，…，10n n v v x a -=+．求多项式的值时，首先计算最内层括号内一次多项式的值，即v 1，然后由内向外逐层计算． 3. 进位制①k 进制：若k 是一个大于1的整数，那么以k 为基数的k 进制数可以表示为一串数字连写在一起的形式．110()n n k a a a a -…11011000n n n n a a a a N a k a a a k --∈<<<≤（，，…，，，，，…，，）②进位制数相互转化：k 进制转十进制，计算k 进制数a 的右数第i 位数字i a 与1i k -的乘积1i i a k -⋅，再将其累加，重复操作求和．十进制数转k 进制数（除k 取余法）： 如右图，十进制数化为二进制数， 89=1011001（2）．➢ 精讲精练1. 用“辗转相除法”求下列数的最大公约数：（1）459和357的最大公约数是____________；余数2222222012511224489（2）三个数324243135，，的最大公约数是____________．2. 用秦九韶算法求多项式的值：（1）计算多项式x x x x x x x f 876543)(23456+++++=在1.0=x 时的值时，需要做乘法和加法的次数分别是_______，_______；（2）求多项式23456()1235879653f x x x x x x x =+-++++在x =-4的值时，4v 的值为_______；（3）计算多项式5432()853261f x x x x x x =+++++，当2x =时的值为________． 3. 完成下列进制的转化：(3)(10)10202____=； (10)__________(8)101=；1231(5)=_____________(7)．4. 三位七进制的数表示的最大的十进制的数是（ ）A ．322B ．402C ．342D ．3655. 在下列各数中，最小的数是（ ）A ．)9(85B ．)6(210C ．)4(1000D ．(2)1111116. 已知三个数12(16)，25(7)，33(4)，按照从小到大的顺序排列为________________．7. 已知()175r =(10)125，则r =________．8. 如图所示的程序框图的算法思路来源于我国古代数学名著《九章算术》中的“更相减损术”，执行该程序框图，若输入的a ，b 的值分别为14，18，则输出的a 的值为（ ） A ．0B ．2C ．4D ．149. 如图所示的程序框图给出了利用秦九韶算法求多项式值的一个实例，若输入n ，x 的值分别为3，2，则输出v 的值为（ ） A ．35B ．20C ．18D ．910.下面是把二进制数(2)11111化为十进制数的一个程序框图，判断框内应填入的条件是（）A．5i>？B．4i≤？C．4i>？D．5i≤？11.执行如图所示的程序框图后，输出的值为4，则P的取值范围是（）A．715816P<≤B．1516P>C．3748P<≤D．715816P<≤12.设a是一个各位数字都不是0且没有重复数字的三位数．将组成a的3个数字按从小到大排成的三位数记为I(a)，按从大到小排成的三位数记为D(a)（例如a=815，则I(a)=158，D(a)=851）．阅读如图所示的程序框图，运行相应的程序，任意输入一个a，输出的结果b=________．13. 已知函数232 1 01 012 1x x y x x x x x -<⎧⎪=+<⎨⎪+⎩≤≥（）（）（），写出求该函数的函数值的算法，并画出程序框图．14. 设计一算法，求使20063212222>++++n Λ成立的最小正整数n 的值.15.设计算法计算：1112131415167S=++++++，画出程序框图．【参考答案】1. （1）51；（2）272. （1）6；5；（2）220；（3）3813. 101 145 3624. C5. D6. (4)(16)(7)331225<<7. 88. B9. C 10. C 11. C 12. 495 13. 略 14. 略 15. 略算法案例（随堂测试）1. 372和684的最大公约数是（ ）A ．36B ．186C ．12D ．5892. 用秦九韶算法计算多项式65432()3567983512f x x x x x x x =+++-++在x =-4时的值时，v 2的值为（ ）A ．-57B ．-22C ．34D ．743. 1234（8）=________（10）；300=________（5）；300=_______（6）．4. 设计一个算法，输入正整数n ，输出111123n++++…．【参考答案】1. C2. C3. 668；2 200；1 2204. 略算法案例（习题）➢ 巩固练习5. 求下列数的最大公约数：（1）1 443与999的最大公约数是_____________；（2）319，377，116的最大公约数是___________．6. 用秦九韶算法求n 次多项式1110()n n n n f x a x a x a x a --=++++…，当x =x 0时，0()f x 需要算乘法、加法的次数分别为（ ） A ．n 2，nB ．2n ，nC ．n ，2nD ．n ，n7.已知532=++++，运用秦九韶算法计算x=3时的值时，v3的值为（）()231f x x x x xA．27 B．11 C．109 D．368.用秦九韶算法求多项式765432=++++++在x=3时的值为________．()765432f x x x x x x x x9.把21化为二进制数，则此数为（）A．10011（2）B．10110（2）C．10101（2）D．11001（2）10.一个k进制的三位数与某六进制的二位数等值，则k不可能是（）A．3 B．4 C．5 D．711.下列各数中，最小的数是（）A．75B．210（6）C．111111（2）D．85（9）12.若a=33（10），b=52（6），c=11111（2），则三个数的大小关系是（）A．c＞b＞a B．b＞c＞a C．c＞a＞b D．a＞b＞c13.中国古代有计算多项式值的秦九韶算法，如图是实现该算法的程序框图．执行该程序框图，若输入的x=2，n=2，依次输入的a为2，2，5，则输出的s=（）A．7B．12C．17D．34第9题图第10题图14.如图是一个算法的程序框图，该算法所输出的结果是（）A．11112310++++…B．11113519++++…C．111124620++++…D．231011112222++++…15.某程序框图如图所示，若输出的S=57，则判断框内为（）A．k＞4？B．k＞5？C．k＞6？D．k＞7？11第11题图 第12题图16. 执行如图所示的程序框图，若输入k 的值为8，则判断框图可填入的条件是（ ）A ．S ≤34？B ．S ≤56？C ．S ≤1112？ D ．S ≤1524？17. 设计一个算法，输入两个数，输出两个数中较大的一个．18.已知函数21111131x x y x x x x ⎧-<-⎪=+-⎨⎪+>≤≤（）（）（），试画出求函数值的程序框图．19. 对任意给定的正整数n ，写出一个求13+23+33+…+n 3的算法程序框图．20.设计算法求111112233499100++++⨯⨯⨯⨯…的值，要求画出程序框图．【参考答案】1.（1）111 （2）292.D3.D4.213245.C6.D7.C8.D9.C10.C11.A12.C13.略14.略15.略16.略12。

二、更相减损术
1、背景介绍： （1）、《九章算术》中的更相减损术： 可半者半之，不可半者，副置分母、子之数，以少 减多，更相减损，求其等也，以等数约之。
（2）、现代数学中的更相减损术：
第一步：任意给定两个正整数；判断他们是否都是 偶数。若是，则用2约简；若不是则执行第二步。 第二步：以较大的数减较小的数，接着把所得的差 与较小的数比较，并以大数减小数。继续这个操作， 直到所得的减数和差相等为止，则这个等数就是所 求的最大公约数。
v1=anx+an-1,
v2=v1x+an-2,
v3=v2x+an-3, ……, vn=vn-1x+a0.
观察上述秦九韶算法中的n个一次式,可见 vk的计算要用到vk-1的值. 若令v0=an,得 v0=an, vK=vK-1x+an-k(k=1,2,……,n 这是一个在秦九韶算法中反复执行的步 骤,因此可用循环结构来实现. [问题]画出程序框图,表示用秦九韶算法求5次多 项式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0当x=x0 (x0是任意实数)时的值的过程,然后写出程序.
第一章 算法初步
1.3.1 算法案例(一)—辗转 相除法与更相减损术
教学目标




1.理解辗转相除法与更相减损术中蕴含的数学原 理，并能根据这些原理进行算法分析； 2.能根据算法语句与程序框图的知识设计完整的 程序框图并写出算法程序. 教学重点 ：理解辗转相除法与更相减损术求最 大公约数的方法 教学难点 ：辗转相除法与更相减损术的方法转 换成程序框图与程序语言。
v2=v1x+an-2, v3=v2x+an-3, ……, vn=vn-1x+a0.

SCH 高中数学（南极数学）同步教学设计（人教A 版必修3第一单元《算法初步》） 班级 姓名 座号1 1．3（1）辗转相除法和更相减损术、秦九韶算法（学生学案） 例1：用辗转相除法求225与135的最大公约数? 例2（课本P36例1） 用更相减损术求98与63的最大公约数.例3（课本P38例2）已知一个5次多项式为8.07.16.25.324)(2345-+-++=x x x x x x f 用秦九韶算法求这个多项式当5=x 时的值.例4：阅读下列程序，说明它解决的实际问题是什么？求多项式 ()12345234++++=x x x x x f 在x=a时的值.【课时作业】1．4 830与3 289的最大公约数为( )A ．23B ．35C ．11D ．132．用秦九韶算法求多项式f (x )＝4x 5－x 2＋2当x ＝3的值时，需要进行的乘法运算和加减运算的次数分别为( )A ．4,2B ．5,3C ．5,2D ．6,23．用辗转相除法求72与120的最大公约数时，需要做除法次数为( )A ．4B ．3C ．5D ．64．用更相减损术求459与357的最大公约数，需要做减法的次数为( )A ．4B ．5C ．6D ．75．用秦九韶算法求多项式f (x )＝1＋2x ＋x 2－3x 3＋2x 4在x ＝－1时的值，v 2的结果是( )A ．－4B ．－1C ．5D ．66．用更相减损术求三个数168,54,264的最大公约数为________．7．用辗转相除法求294和84的最大公约数时，需要做除法的次数是________．8．按照秦九韶算法求多项式f (x )＝1.5x ＋3.5x －4.1x －3.6x ＋6当x ＝0.5时的值的过程中，令v 0＝a 5，v 1＝v 0x＋a 4，…，v 5＝v 4x ＋a 0，则v 4＝________.INPUT “x=”；an=0y=0WHLE n<5y=y+(n+1)*a ∧nn=n+1WENDPRINT yEND。

思考1 已f(知 x)5x54x43x32x2 x1 ,求 f(5). 算法1： 需要(5+4+3+2)=14次乘法，5次加法
秦九韶算法
2021/8/6
7
知识探究(一):秦九韶算法的基本思想
思考1 已f(知 x)5x54x43x32x2
x1 ,求 f(5).
18556
算法1：
需要(5+4+3+2)=14次乘法，5次加法
算法2： 秦九韶算法 需要5次乘法，5次加法
2021/8/6
8
知识探究(一):秦九韶算法的基本思想
思考1 已f(知 x)5x54x43x32x2
x1 ,求 f(5).
18556
算法1：
需要(5+4+3+2)=14次乘法，5次加法
算法2： 秦九韶算法 需要5次乘法，5次加法
思考2 已f(知 x)7x76x65x54x4 3x32x2x1,求 f(3).
18
一般地,对于一个n次多项式 f(x)=anxn+an-1xn-1+an-2xn-2+……+a1x+a0. 我们可以改写成如下形式:
f(x)=(…(anx+an-1)x+an-2)x+…+a1)x+a0. 求多项式的值时,首先计算最内层括号内一 次多项式的值逐层计算一次多项式的值,即
v2=v1x+an-2, v3=v2x+an-3, ……, vn=vn-1x+a0.
这样,求n次多项式f(x)的值就转化为求n个 一次多项式的值.这种算法称为秦九韶算法.
2021/8/6
19
点评:秦九韶算法是求一元多项式的 值的一种方法.