2019年数学湘教版必修5新设计同步（讲义）：第11章 11.4 算法案例

11．4算法案例
1．辗转相除法
用辗转相除法求两个正整数a，b(a>b)的最大公约数的算法步骤：
S1：输入两个正整数a，b；
S2：计算a除以b所得的余数r，即r＝a_MOD_b；
S3：a＝b，b＝r；
S4：判断r＝0是否成立，若成立，输出最大公约数a；
否则返回S2.
2．秦九韶算法
功能
它是一种用于计算一元n次多项式的值的方法
改写后的形式
f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0
＝(anxn－1＋an－1xn－2＋…＋a1)x＋a0
＝((anxn－2＋an－1xn－3＋…＋a2)x＋a1)x＋a0
＝…
＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0
计算方法
从括号最内层开始，由内向外逐层计算
v1＝anx＋an－1，
v2＝v1x＋an－2，
v3＝v2x＋an－3，
…
vn＝vn－1x＋a0，
这样，求n次多项式f(x)的值就转化为求n个一次多项式的值
辗转相除法与更相减损术有什么区别和联系？
提示：
名称
辗转相除法
更相减损术
区别
①以除法为主
②两个整数差值较大时运算次数较少
③相除余数为零时得结果
①以减法为主
②两个整数的差值较大时，运算次数较多
③相减，两数相等得结果
④相减前要做是否都是偶数的判断
联系
①都是求两个正整数的最大公约数的方法
②二者的实质都是递推的过程
③二者都要用循环结构来实现
辗转相除法的应用
　用辗转相除法求6 731与2 809的最大公约数．
[解]　6 731＝2 809×2＋1 113；
2 809＝1 113×2＋583；
1 113＝583×1＋530；
583＝530×1＋53；
530＝53×10.
∴6 731与2 809的最大公约数为53.
所谓辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数．
1．用辗转相除法求123和48的最大公约数．
解：用辗转相除法求最大公约数的过程如下：
123＝2×48＋27，
48＝1×27＋21，
27＝1×21＋6，
21＝3×6＋3，
6＝2×3＋0，
所以123和48的最大公约数为3.
秦九韶算法的应用
　用秦九韶算法计算当x＝2时，多项式：
f(x)＝x6－12x5＋60x4－160x3＋240x2－192x＋64的值．
[解]　将f(x)改写为
f(x)＝(((((x－12)x＋60)x－160)x＋240)x－192)x＋64，
由内向外依次计算一次多项式当x＝2时的值
v0＝1，
v1＝1×2－12＝－10，
v2＝－10×2＋60＝40，
v3＝40×2－160＝－80，
v4＝－80×2＋240＝80，
v5＝80×2－192＝－32，
v6＝－32×2＋64＝0.
∴f(2)＝0，即x＝2时，原多项式的值为0.
秦九韶算法的步骤
S1：输入多项式次数n、最高次项的系数an和x的值；
S2：将v的值初始化为an，将k的值初始化为n－1；
S3：输入k次项的系数ak；
S4：v＝vx＋ak，k＝k－1；
S5：判断k是否大于或等于0.若是，则返回S3；否则，输出多项式的值v.
2．用秦九韶算法求当x＝0.3时，多项式f(x)＝x5＋0.11x3－0.15x－0.04的值．
解：根据秦九韶算法，将f(x)写为：
f(x)＝((((x＋0)x＋0.11)x＋0)x－0.15)x－0.04.
按照从内到外的顺序，依次计算一次多项式当x＝0.3时的值：
v0＝1；
v1＝1×0.3＋0＝0.3；
v2＝0.3×0.3＋0.11＝0.2；
v3＝0.2×0.3＋0＝0.06；
v4＝0.06×0.3－0.15＝－0.132；
v5＝－0.132×0.3－0.04＝－0.079 6.
所以，当x＝0.3时，多项式的值为－0.079 6.
[随堂体验落实]
1．1 037和425的最大公约数是(　　)
A．51　　　　　　　　 　B．17
C．9 D．3
解析：选B　∵1 037＝425×2＋187，
425＝187×2＋51，
187＝51×3＋34，
51＝34×1＋17，
34＝17×2，
即1 037和425的最大公约数是17.
2．用秦九韶算法求多项式f(x)＝7x6＋6x5＋3x2＋2.当x＝4时的值时，先算的是(　　)
A．4×4＝16　　　　　 　B．7×4＝28
C．4×4×4＝64 D．7×4＋6＝34
解析：选D　用秦九韶算法求多项式f(x)＝7x6＋6x5＋3x2＋2当x＝4时的值时，应先算7×4＋6＝34.
3．秦九韶是我国南宋时期的数学家，普州(现四川省安岳县)人，他在所著的《数书九章》中提出的多项式求值的秦九韶算法，至今仍是比较先进的算法．如图所示的程序框图给出了利用秦九韶算法求某多项式值的一个实例．若输入n，x的值分别为3,2，则输出v的值为(　　)
A．9 B．18
C．20 D．35
解析：选B　由程序框图知，初始值：n＝3，x＝2，v＝1，i＝2，
第一次循环：v＝4，i＝1；
第二次循环：v＝9，i＝0；
第三次循环：v＝18，i＝－1.
结束循环，输出当前v的值18.故选B.
4．求两个正整数840与1 785的最大公约数________．
解析：1 785＝840×2＋105，
840＝105×8，
所以105为840与1 785的最大公约数．
答案：105
5．已知函数f(x)＝x3－2x2－5x＋8，利用秦九韶算法求f(9)的值________．
解析：f(x)＝x3－2x2－5x＋8＝((x－2)x－5)x＋8，
∴f(9)＝((9－2)×9－5)×9＋8＝530.
答案：530
6．用秦九韶算法求出当x＝3时f(x)＝2x5－4x3＋3x2－5x＋1的值．
解：∵f(x)＝((((2x＋0)x－4)x＋3)x－5)x＋1，
v0＝2，
v1＝2×3＋0＝6，
v2＝6×3－4＝14，
v3＝14×3＋3＝45，
v4＝45×3－5＝130，
v5＝130×3＋1＝391，
所以f(3)＝391.
[感悟高手解题]
[妙解题]
有甲、乙、丙三种溶液，分别为4 200毫升，3 220毫升和2 520毫升，现要将它们分别都装入相同的小瓶，每个瓶子装入液体的体积相同．问：要使所有溶液都刚好装满小瓶且所用瓶子数量最少，则小瓶的容积应为多少毫升？
[解]　本题实质是求4 200,3 220,2 520的最大公约数．先求4 200和3 220的最大公约数：
4 200＝3 220×1＋980，
3 220＝980×3＋280，
980＝280×3＋140，
280＝140×2，
所以4 200和3 220的最大公约数是140.
再求140和2 520的最大公约数：
2 520＝140×18，
所以140和2 520的最大公约数是140.
综上，4 200,3 220, 2 520的最大公约数是140，所以小瓶的容积应为140毫升．
一、选择题
1．用辗转相除法求72与120的最大公约数时，需要做除法次数为(　　)
A．4　　　　　　　 　　 　B．3
C．5 D．6
解析：选B　用辗转相除法：
120＝72×1＋48,72＝48×1＋24,48＝24×2.
2．用“辗转相除法”求得459和357的最大公约数是(　　)
A．3 B．9
C．17 D．51
解析：选D　用辗转相除法：459＝357×1＋102,357＝102×3＋51,102＝51×2.
∴459与357的最大公约数为51.
3．用秦九韶算法计算多项式f(x)＝3x6＋4x5－5x4＋6x3－7x2＋8x＋1当x＝2时的值时，需要做乘法和加法的次数分别是(　　)
A．6,6 B．5,6
C．5,5 D．6,5
解析：选A　由秦九韶算法将多项式改成如下形式：
f(x)＝(((((3x＋4)x－5)x＋6)x－7)x＋8)x＋1，
按由内到外的顺序，依次计算x＝2时的值．
v0＝3，v1＝3×2＋4＝10.
v2＝10×2－5＝15，
v3＝15×2＋6＝36，
v4＝36×2－7＝65，
v5＝65×2＋8＝138，
v6＝138×2＋1＝277.
这样求多项式的值时，是通过6个一次多项式的值得到的，
故进行了6次乘法和6次加法．
4．已知f(x)＝x5＋2x3＋3x2＋x＋1，应用秦九韶算法计算x＝3时的值时，v3的值为(　　)
A．27 B．11
C．109 D．36
解析：选D　将函数式化成如下形式．
f(x)＝((((x＋0)x＋2)x＋3)x＋1)x＋1.
由内向外依次计算：v0＝1，
v1＝1×3＋0＝3，
v2＝3×3＋2＝11，
v3＝11×3＋3＝36.
二、填空题
5．用秦九韶算法求函数f(x)＝1＋2x＋x2－3x3＋2x4，当x＝－1时的值时，v2的结果是________．
解析：此题的n＝4，a4＝2，a3＝－3，a2＝1，a1＝2，a0＝1，
由秦九韶算法的递推关系式
(k＝1,2，…，n)，得v1＝v0x＋a3＝2×(－1)－3＝－5，
v2＝v1x＋a2＝－5×(－1)＋1＝6.
答案：6
6．378与90的最大公约数为________．
解析：辗转相除法：
378＝90×4＋18，
90＝18×5＋0，
所以378与90的最大公约数是18.
答案：18
7．已知多项式f(x)＝3x5＋8x4－3x3＋5x2＋12x－6，则f(2)＝________.
解析：根据秦九韶算法，
把多项式改写成如下形式：f(x)＝((((3x＋8)x－3)x＋5)x＋12)x－6.
按照从内到外的顺序，依次计算一次多项式当x＝2时的值．
v0＝3，
v1＝3×2＋8＝14，
v2＝14×2－3＝25，
v3＝25×2＋5＝55，
v4＝55×2＋12＝122，
v5＝122×2－6＝238，
所以当x＝2时，多项式的值为238.
答案：238
8．324,243,270三个数的最大公约数为________．
解析：324＝243×1＋81,243＝81×3，所以324与243的最大公约数为81.
270＝81×3＋27,81＝27×3，所以81与270的最大公约数为27.
综上可知，324,243,270三个数的最大公约数为27.
答案：27
三、解答题
9．用辗转相除法求下面两组数的最大公约数．
(1)80,36；(2)294,84.
解：(1)80＝36×2＋8，
36＝8×4＋4，
8＝4×2＋0，
即80与36的最大公约数是4.
(2)294＝84×3＋42，
84＝42×2.
即294与84的最大公约数是42.
10．利用秦九韶算法计算多项式f(x)＝3x4＋2x3－9x2－11x＋1当x＝4时的值，写出每一步的计算表达式．
解：根据秦九韶算法将多项式改写成
f(x)＝(((3x＋2)x－9)x－11)x＋1，
按由内到外的顺序依次计算一次多项式当x＝4时的值．
v0＝3；
v1＝3×4＋2＝14；
v2＝14×4－9＝47；
v3＝47×4－11＝177；
v4＝177×4＋1＝709.
∴x＝4时，多项式的值f(4)＝709.
1．算法与程序框图
(1)算法和程序框图的核心是程序框图的三种基本逻辑结构，它与其他知识，如函数、方程 、不等式、数列等都有密切的联系，应用非常广泛．
(2)从近几年高考题来看程序框图是考查的重点，主要考查算法基本结构以及读图、识图、利用框图解决简单算法问题的能力．
2．基本算法语句
(1)基本算法语句是将程序框图转化为程序语句以实现算法的重要手段，是算法的主体内容．
(2)近两年高考题中基本算法语句均未考查，但仍不可忽视．不排除以后对基本算法语句的考查的可能性．
3．算法案例
通过阅读中国古代数学中的算法案例，体会算法思想以及中国古代数学对世界数学发展的贡献．
程序框图的应用
写出求关于x的方程ax2＋bx＋c＝0(a，b，c为常数)的解的算法步骤，并画出程序框图．
[解]　算法如下：
S1：输入a，b，c；
S2：若a≠0，则执行S3；若a＝0，则执行S7；
S3：Δ＝b2－4ac；
S4：若Δ<0，则输出“方程无实数根”，结束算法；若Δ≥0，则执行S5；
S5：x1＝，x2＝；
S6：输出x1，x2，结束算法；
S7：若b≠0，则执行S8；若b＝0，则执行S10；
S8：x＝－；
S9：输出x，结束算法；
S10：若c≠0，则输出“方程无实数根”，结束算法；若c＝0，则输出“方程的解是全体实数”，结束算法．
根据以上步骤，可画出如图所示的算法程序框图．
设计较简单的程序框图，我们可以通过对问题的分析，建立相应的数学模型或过程模型，进而选择顺序结构、条件结构、循环结构中的一种或几种画出程序框图即可．如果设计的程序框图较为复杂，就要采取“逐步求精”的思想设计程序框图，先将问题中的简单部分明确出来，再逐步对复杂部分进行细化，然后逐步向前推进，设计程序框图．
1．输入一个数x，通过函数y＝计算y，试用程序框图表示其算法．
解：这是一个分段函数，函数值与自变量x的取值范围有关，因此要用程序框图表达其算法，必须使用条件结构．程序框图如图所示．
2．某公司出售软盘，购买500片和500片以上时，按每片4.5元计价，否则按每片5元计价．请画一程序框图按输入软盘片数计算不同收费金额．
解：S1：输入购买软盘片数P；
S2：若购买片数大于等于500，则单价C＝4.5元；否则，单价C＝5元；
S3：单价乘以片数就得收费金额．
M＝C·P.
程序框图如图所示：
条件结构与条件语句
试编写求函数y＝－x2－2x＋3在x∈(－∞，n]上的最大值的伪代码，并画出 程序框图．
[解]　伪代码：
程序框图如图所示：
解决问题的过程中，必须先根据条件作出判断，再决定执行哪一种操作，画程序框图时必须通过条件结构实现，写伪代码也必须用条件语句描述．
3．根据如图所示的框图，说明该程序框图解决什么问题，写出相应的算法，并回答下列问题：
若输入x的值为5，则输出的结果是什么？
解：该程序框图解决的问题是求函数
y＝的值．
算法如下：
S1：输入x；
S2：若x<2，则y＝－2；否则，y＝x2－2x；
S3：输出y.
若输入x的值为5，则输出的结果是15.
4.如图，边长为2的正方形ABCD的边上有一动点P，点P沿边线由B→C→D→A运动，若P运动的路程为x，△APB的面积为y，试编写伪代码，根据输入的x值，输出相应的y值，并画出程序框图．
解：由题意可得y与x的函数关系式
y＝
程序框图如下：
伪代码如下：

循环结构与循环语句
设计算法求S＝12＋22＋32＋…＋992的值．要求画出程序框图，写出用基本语句编写的伪代码．
[解]　程序框图如图所示：
伪代码如下：

当需要解决的问题需要重复相同的步骤，要实现算法必须通过循环结构，伪代码的书写也必须用循环语句来描述．
5．(天津高考)阅读如图所示的程序框图，运行相应的程序，若输入N的值为24，则输出N的值为(　　)
A．0　　　　　　　　 　B．1
C．2 D．3
解析：选C　第一次循环，24能被3整除，N＝＝8>3；
第二次循环，8不能被3整除，N＝8－1＝7>3；
第三次循环，7不能被3整除，N＝7－1＝6>3；
第四次循环，6能被3整除，N＝＝2<3，结束循环，
故输出N的值为2.
6．已知某算法的程序框图如图所示，若将输出的(x，y)值依次记为(x1，y1)，(x2，y2)，…(xn，yn)，
(1)若程序运行中输出的一个数组是(9，t)，求t的值；
(2)程序结束时，共输出(x，y)的组数为多少？
(3)写出程序框图的伪代码．
解：(1)由程序框图知：当x＝1时，y＝0；
当x＝3时，y＝－2；
当x＝9时，y＝－4，
所以t＝－4.
(2)当n＝1时，输出一对，当n＝3时，又输出一对，…，当n＝2 019时，输出最后一对，共输出(x，y)的组数为1 010；
(3)程序框图的伪代码如下：