当前位置:
文档之家› 高中人A数学必修三-第一章学案六 算法案例
高中人A数学必修三-第一章学案六 算法案例
356;1356
5 36
1306;1306
5 36
356,
即
416,343
,2
2 9
的最大公约数是
15 36
.
【评析】本题考查更相减损术.
精品课件
返回
2.用更相减损之术求98和63的最大公约数.
【分析】由于63不是偶数,把98和63以大数减小数,并 辗转相减.
【解析】98-63=35,63-35=28,35-28=7,287=21,21-7=14,14-7=7.所以98和63的最大公约数为7.
343-147=196, 196-147=49,
147-49=98, 98-49=49.
所以147与343的最大公约数是49.
再求49与133的最大公约数:
133-49=84, 84-49=35,
49-35=14,
35-14=21,
21-14=7,
14-7=7.
所以147,343,133的最大公约数为7.
精品课件
返回
学点二 更相减损术
1它.有们甲分、别乙全、部丙装三入种小溶瓶液中,,分每别个重小瓶4 装16kg入, 液k体3g43的, 重k量g2.相先92 同要.将 问:每瓶最多装多少?
【分析】本题考查更相减损术的计算步骤及思想.根据 题意,每个小瓶装的溶液的质量应是三种溶液质量的最大公 约数.先求任意两个数的最大公约数,然后再求这个数与第 三个数的最大公约数.
值,即v1=
anx+,然an后-1由内向外逐层计算一次多项式的
值,即
v2= v3=
v1x+an-2 v2x+an-3
, ,
…
vn= vn-1x+a0 ,
精品课件
返回
这样,求n次多项式f(x)的值就转化为
求n个一次多项式的值
.Leabharlann 上述方法称为秦九韶算法.观察上述秦九韶算法中的n个一次式,可见vk的计算要
【评析】等值算法是当大数减去小数的差等于小数时 停止减法,较小的数就是所求的最大公约数.
精品课件
返回
有甲、乙、丙三种溶液分别重147 kg,343 kg,133 kg,现
要将它们分别全部装入小瓶中,每个小瓶装入液体的质量相
同,问每瓶最多装多少?
解:由题意,每小瓶装的溶液的质量应是三种溶液质量
的最大公约数,先求147与343的最大公约数:
精品课件
返回
【评析】辗转相除法是当大数被小数除尽时,结束 除法运算,较小的数就是最大公约数;更相减损术是当大 数减去小数的差等于小数时停止减法,较小的数就是最 大公约数.
精品课件
返回
用辗转相除法求80与36的最大公约数,并用更相减损术检 验所得结果.
解:用辗转相 除:80=36×2+8,36=8×4+4,8=4×2+0;用更相减损术 检验: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.《九章算术》中的“更相减损术”求两个数的最大
公约数.翻译为现代汉语如下:
第一步,任意给定两个正整数,判断它们是否是偶数,
若是,用2约简;若不是,执行第二步.
第二步,用两数中较大的数减去较小的数,再用 差数. 和 较小的构数成新的一对数,再用大数减小数,以同样的操作
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
求多项式的值时,首先计算最内层括号内一次多项式的
376513563660;366013563465;346513563360;336013561356.
精品课件
返回
即
4
1 6
和
3
3 4
的最大公约数是 15
36
.
8 30 61 35 63 66 5;3 66 51 35 63 56 0;3 56 01 35 63 36 5;3 36 51 35 63 26 0;3 26 01 35 6
用到vk-1的值.若令v0=an,我们可以得到公式:
vo=an vk=vk-1x+an-k(k=1,2,…,n).
这是一个在秦九韶算法中反复执行的步骤,因此可用
循环结构来实现.
精品课件
返回
学点一 辗转相除法 用辗转相除法求90与36的最大公约数.
【分析】本题考查辗转相除法求两个数的最大公约
数的步骤.使用辗转相除法求90与36的最大公约数时,先 用90除以36,余数为18,用36除以18,余数为0,18就是 90与36的最大公约数.顺便提示一下,两个数a,b的最大 公约数一般写成(a,b),如90与36的最大公约数为18,写 成(90,36)=18.
一直做下去,直到产生
一对相等的为数止,这个数(等数)
或这个数与约简的数的乘积就是最大公约数.
2.古希腊求两个正整数的最大公约数的方法是:
辗转相除法 :用较大的数除以较小的数所得的 余数 和
较小的数 构成新的一对数,继续做上面的除法,直到大数
被小数除尽,这个较小的数就是最大公约数.
精品课件
返回
3.把一个n次多项式f(x)=anxn +an-1xn-1+…+
【解析】令m=90,n=36,m=2n+18,r=18. 令m=36,n=18. 又有36=18×2,即m=2n,
精品课件
返回
此时r=0. 令m=18,n=0. 故90与36的最大公约数为18. 程序步骤如下: INPUT m=;n=; m=90;n=36; DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT “90与36的最大公约数为:”;m END
【解析】4 1 6 2 6 1 5 3; 3 5 6 4 3 1 0 4 1 5 3; 2 3 6 9 2 2 5 9 8 3 0 ; 1 3 0 6 5 1 6 30 3 65
1 3 ; 1 3 5 6 1 3 3 6 1 3 5 6 5 ; 1 3 2 6 1 3 2 6 0 1 3 5 6 0 ; 1 3 0 6 1 3 0 6 5 3 9 5 6 5 ; 3 9 6 0 1 3 6 0 3 7 5 6 ;6 5
故每瓶最多装7 kg.
精品课件