算法案例
__________________________________________________________________________________ __________________________________________________________________________________ 1．理解算法案例的算法步骤和程序框图. 2．引导学生得出自己设计的算法程序.
3. 体会算法的基本思想||，提高逻辑思维能力||，发展有条理地思考与数学表达能力. 1．求两个正整数最大公约数的算法 (1)更相减损之术(等值算法)
用两数中较大的数减去较小的数||，再用差数和较小的数构成新的一对数||，再用大数减小数||，以同样的操作一直做下去||，直到产生一对相等的数||，这个数就是最大公约数． (2)用“等值算法”求最大公约数的程序
while a＝a－b b＝b－a end
2．割圆术
用圆内接正多边形面积逐渐逼近圆的面积的算法是计算圆周率的一种方法． 3.秦九韶算法:
把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如下形式： 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
求多项式的值时||，首先计算最内层括号内一次多项式的值||，然后由内向外逐层计算一次多项式的值．这样通过一次式的反复运算||，逐步得出高次多项式的值的方法称作秦九韶算法||。
观察上述秦九韶算法中的n个一次式可见||，只要令??v0?an其中k?1,2,?,n就得到
?vk?vk?1x?an?k了一个递推关系||。这个递推关系是一个反复执行的步骤||，可用循环语句来实现||。
理解秦九韶算法的关键：一是弄清算法原理是加法对乘法的分配律||，二是弄清算法设计中递推关系是一个反复执行的运算||，故用循环语句来实现||。
（1）秦九韶算法过程分析：
由于??v0?an其中k＝1||，2||，…||，n.
?vk?vk?1x?an?k这样我们便可由v0依次求出v1||，v2||，…||，vn：
v1＝v0x＋an－1||，v2＝v1x＋an－2||，v3＝v2x＋an－3||，…||，vn＝vn－1x＋a0||。
于是我们用v来记录每次一次式计算的结果||，最初赋值v＝an||，用v＝v*x＋an－i实现递推循环||，i的初值为1||，i＝i＋1记录循环次数||，i≤n控制何时结束循环输出v.f(x)的系数ak用一个循环语句实现输入||。
（2）f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0当x＝x0时||，求函数值f(x0)的算法设计||。 程序框图：
第1页/共9页
（3）用秦九韶算法将一个多项式(n次)的至多乘法和n次加法运算||，大大提高了运算效率||。
n?n?1?次乘法和n次加法运算减少为至多n次2类型一 用更相减损术求两个正整数的最大公约数
例1：求80和36的最大公约数．
[解析] 当大数减小数的差等于小数时停止减法||，较小的数就是两数的最大公约数． [答案] 80－36＝44||， 44－36＝8||， 36－8＝28||， 28－8＝20||， 20－8＝12||， 12－8＝4||， 8－4＝4.
∴80和36的最大公约数是4.
练习1：用更相减损之术分别求下列两组数的最大公约数： (1)78与36； (2)1 515与600.
[答案] (1)(78||，36)→(42||，36)→(6||，36)→(6||，30)→(6||，24)→(6||，18) →(6||，12)→(6||，6)||，故78与36的最大公约数为6.
(2)1 515－600＝915||，915－600＝315||，600－315＝285||，315－285＝30||，285－30＝255||，255－30＝225||，225－30＝195||，195－30＝165||，165－30＝135||，135－30＝105||，105－30＝75||，75－30＝45||，45－30＝15||，30－15＝15||，故1 515与600的最大公约数是15. 类型二 用辗转相除法求两个正整数的最大公约数
例2：用辗转相除法求546与429的最大公约数.
[解析] 用辗转相除法求最大公约数步骤较少||，而更相减损术虽然步骤较长||，但运算简单． [答案] 546＝1×429＋117||， 429＝3×117＋78||， 117＝1×78＋39||， 78＝2×39||，
故546与429的最大公约数为39.
练习1：用辗转相除法求288和123的最大公约数． [答案] 288＝2×123＋42||， 123＝2×42＋39||， 42＝1×39＋3||， 39＝13×3||，
故3就是288和123的最大公约数.
练习2：用辗转相除法求355和60的最大公约数． [答案] 355＝5×60＋55||， 60＝1×55＋5||， 55＝11×5||，
故5就是355和60的最大公约数. 类型三 用秦九韶算法求多项式的值
例3：用秦九韶算法求多项式f(x)＝x5＋0.11x3－0.15x－0.04当x＝0.3时的值．
[解析](1)用秦九韶算法求多项式的值||，首先要将多项式改写||，然后由内向外逐次计算. 由于下
第2页/共9页
一次计算要用到上一次的结果||，故应认真、细心||，确保每个中间结果的准确性．
(2)当多项式中有几项不存在时||，可将这几项的系数看成是0||，即0×xn. [答案]将f(x)写为：
f(x)＝x5＋0×x4＋0.11x3＋0×x2－0.15x－0.04. 由秦九韶算法的递推公式||，得 v0＝1||，
v1＝v0×0.3＋0＝0.3||， v2＝v1×0.3＋0.11＝0.2||， v3＝v2×0.3＋0＝0.06||，
v4＝v3×0.3－0.15＝－0.132||， v5＝v4×0.3－0.04＝－0.079 6||，
所以当x＝0.3时||，多项式的值为－0.079 6.
练习1：已知函数f(x)＝x3－2x2－5x＋6||，用秦九韶算法求f(10)的值． [答案] 由秦九韶法||，得 f(x)＝x3－2x2－5x＋6 ＝(x2－2x－5)x＋6 ＝((x－2)x－5)x＋6||， 当x＝10时||，
f(10)＝((10－2)×10－5)×10＋6 ＝(8×10－5)×10＋6 ＝75×10＋6 ＝756.
练习2：已知函数f(x)＝x3－2x2＋5x＋6||，用秦九韶算法求f(10)的值． [答案] 由秦九韶法||，得 f(x)＝x3－2x2＋5x＋6 ＝(x2－2x＋5)x＋6 ＝((x－2)x＋5)x＋6||， 当x＝10时||，
f(10)＝((10－2)×10＋5)×10＋6 ＝(8×10＋5)×10＋6 ＝85×10＋6 ＝856.
练习3：已知多项式f(x)＝3x5－2x2－5x4＋3x3＋x||，则f(2)＝________. [答案] 34
f(x)＝3x5－2x2－5x4＋3x3＋x ＝3x5－5x4＋3x3－2x2＋x
＝((((3x－5)x＋3)x－2)x＋1)x||， v0＝3||，
v1＝3×2－5＝1||， v2＝1×2＋3＝5||， v3＝5×2－2＝8||， v4＝8×2＋1＝17||， v5＝17×2＝34.
∴当x＝2时||，多项式的值为34. 类型四 求三个正整数的最大公约数
第3页/共9页
例4：求三个数324、243、270的最大公约数．
[解析] 求三个数的最大公约数||，可先求两数的最大公约数a||，然后求a与第三个数的最大公约数b||，则b为所求的三数的最大公约数．该题解法可推广到求多个数的最大公约数．
[答案] 324＝243×1＋81||，243＝81×3＋0||，则324与243的最大公约数为a＝81. 又270＝81×3＋27||，81＝27×3＋0||，则324||，243||，270的最大公约数为27. 练习1：求324||，243和135的最大公约数．
[答案] (324||，243)―→(81||，243)―→(81||，162)―→(81||，81)则324与243最大公约数为81. 又(81||，135)―→(81||，54)―→(27||，54)―→(27||，27)||，则81与135的最大公约数为27||， ∴324、243、135的最大公约数为27. 类型五 求两个正整数的最小公倍数
例5：求375、85的最小公倍数
[解析] 求两个正整数的最小公倍数||，即利用它们的积除以它们的最大公约数．本题求法可推广到求多个数的情况．
[答案] 先求最大公约数||，375＝85×4＋35||，85＝35×2＋15||，35＝15×2＋5||，15＝5×3＋0.
∴375与85的最大公约数是5||，∴375与85的最小公倍数是(375×85)÷5＝6 375. 练习1：求80与36的最小公倍数． [答案] 先求最大公约数． 80＝36×2＋8
36＝8×4＋4＝8＝4×2＋0 ∴80与36的最大公约数为4.
∴80与36的最小公倍数是(80×36)÷4＝720.
1．秦九韶算法与直接计算相比较||，下列说法错误的是( )
A．秦九韶算法与直接计算相比||，大大节省乘法的次数||，使计算量减少||，并且逻辑结构简单 B．秦九韶算法减少做乘法的次数||，在计算机上也就加快了计算的速度 C．秦九韶算法减少做乘法的次数||，在计算机上也就降低了计算的速度
D．秦九韶算法避免对自变量x单独做幂的计算||，而是与系数一起逐次增长幂次||，从而可提高计算的精度
[答案] C
2．用圆内接正多边形逼近圆||，因而得到的圆周率总是________π的实际值．( ) A．大于等于 B．小于等于 C．等于 D．小于 [答案] D
3．用更相减损之术求88与24的最大公约数为( ) A．2 B．7 C．8 D．12 [答案] C
4．三个数72||，120||，168的最大公约数是________． [答案] 24 5．用秦九韶算法计算f(x)＝9x6＋3x5＋4x4＋6x3＋x2＋8x＋1||，当x＝3时的值||，需要进行________次乘法和________次加法运算．
[答案] 6 6
6．已知f(x)＝x5＋x3＋x2＋x＋1||，求f(3)的值． [答案] f(x)＝((((x＋0)x＋1)x＋1)x＋1)x＋1||， v1＝1×3＋0＝3||， v2＝3×3＋1＝10||，
第4页/共9页
v3＝10×3＋1＝31||， v4＝31×3＋1＝94||， v5＝94×3＋1＝283||，
∴f(3)＝((((3＋0)×3＋1)×3＋1)×3＋1)×3＋1＝283.
_________________________________________________________________________________ _________________________________________________________________________________
基础巩固
一、选择题
1．在秦九韶算法中用到的一种方法是( ) A．消元 B．递推 C．回代 D．迭代
[答案] B
[解析] 秦九韶算法中用到的是递推法．
2．用更相减损术求294和84的最大公约数时||，需要做减法的次数为( ) A．2 B．3 C．4 D．5 [答案] C
[解析] (84||，294)→(84||，210)→(84||，126)→(84||，42)→(42||，42)||，一共做了4次减法．3．用秦九韶算法求多项式f(x)＝x3－3x2＋2x－11的值时||，应把f(x)变形为( ) A．x3－(3x＋2)x－11 B．(x－3)x2＋(2x－11) C．(x－1)(x－2)x－11 D．((x－3)x＋2)x－11 [答案] D
[解析] f(x)＝x3－3x2＋2x－11＝((x－3)x＋2)x－11||，故选D. 4．用“等值算法”可求得204与85的最大公约数是( ) A．15 B．17 C．51 D．85
[答案] B
[解析] 204－85＝119||，119－85＝34||，85－34＝51||，51－34＝17||，34－17＝17||， ∴204和85的最大公约数是17||，故选B.
5．根据递推公式??v0＝an
?v||，其中k＝1||，2||，…||，n||，可得当k＝2时||，v2的值为( k＝vk－1x＋an－k
A．v2＝anx＋an－1
B．v2＝(anx＋an－1)x＋an－2
第5页/共9页
)
人教版高中数学必修三第一章算法初步1.3算法案例（教师版）个性化辅导含答案
