高中数学 第一章 算法初步 13算法案例学案 新人教A版必修3.docx
《高中数学 第一章 算法初步 13算法案例学案 新人教A版必修3.docx》由会员分享，可在线阅读，更多相关《高中数学 第一章 算法初步 13算法案例学案 新人教A版必修3.docx（16页珍藏版）》请在冰点文库上搜索。
高中数学第一章算法初步13算法案例学案新人教A版必修3
1．3 算法案例
1．问题导航
（1）什么叫辗转相除法？
（2）什么叫更相减损术？
（3）辗转相除法与更相减损术的区别是什么？
（4）什么是秦九韶算法？
（5）学习了十进制，知道十进制是使用0～9十个数字，那么二进制、五进制、七进制分别使用哪些数字？
2．例题导读
通过对例1的学习，学会用更相减损术求最大公约数；
通过对例2的学习，学会用秦九韶算法求多项式的值；
通过对例3的学习，学会如何将二进制化为十进制；
通过对例4的学习，学会如何将k进制化为十进制；
通过对例5的学习，学会如何将十进制化为二进制；
通过对例6的学习，学会十进制化为k进制的方法：
即“除k取余法”（k∈N，2≤k≤9）．
1．辗转相除法与更相减损术
（1）辗转相除法：
又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法．
（2）更相减损术：
我国古代数学专著《九章算术》中介绍的一种求两个正整数的最大公约数的算法．
2．秦九韶算法
功能
它是一种用于计算一元n次多项式的值的方法
改写后的形式
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
计算方法
从括号最内层开始，由内向外逐层计算
v1＝anx＋an－1，
v2＝v1x＋an－2，
v3＝v2x＋an－3，
vn＝vn－1x＋a0，
…
这样，求n次多项式f（x）的值就转化为求n个一次多项式的值.
3.进位制
（1）进位制
进位制是人们为了计数和运算方便而约定的记数系统，“满几进一”就是几进制，几进制的基数就是几．
（2）其他进位制与十进制间的转化
①其他进位制化成十进制
其他进位制的数化成十进制时，表示成不同位上数字与基数的幂的乘积之和的形式．
②十进制化成k进制的方法——“除k取余法”．
1．用更相减损术求294和84的最大公约数时，需做减法运算的次数是（ ）
A．2 B．3
C．4D．5
解析：
选C.294－84＝210，210－84＝126，126－84＝42，84－42＝42，共做4次减法运算．
2．用秦九韶算法计算多项式f（x）＝3x6＋4x5＋5x4＋6x3＋7x2＋8x＋1当x＝0.4时的值时，需要做乘法和加法的次数分别是（ ）
A．6，6B．5，6
C．5，5D．6，5
答案：
A
3．完成下列进位制之间的转化．
（1）1034（7）＝________（10）；
（2）119（10）＝________（6）．
解析：
（1）1034（7）＝1×73＋0×72＋3×7＋4×70＝368.
（2）
∴119（10）＝315（6）．
答案：
（1）368
（2）315
4．当所给的多项式按x的降幂排列“缺项”时，用秦九韶算法改写多项式时，应注意什么？
解：
所缺的项写成系数为零的形式，即写成0·xn的形式．
1．对于任何一个数，我们可以用不同的进位制来表示．
2．表示各种进位制数一般在数字右下角加注来表示，如111001
（2）表示二进制数，34（5）表示5进制数．
3．电子计算机一般都使用二进制．
4．利用除k取余法，可以把任何一个十进制数化为k进制数，并且操作简单、实用．
5．通过k进制数与十进制数的转化，我们也可以将一个k进制数转化为另一个不同基数的M进制数．
6．利用秦九韶算法可以减少计算次数提高计算效率．
求最大公约数
用辗转相除法求612与468的最大公约数，并用更相减损术检验所得结果．
（链接教材P36例1）
[解] 用辗转相除法：
612＝468×1＋144，468＝144×3＋36，144＝36×4，
即612和468的最大公约数是36.
用更相减损术检验：
612和468为偶数，两次用2约简得153和117，153－117＝36，117－36＝81，81－36＝45，45－36＝9，36－9＝27，27－9＝18，18－9＝9，
所以612和468的最大公约数为9×2×2＝36.
方法归纳
（1）利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．
（2）利用更相减损术求两个正整数的最大公约数的一般步骤是：
首先判断两个正整数是否都是偶数．若是，用2约简，也可以不除以2，直接求最大公约数，这样不影响最后结果．
1．
（1）1624与899的最大公约数是________．
解析：
1624＝899×1＋725，
899＝725×1＋174，
725＝174×4＋29，
174＝29×6，
故1624与899的最大公约数是29.
答案：
29
（2）用辗转相除法求80和36的最大公约数，并用更相减损术检验所得结果．
解：
辗转相除法：
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.
秦九韶算法及其应用
（2015·福州高一检测）用秦九韶算法写出当x＝3时f（x）＝2x5－4x3＋3x2－5x＋1的值．
[解] ∵f（x）＝（（（（2x＋0）x－4）x＋3）x－5）x＋1，
v0＝2，
v1＝2×3＋0＝6，
v2＝6×3－4＝14，
v3＝14×3＋3＝45，
v4＝45×3－5＝130，
v5＝130×3＋1＝391，
所以f（3）＝391.
方法归纳
利用秦九韶算法将f（x）改写成如下形式f（x）＝（…（（anx＋an－1）x＋an－2）x＋…＋a1）x＋a0，其计算步骤为：
先计算v1＝anx＋an－1，再计算v2＝v1x＋an－2，每次都是把上一次的结果乘以x再与下一个系数相加，其计算量为乘法n次，加法n次．
2．利用秦九韶算法求多项式f（x）＝3x6＋12x5＋8x4－3.5x3＋7.2x2＋5x－13当x＝6时的值，写出详细步骤．
解：
f（x）＝（（（（（3x＋12）x＋8）x－3.5）x＋7.2）x＋5）x－13.
v0＝3，
v1＝v0×6＋12＝30，
v2＝v1×6＋8＝188，
v3＝v2×6－3.5＝1124.5，
v4＝v3×6＋7.2＝6754.2，
v5＝v4×6＋5＝40530.2，
v6＝v5×6－13＝243168.2.
所以f（6）＝243168.2.
进位制
（1）把二进制数101101
（2）化为十进制数；
（2）把十进制数458转化为四进制数．
（链接教材P41例3、例4）
[解]
（1）101101
（2）＝1×25＋0×24＋1×23＋1×22＋0×21＋1×20＝32＋8＋4＋1＝45，
所以二进制数101101
（2）转化为十进制数为45.
（2）
458＝13022（4）．
[互动探究] 将本例
（1）中的二进制数101101
（2）转化为三进制数．
解：
101101
（2）＝1×25＋0×24＋1×23＋1×22＋0×21＋1×20＝45，
∴45＝1200（3），∴101101
（2）＝1200（3）．
方法归纳
（1）将k进制转化为十进制的方法是：
先将这个k进制数写成各个数位上的数字与k的幂的乘积之和的形式，再按照十进制的运算规则计算出结果．
（2）十进制转化为k进制，采用除k取余法，也就是除基数，倒取余．
3．
（1）二进制数算式1010
（2）＋10
（2）的值是（ ）
A．1011
（2）B．1100
（2）
C．1101
（2）D．1000
（2）
解析：
选B.二进制数的加法是逢二进一，所以选B.
（2）下列各组数中最小的数是（ ）
A．1111
（2）B．210（6）
C．1000（4）D．101（8）
解析：
选A.统一化为十进制数为1111
（2）＝15；210（6）＝78；1000（4）＝64；101（8）＝65.
易错警示
因忽略零系数项而致误
利用秦九韶算法求多项式f（x）＝x6－5x5＋6x4＋x2＋3x＋2当x＝－2时的值为（ ）
A．320B．－160
C．－320D．300
[解析] 将多项式变式为f（x）＝（（（（（x－5）x＋6）x＋0）x＋1）x＋3）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）＋3＝－159，v6＝－159×（－2）＋2＝320.
[答案] A
[错因与防范]
（1）考虑x＝－2而认为多项式的值为负值．
（2）易忽略多项式中系数为0的项，致使多项式改写不正确．
（3）解题时注意多项式变形后有几次乘法和几次加法．
（4）要注意所给多项式的项数，特别是系数为0的项．
4．
（1）用秦九韶算法计算多项式f（x）＝12＋35x－8x2＋6x4＋5x5＋3x6在x＝－4时的值时，v3的值为（ ）
A．－144B．－136
C．－57D．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.
（2）已知多项式f（x）＝3x5＋8x4－3x3＋5x2＋12x－6，则f
（2）＝________．
解析：
根据秦九韶算法，把多项式改写成如下形式：
f（x）＝（（（（3x＋8）x－3）x＋5）x＋12）x－6.
按照从内到外的顺序，依次计算一次多项式当x＝2时的值．
v0＝3，
v1＝3×2＋8＝14，
v2＝14×2－3＝25，
v3＝25×2＋5＝55，
v4＝55×2＋12＝122，
v5＝122×2－6＝238，
所以当x＝2时，多项式的值为238.
答案：
238
1．下列关于利用更相减损术求156和72的最大公约数的说法中正确的是（ ）
A．都是偶数必须约简
B．可以约简，也可以不约简
C．第一步作差为156－72＝84；第二步作差为72－84＝－12
D．以上都不对
解析：
选B.约简是为了使运算更加简捷，故不一定要约简，A错．C中第二步应为84－72＝12，故选B.
2．用辗转相除法计算294与84的最大公约数时，需要做的除法次数是（ ）
A．1B．2
C．3D．4
解析：
选B.294＝84×3＋42，84＝42×2，至此公约数已求出．
3．二进制数1101111
（2）化成十进制数是________．
解析：
1101111
（2）＝1×20＋1×21＋1×22＋1×23＋0×24＋1×25＋1×26＝111.
答案：
111
4．若k进制数123（k）与十进制数38相等，则k＝________．
解析：
由k进制数123可知k≥4.
下面可用验证法：
若k＝4，则38（10）＝212（4），不合题意；
若k＝5，则38（10）＝123（5）成立，所以k＝5.
答案：
5
[A.基础达标]
1.45和150的最大公约数和最小公倍数分别是（ ）
A．5，150 B．15，450
C．450，15D．15，150
解析：
选B.利用辗转相除法求45和150的最大公约数：
150＝45×3＋15，45＝15×3，45和150的最大公约数为15.45和150的最小公倍数为15×（45÷15）×（150÷15）＝450，故选B.
2．把67化为二进制数为（ ）
A．1100001
（2）B．1000011
（2）
C．110000
（2）D．1000111
（2）
解析：
选B.
∴把67化为二进制数为1000011
（2）．
3．（2015·三明高一检测）计算机中常用十六进制，采用数字0～9和字母A～F共16个计算符号与十进制的对应关系如下表：
十六进制
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
十进制
例如用十六进制表示D＋E＝1B，则（2×F＋1）×4＝（ ）
A．6EB．7C
C．5FD．B0
解析：
选B.（2×F＋1）×4用十进制可以表示为（2×15＋1）×4＝124，而124＝16×7＋12，所以用十六进制表示为7C，故选B.
4.若用秦九韶算法求多项式f（x）＝4x5－x2＋2当x＝3时的值，则需要做乘法运算和加减法运算的次数分别为（ ）
A．4，2B．5，3
C．5，2D．6，2
解析：
选C.f（x）＝4x5－x2＋2＝（（（（4x）x）x－1）x）x＋2，所以需要做5次乘法运算和2次加减运算．
5.（2015·青海调研）已知一个k进制的数132与十进制的数30相等，那么k等于（ ）
A．7或4B．－7
C．4D．都不对
解析：
选C.132（k）＝1×k2＋3×k＋2＝k2＋3k＋2，
∴k2＋3k＋2＝30，即k2＋3k－28＝0，
解得k＝4或k＝－7（舍去）．
6.三个数72，120，168的最大公约数是________．
解析：
由更相减损术，得
168－120＝48，120－48＝72，72－48＝24，48－24＝24，
故120和168的最大公约数是24.
而72－24＝48，48－24＝24，
故72和24的最大公约数也是24，
所以72，120，168的最大公约数是24.
答案：
24
7.（2015·莱芜质检）已知函数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.
答案：
756
8.（2015·福州高一检测）三进制数2022（3）化为六进制数为abc（6），则a＋b＋c＝________．
解析：
2022（3）＝2×33＋0×32＋2×31＋2×30＝62.
三进制数2022（3）化为六进制数为142（6），
∴a＋b＋c＝7.
答案：
7
9.已知函数f（x）＝x3－3x2－4x＋5，试用秦九韶算法求f
（2）的值．
解：
根据秦九韶算法，把多项式改写成如下形式：
f（x）＝x3－3x2－4x＋5
＝（x2－3x－4）x＋5
＝（（x－3）x－4）x＋5.
把x＝2代入函数式得
f
（2）＝（（2－3）×2－4）×2＋5＝－7.
10.古时候，当边境有敌人来犯时，守边的官兵通过在烽火台上点火向境内报告来犯敌人数，如图所示，烽火台上点火表示数字1，未点火表示数字0，约定二进制数对应的十进制数的单位是1000，请你计算一下，这组烽火台表示有多少敌人入侵？
解：
由题图可知这组烽火台表示的二进制数为11011
（2），它表示的十进制数为11011
（2）＝1×24＋1×23＋0×22＋1×21＋1×20＝27，由于约定二进制数对应的十进制数的单位是1000，所以入侵的敌人的数目为27×1000＝27000（人）．
[B.能力提升]
1．将十进制数389化成四进制数的末位是（ ）
A．1B．2
C．3D．0
解析：
选A.389＝4×97＋1，即第一次用389除以4余1，而这就是最后一位数字．
2．（2015·盐城质检）m是一个正整数，对于两个正整数a，b，如果a－b是m的倍数，则称a，b对模m同余，用符号a≡b（Modm）表示，则下列各式中不正确的为（ ）
A．12≡7（Mod5）B．21≡10（Mod3）
C．34≡20（Mod2）D．47≡7（Mod40）
解析：
选B.逐一验证，对于A，12－7＝5是5的倍数；对于B，21－10＝11不是3的倍数；对于C，34－20＝14是2的倍数；对于D，47－7＝40是40的倍数，故选B.
3．324，243，135三个数的最大公约数是________．
解析：
324＝243×1＋81，
243＝81×3，
所以243与324的最大公约数是81.
又135＝81×1＋54，
81＝54×1＋27，
54＝27×2＋0，
所以135与81的最大公约数是27.
答案：
27
4.在计算机的运行过程中，常常要进行二进制数与十进制数的转换与计算．如十进制数8转换成二进制数是1000，记作8（10）＝1000
（2）；二进制数111转换成十进制数是7，记作111
（2）＝7（10）等．二进制的四则运算，如11
（2）＋101
（2）＝1000
（2）．请计算：
11
（2）×111
（2）＝________，10101
（2）＋1111
（2）＝________．
解析：
由题可知，在二进制数中的运算规律是“满二进一”，
∴11
（2）×111
（2）＝10101
（2），
10101
（2）＋1111
（2）＝100100
（2）．
答案：
10101
（2） 100100
（2）
5．有甲、乙、丙三种溶液分别重147g、343g、133g，现要将它们分别全部装入小瓶中，每个小瓶装入液体的质量相同，问每瓶最多装多少？
解：
先求147与343的最大公约数．
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.
所以每瓶最多装7g.
6．（选做题）已知175（r）＝125（10），求在这种进制里的数76（r）应记成十进制的什么数？
解：
∵1×r2＋7×r1＋5×r0＝125，
∴r2＋7r－120＝0，
∴r＝8或r＝－15（舍去），
∴r＝8.
76（r）＝76（8）＝7×81＋6×80＝62（10）．
升级会员 