- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
§1.3 算法案例
第一课时 辗转相除法与更相减损术､秦九韶算法
自学导引 1.理解辗转相除法与更相减损术的含义,了解执行过程. 2.掌握秦九韶算法的计算过程,了解它在数学计算中的应用. 3.进一步体会算法的基本思想.
课前热身
欧几里得算法
两个正整数的最大公约数
1.辗转相除法是用于求
_____________________的一种方 较大的数
解:解法1(辗转相除法):先求175与100的最大公约数: 175=100×1+75, 100=75×1+25, 75=25×3. ∴175与100的最大公约数是25. 以下再求25与75的最大公约数: 75=25×3 ∴25和75的最大公约数是25.
故25是75和25的最大公约数,也就是175､100､75的最大公约数.
Hale Waihona Puke (3)任何两个数,用辗转相除法求其最大公约数的程序框图. 由于辗转相除法总是用较大的数去除以较小的数,所以首先要对一 开始给定的两数的大小进行判断,并将大数赋给m,小数赋给n,然 后再执行下面的过程.程序框图如下图所示:
(4)辗转相除法求两个数的最大公约数的程序设计.
INPUT “a,b”;a,b IF a<b THEN t=a a=b b=t END IF r=a MOD b WHILE r<>0 a=b b=r r=a MOD b WEND PRINT b END
解:(1)98和63 辗转相除法 S1 98=63 ×1+35, S2 63=35 ×1+28, S3 35=28×1+7, S4 28=4 ×7, 最大公约数为7.
更相减损术 S1 98-63=35, S2 63-35=28, S3 35-28=7, S4 28-7=21, S5 21-7=14, S6 14-7=7, 故98和63的最大公约数为7.
v0 an , 则有 其中k 1, 2,, n. vk vk 1 x an k ,
这样我们便可由a0依次求出v1,v2,„,vn: v1=v0x+an-1,v2=v1x+an-2,v3=v2x+an-3,„, vn=vn-1x+a0. 显然,用秦九韶算法求n次多项式的值时只需做n次乘法和n次加法 运算.
变式训练2:求三个数324,243,108的最大公约数. 解:解法1:先求324与243的最大公约数, 324=243×1+81, 243=81×3,
∴324与243的最大公约数为81.
下面再求108与81的最大公约数: 108=81+27, 81=27×3. ∴108与81的最大公约数是27.
故324,243,108的最大公约数为27.
比较,并以大数减小数,继续这个操作,直到所得的数
相等 ________ 为止,则这个数就是所求的最大公约数. 秦九韶
4.秦九韶算法是我国南宋数学家________在他的代表作
《数书九章》 ___________ 中提出的一种用于计算一元n次多项式的值
的方法.
名师讲解 1.辗转相除法
(1)辗转相除的原理. 设m,n是两个整数(不妨设m>n),用m除以n,若商为q1,余数为 r1(0≤r1<n),则m=n·q1+r1,显然若x是m和n的公约数,即x能整除 m和n,则x也必然能整除r1,这样x也是n和r1的公约数,故求m和n 的公约数就是求n和r1的公约数;同理,用n除以r1,得 n=r1·q2+r2(0≤r2<r1),所以n和r1的公约数就是r1和r2的公约数,„,
2.更相减损术 (1)更相减损术求两数最大公约数的过程与算法设计: 对于给定的两个数,用较大的数减去较小的数,接着把得到的差与较 小的数比较,用这时两个数中的较大的数减去较小的数,继续这样 的操作(大数减小数),直到所得的数相等为止,那么这个数(等数) 就是所求的最大公约数.
显然,上述过程中大数减去小数是一个重复执行的过程,因此只需将
(2)秦九韶算法程序框图: 以5次多项式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0当x=x0时为例,如下 图:
典例剖析 题型一 求两个数的最大公约数
例1:分别用辗转相除法和更相减损术逐步列出求(1)98和 63;(2)8251和6105的最大公约数的步骤,你有什么发现?对优劣 作出评判. 分析:辗转相除法是做两个数的带余除法,更相减损术是做两个数的 减法.
依次下去,由于m>n>r1>r2>„,所以到某一步必然有ri=ri+1·qi+2,
即ri恰能被ri+1整除,这时ri+1是ri和ri+1的公约数,它也必然是ri-1和 ri,ri-2和ri-1,„,r1与r2,n和r1,m和n的最大公约数.
(2)辗转相除法的算法分析. 由以上辗转相除法的原理可 以发现,辗转相除法的基本步 骤是用较大的数除以较小的 数,考虑到算法中的赋值语句 可以对同一变量多次赋值,我们可以把较大的数用变量m表示,把较小的数用变量n表示, 这样式子m=n·q+r(0≤r<n)就是一个反复执行的步骤,因此可以用循环结构实现算法. 如上图.
注:解法2的过程可简记为 (175,100,75) =(175-100,100-75,75) =(75,25,75) =(75-2×25,25,75-25×2) =(25,25,25) ∴三个数175,100,25的最大公约数为25. 规律技巧:本题的解法可以推广到求多个数的最大公约数,只需依次
计算即可.
解:f(x)=1+x+0.5x2+0.16667x3+0.04167x4+0.00833x5 =((((0.00833x+0.04167)x+0.16667)x+0.5)x+1)x+1. 而x=-0.2,所以有v0=a5=0.00833,v1=v0x+a4=0.04, v2=v1x+a3=0.15867,v3=v2x+a2=0.46826, v4=v3x+a1=0.90635,v5=v4x+a0=0.81873. 即f(-0.2)=0.81873.
答案:D
3.用秦九韶算法计算多项式f(x)=3x6+4x5+5x4+6x3+7x2+8x+1当 x=0.4时的值时,需要做乘法和加法的次数分别是( A.6,6 C.5,5 B.5,6 D.6,5 )
解析:∵f(x)的最高次项为3x6,共含有7项,∴用秦九韶算法求x=0.4 时的值时,需作乘法和加法各6次.
解法2:(324,243,108) =(324-243,243-108,108) =(81,135,108) =(81,135-108,108-81) =(81,27,27)=(81-2×27,27,27) =(27,27,27). ∴三个数324,243,108的最大公约数为27.
题型三 秦九韶算法的应用 例3:用秦九韶算法求多项式 f(x)=1+x+0.5x2+0.16667x3+0.04167x4+0.00833x5在x=-0.2的 值. 分析:可根据秦九韶算法原理,将所给多项式改写,然后由内到外逐次 计算即可.
解析:294=84×3+42,84=42×2. 故需做2次除法.
答案:B
2.两个整数490和910的最大公约数是( A.2 C.30 B.10 D.70
)
解析:910=91×10,490=49×10,
∵91=49×1+42,
49=42×1+7, 42=7×6. ∴91与49的最大公约数为7. 故910与490的最大公约数为70.
误区警示:利用秦九韶算法计算多项式值关键是能正确地将所给多 项式改写,然后由内向外逐次计算,由于后项计算需用到前项的结 果,故应认真､细心,确保中间结果的准确性.
变式训练3:已知f(x)=x5-4x4+2x2-5x+1,求f(3)的值.
解:f(x)=x5-4x4+0\5x3+2x2-5x+1 =(x4-4x3+0\5x2+2x-5)x+1 =((x3-4x2+0\5x+2)x-5)x+1 =(((x2-4x+0)x+2)x-5)x+1 =((((x-4)x+0)x+2)x-5)x+1.
步骤即可.
解:用辗转相除法: 80=36×2+8, 36=8×4+4, 8=4×2+0. 故80和36的最大公约数是4. 用更相减损术检验:80-36=44,
44-36=8, 36-8=28, 28-8=20, 20-8=12,
12-8=4,
8-4=4. ∴80和36的最大公约数是4.
题型二 求三个数的最大公约数 例2:求三个数175､100､75的最大公约数. 分析:求三个数的最大公约数时,可以先求出其中两个数的最大公约 数,用这个最大公约数再与第三个数求最大公约数,所得结果就是 这三个数的最大公约数.
∵x=3,∴v0=a5=1; v1=1×3-4=-1; v2=-1×3+0=-3; v3=-3×3+2=-7; v4=-7×3-5=-26; v5=-26×3+1=-77. ∴f(3)=-77.
技能演练 基础强化
1.用辗转相除法求294和84的最大公约数时,需要做除法的次数是 ( A.1 C.3 D.4 ) B.2
因此(1)中 S4 28=4×7 可作四次减法,即28中可减4次7.
(2)中 S4 1813=333×5+148 在1813中可减5次333. 从形式上看更相减损术比辗转相除法复杂,但计算机更“喜欢”做 加减法.加减法比乘除法快几百倍. 变式训练1:用辗转相除法求80和36的最大公约数,并用更相减损术 检验所得结果. 分析:将80作为大数,36作为小数,执行辗转相除法和更相减损术的
