课件48张PPT。第一章 算法初步1.3 算法案例两个正整数的最大公约数 欧几里得算法 较大的数 较小的数 余数和较小的数 较小的数 《九章算术》 2 减去 相等 乘积 最内层 由内向外 计数 运算方便 k进制 k 各位上的数字与k的幂的乘积之和 按照十进制数的运算规则计算出结果 除k取余法 用k连续去除十进制数所得的商 把各步得到的余数倒排写出 求最大公约数 秦九韶算法 进位制及其转化 点击右图进入…Thank you for watching !1.3 算法案例
学 习 目 标
核 心 素 养
1.会用辗转相除法与更相减损术求两数的最大公约数．(重点、易混点)
2．会用秦九韶算法求多项式的值．(重点)
3．会在不同进位制间进行相互转化．(难点)
1.通过古代传统算法，培养数学运算素养．
2．借助算法案例，提升逻辑推理素养.
1．辗转相除法与更相减损术
(1)辗转相除法
①辗转相除法是用于求两个正整数的最大公约数的一种算法，这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫欧几里得算法．
②所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数．若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数．
(2)更相减损术
更相减损术是我国古代数学专著《九章算术》中介绍的一种求两数最大公约数的方法．其基本过程是：第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数或这个数与约简的数的乘积就是所求的最大公约数．
2．秦九韶算法
把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如下形式：f(x)＝(…((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)的值的方法叫秦九韶算法．
3．进位制
(1)进位制是人们为了计数和运算方便而约定的记数系统．“满k进一”就是k进制，k进制的基数是 k．
(2)将k进制数化为十进制数的方法是：先把k进制数写成各位上的数字与k的幂的乘积之和的形式，再按照十进制数的运算规则计算出结果．
(3)将十进制数化为k进制数方法是：除k取余法．即用k连续去除十进制数所得的商，直到商为零为止，然后把各步得到的余数倒排写出．就是相应的k进制数．
1．在对16和12求最大公约数时，整个操作如下：16－12＝4，12－4＝8，8－4＝4.由此可以看出12和16的最大公约数是( )
A．4 B．12
C．16 D．8
A [根据更相减损术的方法判断．]
2．下列有可能是4进制数的是( )
A．5123 B．6542
C．3103 D．4312
C [4进制中逢4进1，每位上的数字一定小于4.]
3．已知多项式f(x)＝4x5＋3x4＋2x3－x2－x－，用秦九韶算法求f(－2)等于( )
A．－ B．
C． D．－
A [∵f(x)＝((((4x＋3)x＋2)x－1)x－1)x－，
∴f(－2)＝－.]
4．利用辗转相除法求3 869与6 497的最大公约数时，第二步是________
3 869＝2 628×1＋1 241 [第一步应为6 497＝3 869×1＋2 628；
第二步应为3 869＝2 628×1＋1 241.]
求最大公约数
【例1】 求228与1995的最大公约数．
思路点拨：求两个正整数的最大公约数可以用辗转相除法，也可以用更相减损术．
[解] 法一：(辗转相除法)1 995＝8×228＋171，228＝1×171＋57，171＝3×57，
所以228与1 995的最大公约数为57.
法二：(更相减损术)1 995－228＝1 767，1 767－228＝1 539，
1 539－228＝1 311，1 311－228＝1 083，
1 083－228＝855，855－228＝627，
627－228＝399，399－228＝171，
228－171＝57，171－57＝114，
114－57＝57.
所以228与1 995的最大公约数为57.
求最大公约数的两种方法
(1)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．
(2)利用更相减损术求两个正整数的最大公约数的一般步骤是：第一步判断两个正整数是否都是偶数，若是，用2约简，也可以不除以2，直接求最大公约数，这样不影响最后结果．第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．
1．用辗转相除法和更相减损术求1 515与600的最大公约数，需要运算的次数分别为( )
A．4，15 B．5，14
C．5，13 D．4，12
B [辗转相除法：1 515＝600×2＋315；600＝315×1＋285，315＝285×1＋30，285＝30×9＋15，30＝15×2，故最大公约数为15，且需计算5次．
用更相减损术：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.故最大公约数为15，且需计算14次．]
秦九韶算法
【例2】 已知一个5次多项式为f(x)＝4x5＋2x4＋3.5x3－2.6x2＋1.7x－0.8，用秦九韶算法求这个多项式当x＝5时的值．
思路点拨：可根据秦九韶算法的原理，将所给的多项式改写，然后由内到外逐次计算．
[解] 将f(x)改写为f(x)＝((((4x＋2)x＋3.5)x－2.6)x＋1.7)x－0.8，
由内向外依次计算一次多项式，当x＝5时的值：
v0＝4；
v1＝4×5＋2＝22；
v2＝22×5＋3.5＝113.5；
v3＝113.5×5－2.6＝564.9；
v4＝564.9×5＋1.7＝2 826.2；
v5＝2 826.2×5－0.8＝14 130.2.
所以当x＝5时，多项式的值等于14 130.2.]
利用秦九韶算法求多项式的值的步骤
2．用秦九韶算法计算多项式f(x)＝12＋35x－8x2＋6x4＋5x5＋3x6在x＝－4时，v3的值为( )
A．－144 B．－136
C．－57 D．34
B [根据秦九韶算法多项式可化为f(x)＝(((((3x＋5)x＋6)x＋0)x－8)x＋35)x＋12.
由内向外计算v0＝3；
v1＝3×(－4)＋5＝－7；
v2＝－7×(－4)＋6＝34；
v3＝34×(－4)＋0＝－136.]
进位制及其转化
[探究问题]
1．数学上通常使用什么进位制？它的原理是什么？
[提示] 十进制
十进制的原理是满十进一．一个十进制正整数N可以写成an·10n＋an－1·10n－1＋…＋a1·101＋a0·100的形式，其中an，an－1，…，a1，a0都是0至9中的数字，且an≠0.例如365＝3×102＋6×10＋5.
2．你还知道哪些进位制？它们与目前我们使用的进位制数之间能否转化？
[提示] (1)二进制使用0和1这两个数字，基数为2.
(2)八进制使用0，1，2，3，4，5，6，7这八个数字，基数为8.
(3)十六进制使用0，1，2，3，4，5，6，7，8，9，A，B，C，D，E，F这十六个符号，基数为16.其中A，B，C，D，E，F分别相当于十进制中的10，11，12，13，14，15.
它们与十进位制数之间可以转化，两个非十进制数之间也可以以十进制作“桥梁”，进行相互转化．
3．不同的进位制数如何区分？
[提示] 一般地，k进制数的原理是满k进一，k进制数一般在右下角处标注(k)，以示区别．例如270(8)表示270是一个8进制数．但十进制一般省略不写．
【例3】 把“五进制”数1 234(5)转化为“十进制”数，再把它转化为“八进制”数．
思路点拨：k进制化十进制时，利用求各位上的数与k的幂的乘积后再相加的方法，十进制化为其他进制可采用除k取余法．
[解] ∵1 234(5)＝1×53＋2×52＋3×51＋4×50＝194，而
∴1 234(5)＝194＝302(8)．
1．(变条件)210(6)化成十进制数为________．
85化成七进制数为________．
78 151(7) [210(6)＝2×62＋1×6＝78，
所以85＝151(7)．]
2．(变结论)把1234(5)化成七进制数为________．
365(7) [∵1234(5)＝1×53＋2×52＋3×51＋4×50＝194.而
∴1 234(5)＝194＝365(7)]
进位制的转换方法
1．要把k进制数化为十进制数，首先把k进制数表示成不同位上数字与k的幂的乘积之和，其次按照十进制的运算规则计算和．
2．十进制数化为k进制数(除k取余法)的步骤
1．求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相减损术．用辗转相除法，即根据a＝nb＋r这个式子，反复相除，直到r＝0为止；用更相减损术，即根据r＝|a－b|这个式子，反复相减，直到r＝0为止．
2．秦九韶算法的关键在于把n次多项式转化为一次多项式，注意体会递推的实现过程，实施运算时要由内向外，一步一步执行．
3．把一个非十进制数转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除k取余法，把十进制数转化为k进制数．而在使用除k取余法时要注意以下几点：(1)必须除到所得的商是0为止；(2)各步所得的余数必须从下到上排列；(3)切记在所求数的右下角标明基数．
1．判断下列结论的正误(正确的打“√”，错误的打“×”)
(1)用辗转相除法与更相减损术都可以求两个正整数的最大公约数． ( )
(2)秦九韶算法的优点是减少了乘法运算的次数，提高了运算效率． ( )
(3)不同进位制中，十进制的数比二进制的数大． ( )
[答案] (1)√ (2)√ (3)×
2．用辗转相除法求72与120的最大公约数时，需要做除法次数为( )
A．4 B．3
C．5 D．6
B [120＝72×1＋48，72＝48×1＋24，48＝24×2.]
3．将八进制数123(8)化为十进制数，结果为________．
83 [1×82＋2×81＋3×80＝64＋16＋3＝83.]
4．用秦九韶算法求多项式f(x)＝8x7＋5x6＋3x4＋2x＋1，当x＝2时的值．
[解] 根据秦九韶算法，把多项式改写成如下形式：
f(x)＝8x7＋5x6＋0·x5＋3·x4＋0·x3＋0·x2＋2x＋1＝((((((8x＋5)x＋0)x＋3)x＋0)x＋0)x＋2)x＋1.
而x＝2，所以有v0＝8，
v1＝8×2＋5＝21，
v2＝21×2＋0＝42，
v3＝42×2＋3＝87，
v4＝87×2＋0＝174，
v5＝174×2＋0＝348，
v6＝348×2＋2＝698，
v7＝698×2＋1＝1 397.
所以当x＝2时，多项式的值为1 397.
课时分层作业(八) 算法案例
(建议用时：60分钟)
[基础达标练]
一、选择题
1．把67化为二进制数为( )
A．1 100 001(2) B．1 000 011(2)
C．110 000(2) D．1 000 111(2)
B [利用除2取余法可得相应的除法算式如图，故67＝1 000 011(2)．]
2．下列关于利用更相减损术求156和72的最大公约数的说法中正确的是( )
A．都是偶数必须约简
B．可以约简，也可以不约简
C．第一步作差为156－72＝84；第二步作差为72－84＝－12
D．以上都不对
B [利用更相减损术求解两偶数的最大公约数时，约简是为了使运算更简捷，并非必须约简，A错，B对；C中第二步应为84－72＝12，故C错；D不对．]
3．用秦九韶算法求多项式f(x)＝7x6＋6x5＋3x2＋2当x＝4时的值时，先算的是( )
A．4×4 B．7×4
C．4×4×4 D．7×4＋6
D [∵f(x)＝(((((7x＋6)x＋0)x＋0)x＋3)x＋0)x＋2.根据由内到外的运算顺序，结合题目知，应先算7×4＋6.]
4．三位四进制数中的最大数等于十进制数的( )
A．63 B．83
C．189 D．252
A [根据进位制的原理知四进制使用0，1，2，3这四个数字，基数为4，所以三位四进制数中的最大数为333(4)，则333(4)＝3×42＋3×41＋3＝63.]
5．用秦九韶算法计算f(x)＝6x5－4x4＋x3－2x2－9x，需要加法(或减法)与乘法运算的次数分别为( )
A．5，4 B．5，5
C．4，4 D．4，5
D [n次多项式需进行n次乘法；若各项均不为零，则需进行n次加法，缺一项就减少一次加法运算．f(x)中无常数项，故加法次数要减少一次，为5－1＝4.故选D.]
二、填空题
6．1037与425的最大公约数是________．
17 [∵1037＝425×2＋187，425＝187×2＋51，187＝51×3＋34，51＝34×1＋17，34＝17×2.故1037与425的最大公约数是17.]
7．将三进制数2022(3)化为六进制数abc(6)，则a＋b＋c＝________．
7 [2022(3)＝2×33＋0×32＋2×31＋2×30＝62，
所以将2022(3)化为六进制数为142(6)，故a＋b＋c＝7.]
8．用秦九韶算法求多项式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次加法，故③正确，④错误．]
三、解答题
9．用两种方法术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.
10．若二进制数10b1(2)和三进制数a02(3)相等，求正整数a、b.
[解] ∵10b1(2)＝1×23＋b×2＋1＝2b＋9，
a02(3)＝a×32＋2＝9a＋2
∴2b＋9＝9a＋2，即9a－2b＝7
又∵a∈{1，2}、b∈{0，1}
∴只有当a＝1，b＝1时符合．
[能力提升练]
1．计算机中常用的十六进制是逢16进1的计数制，采用数字0～9和字母A～F共16个计数符号，这些符号与十进制数的对应关系如下表：
十六进制
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
十进制
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
例如，用十六进制表示：E＋D＝1B，则A×B等于( )
A．6E B．72
C．5F D．B0
A [A×B用十进制表示10×11＝110，而110＝6×16＋14，所以用16进制表示6E.]
2．运行下面的程序，当输入的数据为78，36时，输出的结果为( )
A．24 B．18
C．12 D．6
D [由程序语句，知此程序是用更相减损术求输入的两个不同正整数的最大公约数．因为78－36＝42，42－36＝6，36－6＝30，30－6＝24，24－6＝18，18－6＝12，12－6＝6，所以78和36的最大公约数为6，所以输出的结果为6，故选D.]
3．若k进制数123(k)与十进制数38相等，则k＝________．
5 [由k进制数123知k≥4，可以用验证法求[解] 若k＝4，则38(10)＝212(4)不成立；若k＝5，则38(10)＝123(5)成立，所以k＝5.或者由123(k)＝1×k2＋2×k＋3＝k2＋2k＋3＝38，得k2＋2k－35＝0.∴k＝5或k＝－7(舍去)．]
4．中国古代有计算多项式值的秦九韶算法，如图是实现该算法的程序框图．执行该程序框图，若输入的x＝2，n＝2，依次输入的a为2，2，5，则输出的s＝________．
17 [由秦九韶算法的意义可知s＝f(x)＝((0×x＋2)x＋2)x＋5＝2x2＋2x＋5.故输出s＝f(2)＝17.]
5．用秦九韶算法，判断函数f(x)＝5x7＋x6－x3＋x＋3在区间[－1，0]内是否有零点．
[解] 根据秦九韶算法，把多项式改写成如下形式：
f(x)＝5x7＋x6－x3＋x＋3＝((((((5x＋1)x＋0)x＋0)x－1)x＋0)x＋1)x＋3.
当x＝－1时，v0＝5，
v1＝5×(－1)＋1＝－4，
v2＝－4×(－1)＋0＝4，
v3＝4×(－1)＋0＝－4，
v4＝－4×(－1)－1＝3，
v5＝3×(－1)＋0＝－3，
v6＝－3×(－1)＋1＝4，
v7＝4×(－1)＋3＝－1，
∴f(－1)＝－1.
又f(0)＝3，∴f(0)f(－1)<0，
由零点存在性定理，知函数f(x)在区间[－1，0]内有零点．
