(共29张PPT)
1.3
算法案例
第二课时
问题提出
问题提出
问题提出
秦九韶算法
知识探究(一):秦九韶算法的基本思想
思考1
知识探究(一):秦九韶算法的基本思想
思考1
21325
知识探究(一):秦九韶算法的基本思想
思考1
21325
算法1：
需要(5+4+3+2+1)=15次乘法，5次加法
知识探究(一):秦九韶算法的基本思想
思考1
21325
算法1：
需要(5+4+3+2+1)=15次乘法，5次加法
秦九韶算法
算法2：
需要5次乘法，5次加法
知识探究(一):秦九韶算法的基本思想
思考1
21325
算法1：
需要(5+4+3+2+1)=15次乘法，5次加法
秦九韶算法
思考2
算法2：
需要5次乘法，5次加法
知识探究(一):秦九韶算法的基本思想
思考1
21325
算法1：
需要(5+4+3+2+1)=15次乘法，5次加法
秦九韶算法
思考2
18556
算法2：
需要5次乘法，5次加法
知识探究(二):秦九韶算法的程序设计
思考1:用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法？其算法步骤如何设计？
第一步，输入多项式的次数n，最高次
项的系数an和x的值.
第二步，令v=an，i=n-1.
第三步，输入i次项的系数ai.
第四步，v=vx+ai，i=i-1.
第五步，判断i≥0是否成立.若是，则返回第
二步；否则，输出多项式的值v.
思考2:该算法的程序框图如何表示？
开始
输入n，an，x的值
v=an
v=vx+ai
输入ai
i≥0？
i=n-1
i=i-1
结束
是
输出v
否
思考3:该程序框图对应的程序如何表述？
开始
输入n，an，x的值
v=an
v=vx+ai
输入ai
i≥0？
i=n-1
i=i-1
结束
是
输出v
否
INPUT
“n=”；n
INPUT
“an=”；a
INPUT
“x=”；x
v=a
i=n-1
WHILE
i>=0
INPUT
“ai=”；b
v=v
x+b
i=i-1
WEND
PRINT
y
END
理论迁移
例1
已知一个5次多项式为
用秦九韶算法求f(5)的值.
f(x)=((((5x+2)x+3.5)x-2.6)x+1.7)x-0.8.
v1=5×5+2=27；
v2=27×5+3.5=138.5；
v3=138.5×5-2.6=689.9；
v4=689.9×5+1.7=3451.2；
v5=3451.2×5-0.8=17255.2.
所以f(5)=
=17255.2.
例
2
阅读下列
程序，说明它
解决的实际问
题是什么？
理论迁移
例
2
阅读下列
程序，说明它
解决的实际问
题是什么？
理论迁移
小结作业
作业：《习案》作业九§1.3 算法案例
课时目标 通过三种算法案例：辗转相除法与更相减损术，秦九韶算法，进位制，进一步体会算法的思想，提高算法设计水平，体会中国古代数学对世界的贡献．
1．辗转相除法
(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法．
(2)辗转相除法的算法步骤
第一步，给定两个正整数m，n.
第二步，计算m除以n所得的余数r.
第三步，m＝n，n＝r.
第四步，若r＝0，则m、n的最大公约数等于m；否则，返回第二步．
2．更相减损术
第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．
第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．
3．秦九韶算法
把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋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个一次多项式的值．
4．进位制
进位制是人们为了计数和运算方便而约定的记数系统，“满k进一”就是k进制，k进制的基数是k.
把十进制转化为k进制数时，通常用除k取余法．
一、选择题
1．下列说法中正确的个数为( )
(1)辗转相除法也叫欧几里得算法；
(2)辗转相除法的基本步骤是用较大的数除以较小的数；
(3)求最大公约数的方法，除辗转相除法之外，没有其他方法；
(4)编写辗转相除法的程序时，要用到循环语句．
A．1
B．2
C．3
D．4
答案 C
解析 (1)、(2)、(4)正确，(3)错误．
2．用更相减损术求294和84的最大公约数时，需做减法的次数是( )
A．2
B．3
C．4
D．5
答案 C
解析 由于294和84都是偶数，
所以用2约简：
294÷2＝147，
84÷2＝42，
又由于147不是偶数，
所以147－42＝105，
105－42＝63，
63－42＝21，
42－21＝21，
故需做4次减法，故选C.
3．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.
4．用秦九韶算法计算多项式f(x)＝6x6＋5x5＋4x4＋3x3＋2x2＋x＋7在x＝0.4时的值时，需做加法和乘法的次数的和为( )
A．10
B．9
C．12
D．8
答案 C
解析 f(x)＝(((((6x＋5)x＋4)x＋3)x＋2)x＋1)x＋7
∴加法6次，乘法6次，
∴6＋6＝12(次)，故选C.
5．已知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，
v4＝36×3＋1＝109，
v5＝109×3＋1＝328.
6．下列有可能是4进制数的是( )
A．5
123
B．6
542
C．3
103
D．4
312
答案 C
解析 4进制数每位上的数字一定小于4，故选C.
二、填空题
7．辗转相除法程序中有一空请填上．
答案 a
MOD
b
解析 MOD用来表示a除以b的余数．
8．更相减损术程序中有两空请填上．
答案 a＝b b＝r
9．已知三个数12(16)，25(7)，33(4)，将它们按由小到大的顺序排列为________．
答案 33(4)<12(16)<25(7)
解析 将三个数都化为十进制数．
12(16)＝1×16＋2＝18，
25(7)＝2×7＋5＝19，
33(4)＝3×4＋3＝15，
∴33(4)<12(16)<25(7)．
三、解答题
10．用两种方法求210与98的最大公约数．
解 用辗转相除法：
210＝98×2＋14，
98＝14×7.
∴210与98的最大公约数为14.
用更相减损术：
∵210与98都是偶数，用2约简得
105和49，
105－49＝56,56－49＝7，
49－7＝42,42－7＝35，
35－7＝28,28－7＝21，
21－7＝14,14－7＝7.
∴210与98的最大公约数为2×7＝14.
11．用秦九韶算法计算多项式f(x)＝x6－12x5＋60x4－160x3＋240x2－192x＋64当x＝2时的值．
解 将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.
能力提升
12．把111化为五进制数．
解
∴111化为五进制数为421(5)．
13．把10
231(5)化为四进制数．
解 先化成十进制数．
10
231(5)＝1×54＋0×53＋2×52＋3×51＋1
＝625＋50＋15＋1
＝691
再化为四进制数
∴10
231(5)＝22
303(4).
1．辗转相除法与更相减损术的区别和联系
(1)都是求最大公约数的方法．
(2)二者的实质都是递归的过程．
(3)二者都要用循环结构来实现．
2．秦九韶算法的特点
秦九韶算法的特点在于把求一个n次多项式的值转化为求n个一次多项式的值，即把求f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0的值转化为求递推公式：
这样可以最多计算n次乘法和n次加法即可得多项式的值，和直接代入多项式相比减少了乘法的运算次数，提高了运算效率．
3．十进制与其他进制的转化
(1)将k进制转化为十进制的方法：先把k进制数写成各位上的数字与k的幂的乘积的形
式，再按十进制的运算规则计算．
(2)将十进制化成k进制的方法：用除k取余法，用k连续去除十进制数所得的商，直到商为零为止，然后将各步所得的余数倒序写出，即为相应的k进制数．(共36张PPT)
QD
ANYOU
KETANG
81750
余数
8
218
8
27
2
8
3
0秦九韶算法
( http: / / www. )
一、三维目标
( http: / / www. )
（a）知识与技能
( http: / / www. )
了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质。
( http: / / www. )
（b）过程与方法
( http: / / www. )
模仿秦九韶计算方法，体会古人计算构思的巧妙。
( http: / / www. )
（c）情态与价值观
( http: / / www. )
通过对秦九韶算法的学习，了解中国古代数学家对数学的贡献，充分认识到我国文化历史的悠久。充分认识信息技术对数学的促进。
( http: / / www. )
二、教学重难点
( http: / / www. )
重点：1.秦九韶算法的特点
( http: / / www. )
难点：1.秦九韶算法的先进性理解
( http: / / www. )
三、教学设计
( http: / / www. )
（一）创设情景，揭示课题
( http: / / www. )
1.辗转相除法和更相减损术，是求两个正整数的最大公约数的优秀算法，我们将算法转化为程序后，就可以由计算机来执行运算，实现了古代数学与现代信息技术的完美结合.
( http: / / www. )
2.对于求n次多项式的值，在我国古代数学中有一个优秀算法，即秦九韶算法，我们将对这个算法作些了解和探究.
( http: / / www. )
（二）研探新知
( http: / / www. )
思考1
21325
( http: / / www. )
算法1：需要(5+4+3+2)=14次乘法，5次加法
( http: / / www. )
算法2：需要5次乘法，5次加法
秦九韶算法
( http: / / www. )
思考2
18556
思考3:利用后一种算法求多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值，这个多项式应写成哪种形式？
f(x)=anxn+an-1xn-1+…+a1x+a0=(anxn-1+an-1xn-2+…+a2x+a1)x+a0
=((anxn-2+an-1xn-3+…+a2)x+a1)x+a0=…
=(…((anx+an-1)x+an-2)x+…+a1)x+a0.
思考4:对于f(x)=(…((anx+an-1)x+an-2)x+…+a1)x+a0，由内向外逐层计算一次多项式的值，其算法步骤如何？
第一步，计算v1=anx+an-1.
第二步，计算v2=v1x+an-2.
第三步，计算v3=v2x+an-3.
…
第n步，计算vn=vn-1x+a0.
思考5:上述求多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值的方法称为秦九韶算法，利用该算法求f(x0)的值，一共需要多少次乘法运算，多少次加法运算？
思考6:在秦九韶算法中，记v0=an，那么第k步的算式是什么？
vk=vk-1x+an-k
(k=1，2，…，n)
例1
阅读下列程序，说明它解决的实际问题是什么？
求多项式，在x=a时的值.
评价一个算法好坏的一个重要标志是运算的次数，如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理论算法.在多项式求值的各种算法中，秦九韶算法是一个优秀算法.
作业：《习案》作业九(共104张PPT)
1.3
算法案例
第二课时
问题提出
问题提出
问题提出
问题提出
问题提出
问题提出
问题提出
辗转相除法与
更相减损术
知识探究（一）:辗转相除法
知识探究（一）:辗转相除法
知识探究（一）:辗转相除法
8251=6105×1+2146，
8251=6105×1+2146，
6105=2146×2+1813，
2146=1813×1+333，
8251=6105×1+2146，
6105=2146×2+1813，
2146=1813×1+333，
1813=333×5+148，
8251=6105×1+2146，
6105=2146×2+1813，
2146=1813×1+333，
333=148×2+37，
1813=333×5+148，
8251=6105×1+2146，
6105=2146×2+1813，
2146=1813×1+333，
148=37×4+0.
333=148×2+37，
1813=333×5+148，
8251=6105×1+2146，
6105=2146×2+1813，
思考5:该算法的程序框图如何表示？
思考5:该算法的程序框图如何表示？
思考5:该算法的程序框图如何表示？
思考5:该算法的程序框图如何表示？
思考5:该算法的程序框图如何表示？
思考5:该算法的程序框图如何表示？
思考5:该算法的程序框图如何表示？
思考5:该算法的程序框图如何表示？
思考5:该算法的程序框图如何表示？
思考5:该算法的程序框图如何表示？
思考6:该程序框图对应的程序如何表述？
思考6:该程序框图对应的程序如何表述？
INPUT
m，n
思考6:该程序框图对应的程序如何表述？
INPUT
m，n
DO
思考6:该程序框图对应的程序如何表述？
INPUT
m，n
DO
r=m
MODn
思考6:该程序框图对应的程序如何表述？
INPUT
m，n
DO
r=m
MODn
m=n
思考6:该程序框图对应的程序如何表述？
INPUT
m，n
DO
r=m
MODn
m=n
n=r
思考6:该程序框图对应的程序如何表述？
INPUT
m，n
DO
r=m
MODn
m=n
n=r
LOOP
UNTIL
r=0
思考6:该程序框图对应的程序如何表述？
INPUT
m，n
DO
r=m
MODn
m=n
n=r
LOOP
UNTIL
r=0
PRINT
m
开始
开始
开始
n>0？
开始
n>0？
开始
n>0？
结束
开始
n>0？
结束
是
开始
m=n
n>0？
结束
是
开始
m=n
n>0？
结束
是
n=r
开始
m=n
n>0？
结束
是
n=r
开始
m=n
n>0？
结束
是
n=r
INPUT
m，n
开始
m=n
n>0？
结束
是
n=r
INPUT
m，n
WHILE
n>0
开始
m=n
n>0？
结束
是
n=r
INPUT
m，n
WHILE
n>0
r=m
MODn
开始
m=n
n>0？
结束
是
n=r
INPUT
m，n
WHILE
n>0
r=m
MODn
m=n
开始
m=n
n>0？
结束
是
n=r
INPUT
m，n
WHILE
n>0
r=m
MODn
m=n
n=r
开始
m=n
n>0？
结束
是
n=r
INPUT
m，n
WHILE
n>0
r=m
MODn
m=n
n=r
WEND
开始
m=n
n>0？
结束
是
n=r
INPUT
m，n
WHILE
n>0
r=m
MODn
m=n
n=r
WEND
PRINT
m
开始
m=n
n>0？
结束
是
n=r
INPUT
m，n
WHILE
n>0
r=m
MODn
m=n
n=r
WEND
PRINT
m
END
知识探究（二）:更相减损术
知识探究（二）:更相减损术
知识探究（二）:更相减损术
98-63=35，
知识探究（二）:更相减损术
98-63=35，
63-35=28，
知识探究（二）:更相减损术
98-63=35，
35-28=7，
63-35=28，
知识探究（二）:更相减损术
98-63=35，
28-7=21，
35-28=7，
63-35=28，
知识探究（二）:更相减损术
98-63=35，
21-7=14，
28-7=21，
35-28=7，
63-35=28，
知识探究（二）:更相减损术
98-63=35，
14-7=7.
21-7=14，
28-7=21，
35-28=7，
63-35=28，
思考3:该算法的程序框图如何表示？
思考3:该算法的程序框图如何表示？
INPUT
m，n
INPUT
m，n
WHILE
m<>n
INPUT
m，n
WHILE
m<>n
k=m-n
INPUT
m，n
WHILE
m<>n
k=m-n
IF
n>k
THEN
INPUT
m，n
WHILE
m<>n
k=m-n
IF
n>k
THEN
m=n
INPUT
m，n
WHILE
m<>n
k=m-n
IF
n>k
THEN
m=n
n=k
INPUT
m，n
WHILE
m<>n
k=m-n
IF
n>k
THEN
m=n
n=k
ELSE
INPUT
m，n
WHILE
m<>n
k=m-n
IF
n>k
THEN
m=n
n=k
ELSE
m=k
INPUT
m，n
WHILE
m<>n
k=m-n
IF
n>k
THEN
m=n
n=k
ELSE
m=k
END
IF
INPUT
m，n
WHILE
m<>n
k=m-n
IF
n>k
THEN
m=n
n=k
ELSE
m=k
END
IF
WEND
INPUT
m，n
WHILE
m<>n
k=m-n
IF
n>k
THEN
m=n
n=k
ELSE
m=k
END
IF
WEND
PRINT
m
INPUT
m，n
WHILE
m<>n
k=m-n
IF
n>k
THEN
m=n
n=k
ELSE
m=k
END
IF
WEND
PRINT
m
END
理论迁移
理论迁移
理论迁移
小结作业
小结作业1-3-1辗转相除法与更相减损术、秦九韶算法
一、选择题
1．下列有关辗转相除法的说法正确的是( )
A．它和更相减损术一样是求多项式值的一种方法
B．基本步骤是用较大的数m除以较小的数n得到除式m＝nq＋r，直至rC．基本步骤是用较大的数m除以较小的数n得到除式m＝qn＋r(0≤rD．以上说法均不正确
[答案] C
2．当x＝9时，用秦九韶算法计算f(x)＝12x6＋5x5＋8x4＋11x3＋18x2＋52x＋99的值，需要进行的乘法和加法的次数分别是( )
A．12,12
B．6,7
C．21,6
D．6,6
[答案] D
3．在m＝nq＋r(0≤rA．一定是
B．不一定是
C．一定不是
D．不能确定
[答案] A
[解析] k是n，r的公约数，则n＝kk1，r＝kk2，m＝nq＋r＝kk1q＋kk2＝(k1q＋k2)k，所以k是(k1q＋k2)k与kk1的公约数，即k一定是m，n的公约数．
4．如图所示的程序表示的算法是( )
A．交换m、n的值
B．辗转相除法
C．更相减损术
D．秦九韶算法
[答案] B
5．用辗转相除法求294和84的最大公约数时，需要做除法的次数是( )
A．1 B．2 C．3 D．4
[答案] B
[解析] ∵294＝84×3＋42,84＝42×2，∴选B.
6．运行下面的程序，当输入n＝840和m＝1764时，输出结果是( )
A．84
B．12
C．168
D．252
[答案] A
[解析] ∵1764＝840×2＋84,840＝84×10，
∴1764与840的最大公约数为84.
7．用更相减损术，求105与30的最大公约数时，需要做减法的次数是( )
A．2
B．3
C．4
D．5
[答案] C
[解析] 105－30＝75,75－30＝45,45－30＝15,30－15＝15.
8．用秦九韶算法求n次函数f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0在x＝x0时的值时，一个反复执行的步骤是( )
A.(k＝1,2，…，n)
B.(k＝1,2，…，n)
C.(k＝1,2，…，n)
D.(k＝1,2，…，n)
[答案] B
[解析] 由秦九韶算法的原理可知．
9．已知f(x)＝3x3＋2x2＋x＋4，则f(10)＝( )
A．3214
B．3210
C．2214
D．90
[答案] A
[解析] ∴答案A.
10．下图表示的程序框图是用秦九韶算法求多项式Pn(x)＝anxn＋an－1xn－1＋…＋a1x＋a0函数值的过程，则程序框图中①应为( )
A．i>n
B．iC．i≥n
D．i≤n
[答案] D
[解析] 本题是用秦九韶算法求多项式Pn(x)＝anxn＋an－1xn－1＋…＋a1x＋a0函数值的当型循环结构，最后一次应为i＝n，当i>n时应跳出循环，即不满足i≤n时跳出循环．
二、填空题
11．930与868的最大公约数是________．
[答案] 62
[解析] ∵930＝868×1＋62
868＝62×14
∴930与868的最大公约数为62.
12．用秦九韶算法计算f(x)＝3x4＋2x2＋x＋4当x＝10时的值的过程中，v1的值为________．
[答案] 30
[解析] 改写多项式为f(x)＝(((3x＋0)x＋2)x＋1)x＋4，则v0＝3，v1＝3×10＋0＝30.
13．阅读程序：
INPUT “m，n＝”；m，n
IF n>m THEN
t＝m
m＝n
n＝t
END IF[来源:学_
DO
r＝m MOD n
m＝n
n＝r
LOOP
UNTIL r＝0
PRINT m
END[]
若INPUT语句中输入m，n的数据分别是72,168，则程序运行的结果为________．
[答案] 24
[解析] 该程序是用辗转相除法求两个数的最大公约数的算法程序，输入72,168，即求它们的最大公约数，可求出它们的最大公约数为24.
14．用秦九韶算法求多项式f(x)＝7x5＋5x4＋10x3＋10x2＋5x＋1在x＝－2时的值：
①第一步，x＝－2.
第二步，f(x)＝7x5＋5x4＋10x3＋10x2＋5x＋1.
第三步，输出f(x)．
②第一步，x＝－2.
第二步，f(x)＝((((7x＋5)x＋10)x＋10)x＋5)x＋1.
第三步，输出f(x)．
③需要计算5次乘法，5次加法．
④需要计算9次乘法，5次加法．
以上说法中正确的是________(填序号)．
[答案] ②③
[解析] ①是直接求解，并不是秦九韶算法，故①错误，②正确．
对于一元最高次数是n的多项式，应用秦九韶算法需要运用n次乘法和n次加法，故③正确，④错误．
三、解答题
15．(1)用辗转相除法求840与1764的最大公约数．
(2)用更相减损术求459与357的最大公约数．
[解析] (1)1746＝840×2＋84
840＝84×10＋0
所以840与1764的最大公约数为84.
(2)459－357＝102
357－102＝255
255－102＝153
153－102＝51
102－51＝51
所以459与357的最大公约数为51.
16．用秦九韶算法求多项式f(x)＝x6－5x5＋6x4＋x2＋0.3x＋2当x＝－2时的值．
[解析] ∵f(x)＝x6－5x5＋6x4＋0·x3＋x2＋0.3x＋2
＝(((((x－5)x＋6)x＋0)x＋1)x＋0.3)x＋2
∴当x＝－2时，
v0＝1
v1＝－2－5＝－7
v2＝－7×(－2)＋6＝20
v3＝20×(－2)＋0＝－40
v4＝－40×(－2)＋1＝81
v5＝81×(－2)＋0.3＝－161.7[来源:
v6＝－161.7×(－2)＋2＝325.4[来源:学+
∴f(－2)＝325.4.
17．有甲、乙、丙三种溶液分别重147
g,343
g,133
g，现要将它们分别全部装入小瓶中，每个小瓶装入液体的质量相同，则每瓶最多装多少溶液？
[解析] 每个小瓶的溶液的质量应是三种溶液质量147,343,133的公约数，最大质量即是其最大公约数．
先求147与343的最大公约数：
343－147＝196，
196－147＝49，
147－49＝98.
98－49＝49.[来源:学
所以147与343的最大公约数是49.
再求49与133的最大公约数：
133－49＝84，
84－39＝35，
49－35＝14，
35－14＝21，
21－14＝7，
14－7＝7，所以49与133的最大公约数为7，
所以147,343,133的最大公约数为7.
即每瓶最多装7
g溶液．1.
3算法案例
【教学目标】：
1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。
2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。
【教学重难点】：
重点：理解辗转相除法与更相减损术求最大公约数的方法。
难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言。
【教学过程】：
情境导入：
1.教师首先提出问题：在初中，我们已经学过求最大公约数的知识，你能求出18与30的公约数吗？
2.接着教师进一步提出问题，我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数？这就是我们这一堂课所要探讨的内容。
新知探究：
1.辗转相除法
例1
求两个正数8251和6105的最大公约数。
（分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数）
解：8251＝6105×1＋2146
显然8251的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。
6105＝2146×2＋1813
2146＝1813×1＋333
1813＝333×5＋148
333＝148×2＋37
148＝37×4＋0
则37为8251与6105的最大公约数。
以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。利用辗转相除法求最大公约数的步骤如下：
第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；
第二步：若r0＝0，则n为m，n的最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1；
第三步：若r1＝0，则r1为m，n的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2；
……
依次计算直至rn＝0，此时所得到的rn-1即为所求的最大公约数。
练习：利用辗转相除法求两数4081与20723的最大公约数（答案：53）
2.更相减损术
我国早期也有解决求最大公约数问题的算法，就是更相减损术。
更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母·子之数，以少减多，更相减损，求其等也，以等数约之。
翻译出来为：
第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。
第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。
例2
用更相减损术求98与63的最大公约数.
解：由于63不是偶数，把98和63以大数减小数，并辗转相减，即：98－63＝35
63－35＝28
35－28＝7
28－7＝21
21－7＝14
14－7＝7
所以，98与63的最大公约数是7。
练习：用更相减损术求两个正数84与72的最大公约数。（答案：12）
比较辗转相除法与更相减损术的区别：
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到
3.
秦九韶算法
秦九韶计算多项式的方法
令，则有，
其中.这样，我们便可由依次求出；
显然，用秦九韶算法求n次多项式的值时只需要做n次乘法和n次加法运算
4.进位制
进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值.可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制.现在最常用的是十进制，通常使用10个阿拉伯数字0-9进行记数.
对于任何一个数，我们可以用不同的进位制来表示.比如：十进数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的.
表示各种进位制数一般在数字右下脚加注来表示,如111001(2)表示二进制数,34(5)表示5进制数.
（1）.k进制转换为十进制的方法：
，
（2）.十进制转化为k进制数b的步骤为：
第一步，将给定的十进制整数除以基数k，余数便是等值的k进制的最低位；
第二步，将上一步的商再除以基数k，余数便是等值的k进制数的次低位；
第三步，重复第二步，直到最后所得的商等于0为止，各次所得的余数，便是k进制各位的数，最后一次余数是最高位，即除k取余法.
要点诠释：
1、在k进制中，具有k个数字符号.如二进制有0，1两个数字.
2、在k进制中，由低位向高位是按“逢k进一”的规则进行计数.
3、非k进制数之间的转化一般应先转化成十进制，再将这个十进制数转化为另一种进制的数，有的也可以相互转化.
【反馈测评】：
1．求324、243、135这三个数的最大公约数。
求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大公约数的最大公约数即为所求。
2．用更相减损术求98与63的最大公约数
解：由于63不是偶数，把98和63以大数减小数，并辗转相减
98－63＝35
63－35＝28
35－28＝7
28－7＝21
21－7＝21
14－7＝7
所以，98和63的最大公约数等于7
3．已知一个五次多项式为用秦九韶算法求这个多项式当x
=
5的值。
解：将多项式变形：按由里到外的顺序，依此计算一次多项式当x
=
5时的值：
，，，
，所以，当x
=
5时，多项式的值等于17255.2
4．将二进制数110011(2)化成十进制数
解：根据进位制的定义可知
所以，110011（2）=51。
【板书设计】：
1.3算法案例
课前预习学案
一、预习目标
1、理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。
2、理解秦九韶算法的思想。
二、预习内容
什么是进位制？最常见的进位制是什么？除此之外还有哪些常见的进位制？请举例说明．
三、提出疑惑
思考：辗转相除法中的关键步骤是哪种逻辑结构？
课内探究学案
1、
学习目标
1.
会用辗转相除法与更相减损术求最大公约数的方法。
2.
会利用秦九韶算法求多项式的值。
3．各进位制之间能灵活转化。
二、学习重难点：
重点：辗转相除法与更相减损术求最大公约数的方法和秦九韶算法求多项式的值。
难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言。
3、
学习过程
辗转相除法思路：可以利用除法将大数化小,找两数的最大公约数.(适于两数较大时)
(1)用较大的数m除以较小的数n得到一个商和一个余数；
(2)若＝0,则n为m,n的最大公约数；若≠0,则用除数n除以余数得到一个
和一个余数；(3)若＝0,则为m,n的最大公约数;若≠0,则用除数除以余数得到一个商和一个余数；……依次计算直至＝0，此时所得到的即为所求的最大公约数.
例题1：求两个正数1424和801的最大公约数.
①以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法.
②由上述步骤可以看出，辗转相除法中的除法是一个反复执行的步骤，且执行次数由余数
是否等于0来决定,所以可把它看成一循环体,写出辗转相除法完整的程序框图和程序语言.
教学更相减损术：我国早期也有求最大公约数问题的算法，就是更相减损术.
在《九章算
术》中有更相减损术求最大公约数的步骤：可半者半之，不可半者，副置
分母 子之数，以少减多，更相减损，求其等也，以等数约之.
翻译为：(1)
任意给出两个正数；判断它们是否都是偶数.
若是，用2约简；若不是，执
行第二步.
(2)
以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小
数.
继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最
大公约数.
例题2.
用更相减损术求91和49的最大公约数.
秦九韶算法：
（1）设计求多项式当x=5时的值的算法，并写出程序。
（2）有没有更高效的算法？能否探求更好的算法，来解决任意多项式的求解问题？
引导学生把多项式变形为：
并提问：从内到外，如果把每一个括号都看成一个常数，那么变形后的式子中有哪些“一次式”？x的系数依次是什么？
用秦九韶算法求多项式的值，与多项式组成有直接关系吗？用秦九韶算法计算上述多项式的值，需要多少次乘法运算和多少次加法运算？秦九韶算法适用于一般的多项式的求值问题吗？
怎样用程序框图表示秦九韶算法？观察秦九韶算法的数学模型，计算时要用到的值，若令，我们可以得到下面的递推公式：
这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现。请画出程序框图。
例题3．已知一个五次多项式为用秦九韶算法求这个多项式当x
=
5的值。
进位制：
我们了解十进制吗？所谓的十进制，它是如何构成的？其它进位制的数又是如何的呢？
进位制是人们为了计数和运算方便而约定的记数系统。进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制。
例题4．将二进制数110011(2)化成十进制数
精讲点拨：
1．求两个正数8251和2146;228和1995;5280和12155的最大公约数.
2．
求两个正数8251和2146的最大公约数.
3.用秦九韶算法计算多项式
在x=-4时的值时,V3的值为
：
反思总结：
比较辗转相除法与更相减损术的区别
(1)都是求
的方法，计算上辗转相除法以
法为主，更相减损术以
法为主，计算次数上
法计算次数相对较少，特别当两个数字
时计算次数的区别较明显．
(2)从结果体现形式来看，辗转相除法体现结果是以
则得到，而更相减损术
则以
而得到．
(3)通过对秦九韶算法的学习，你对算法本身有哪些进一步认识？
(4)秦九韶算法在计算一个n次多项式的值时，只要做____次乘法运算和____次加法运算。
课后练习与提高
1、用“辗转相除法”求得459和357的最大公约数是：
A．3
B．9
C．17
D．51
2、将数转化为十进制数为：
A.
524
B.
774
C.
256
D.
260
3、用秦九韶算法计算多项式
当时的值时,需要做乘法和加法的次数分别是：
A.
6
,
6
B.
5
,
6
C.
5
,
5
D.
6
，5
参考答案:1D
2B
3A
小结
作业
五、反馈测评：
三、秦九韶算法
四、进位制
1.3算法案例
一、辗转相除法
例1
二、更相减损术
例2
PAGE
-
1
-辗转相除法与更相减损术
( http: / / www. )
一、三维目标
( http: / / www. )
（a）知识与技能
( http: / / www. )
1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。
( http: / / www. )
2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。
( http: / / www. )
（b）过程与方法
( http: / / www. )
在辗转相除法与更相减损术求最大公约数的学习过程中对比我们常见的约分求公因式的方法，比较它们在算法上的区别，并从程序的学习中体会数学的严谨，领会数学算法计算机处理的结合方式，初步掌握把数学算法转化成计算机语言的一般步骤。
( http: / / www. )
（c）情态与价值观
( http: / / www. )
1.通过阅读中国古代数学中的算法案例，体会中国古代数学对世界数学发展的贡献。
( http: / / www. )
2.在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能力，在利用算法解决数学问题的过程中培养理性的精神和动手实践的能力。
( http: / / www. )
二、教学重难点
( http: / / www. )
重点：理解辗转相除法与更相减损术求最大公约数的方法。
( http: / / www. )
难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言。
( http: / / www. )
三、教学设计
( http: / / www. )
（一）创设情景，揭示课题
( http: / / www. )
1.教师首先提出问题：在初中，我们已经学过求最大公约数的知识，你能求出18与30的公约数吗？
( http: / / www. )
2.接着教师进一步提出问题，我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数？这就是我们这一堂课所要探讨的内容。
( http: / / www. )
（二）研探新知
( http: / / www. )
1.辗转相除法
( http: / / www. )
例1
求两个正数8251和6105的最大公约数。
( http: / / www. )
解：8251＝6105×1＋2146
( http: / / www. )
显然8251的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。
( http: / / www. )
6105＝2146×2＋1813
2146＝1813×1＋333
( http: / / www. )
1813＝333×5＋148
333＝148×2＋37
( http: / / www. )
148＝37×4＋0
( http: / / www. )
则37为8251与6105的最大公约数。
( http: / / www. )
以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。利用辗转相除法求最大公约数的步骤如下：
( http: / / www. )
第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；
( http: / / www. )
第二步：若r0＝0，则n为m，n的最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1；
( http: / / www. )
第三步：若r1＝0，则r1为m，n的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2；
……
依次计算直至rn＝0，此时所得到的rn－1即为所求的最大公约数。
（1）辗转相除法的程序框图及程序
程序框图：（略）
程序：（当循环结构）
直到型结构见书37面。
INPUT
“m=”;m
INPUT
“n=”;n
IF
mTHEN
x=m
m=n
n=x
END
IF
r=m
MOD
n
WHILE
r<>0
r=m
MOD
n
m=n
n=r
WEND
PRINT
m
END
练习：利用辗转相除法求两数4081与20723的最大公约数（答案：53）
2.更相减损术
我国早期也有解决求最大公约数问题的算法，就是更相减损术。
更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母·子之数，以少减多，更相减损，求其等也，以等数约之。
翻译出来为：
第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。
第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。
例2
用更相减损术求98与63的最大公约数.
解：由于63不是偶数，把98和63以大数减小数，并辗转相减，即：98－63＝35
63－35＝28
35－28＝7
28－7＝21
21－7＝14
14－7＝7
所以，98与63的最大公约数是7。
练习：用更相减损术求两个正数84与72的最大公约数。（答案：12）
3.比较辗转相除法与更相减损术的区别
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到
5.课堂练习
一.用辗转相除法求下列各组数的最大公约数，并在自己编写的BASIC程序中验证。
（1）225；135
（2）98；196
（3）72；168
（4）153；119
6.小结：
辗转相除法与更相减损术求最大公约数的计算方法及完整算法程序的编写。
