1.3 算法案例
图片预览
文档简介
课件34张PPT。1．3 算法案例第一章 算法初步2．例题导读
通过对例1的学习，学会用更相减损术求最大公约数；
通过对例2的学习，学会用秦九韶算法求多项式的值；
通过对例3的学习，学会如何将二进制化为十进制；
通过对例4的学习，学会如何将k进制化为十进制；
通过对例5的学习，学会如何将十进制化为二进制；
通过对例6的学习，学会十进制化为k进制的方法：即“除k取余法”(k∈N，2≤k≤9)．1．辗转相除法与更相减损术
(1)辗转相除法：又叫欧几里得算法，是一种求两个正整数的____________的古老而有效的算法．
(2)更相减损术：我国古代数学专著《九章算术》中介绍的一种求两个正整数的____________的算法．最大公约数最大公约数2．秦九韶算法一元n次多项式(anxn－1＋an－1xn－2＋…＋a1)x＋a0(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0v2x＋an－3n个一次多项式3.进位制
(1)进位制
进位制是人们为了____________和____________方便而约定的记数系统，“满几进一”就是__________制，__________制的基数就是____________．
(2)其他进位制与十进制间的转化
①其他进位制化成十进制
其他进位制的数化成十进制时，表示成_________________
______________________的形式．
②十进制化成k进制的方法——“____________”．计数运算几进几几进基数的幂的乘积之和除k取余法不同位上数字与1．用更相减损术求294和84的最大公约数时，需做减法运算的次数是( )
A．2 B．3
C．4 D．5
解析：294－84＝210，210－84＝126，126－84＝42，84－42＝42，共做4次减法运算．C2．用秦九韶算法计算多项式f(x)＝3x6＋4x5＋5x4＋6x3＋7x2＋8x＋1当x＝0.4时的值时，需要做乘法和加法的次数分别是
( )
A．6，6 B．5，6
C．5，5 D．6，5A3．完成下列进位制之间的转化．
(1)1 034(7)＝________(10)；
(2)119(10)＝________(6)．3683154．当所给的多项式按x的降幂排列“缺项”时，用秦九韶算法改写多项式时，应注意什么？
解：所缺的项写成系数为零的形式，即写成0·xn的形式．1．对于任何一个数，我们可以用不同的进位制来表示．
2．表示各种进位制数一般在数字右下角加注来表示,如111 001(2)表示二进制数，34(5)表示5进制数．
3．电子计算机一般都使用二进制．
4．利用除k取余法，可以把任何一个十进制数化为k进制数，并且操作简单、实用．
5．通过k进制数与十进制数的转化，我们也可以将一个k进制数转化为另一个不同基数的M进制数．
6．利用秦九韶算法可以减少计算次数提高计算效率．求最大公约数1．(1)1 624与899的最大公约数是________．
解析：1 624＝899×1＋725，
899＝725×1＋174，
725＝174×4＋29，
174＝29×6，
故1 624与899的最大公约数是29.29(2)用辗转相除法求80和36的最大公约数，并用更相减损术检验所得结果．
秦九韶算法及其应用[解] ∵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.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＝1 124.5，
v4＝v3×6＋7.2＝6 754.2，
v5＝v4×6＋5＝40 530.2，
v6＝v5×6－13＝243 168.2.
所以f(6)＝243 168.2.进位制[互动探究] 将本例(1)中的二进制数101 101(2)转化为三进制数．3．(1)二进制数算式1 010(2)＋10(2)的值是( )
A．1 011(2) B．1 100(2)
C．1 101(2) D．1 000(2)
解析：二进制数的加法是逢二进一，所以选B.
(2)下列各组数中最小的数是( )
A．1 111(2) B．210(6)
C．1 000(4) D．101(8)
解析：统一化为十进制数为1 111(2)＝15；210(6)＝78；1 000(4)＝64；101(8)＝65.BAA[解析] 将多项式变式为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.
[错因与防范]
(1)考虑x＝－2而认为多项式的值为负值．
(2)易忽略多项式中系数为0的项，致使多项式改写不正确．
(3)解题时注意多项式变形后有几次乘法和几次加法．
(4)要注意所给多项式的项数，特别是系数为0的项．4．(1)用秦九韶算法计算多项式f(x)＝12＋35x－8x2＋6x4＋5x5＋3x6在x＝－4时的值时，v3的值为( )
A．－144 B．－136
C．－57 D．34
解析：根据秦九韶算法多项式可化为
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.B(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.2381．下列关于利用更相减损术求156和72的最大公约数的说法中正确的是( )
A．都是偶数必须约简
B．可以约简，也可以不约简
C．第一步作差为156－72＝84；第二步作差为72－84＝－12
D．以上都不对
解析：约简是为了使运算更加简捷，故不一定要约简，A错．C中第二步应为84－72＝12，故选B.B2．用辗转相除法计算294与84的最大公约数时，需要做的除法次数是( )
A．1 B．2
C．3 D．4
解析：294＝84×3＋42，84＝42×2，至此公约数已求出．
3．二进制数1 101 111(2)化成十进制数是________．
解析：1 101 111(2)＝1×20＋1×21＋1×22＋1×23＋0×24＋1×25＋1×26＝111.B1114．若k进制数123(k)与十进制数38相等，则k＝________．
解析：由k进制数123可知k≥4.
下面可用验证法：
若k＝4，则38(10)＝212(4)，不合题意；
若k＝5，则38(10)＝123(5)成立，所以k＝5.5本部分内容讲解结束按ESC键退出全屏播放
通过对例1的学习，学会用更相减损术求最大公约数；
通过对例2的学习，学会用秦九韶算法求多项式的值；
通过对例3的学习，学会如何将二进制化为十进制；
通过对例4的学习，学会如何将k进制化为十进制；
通过对例5的学习，学会如何将十进制化为二进制；
通过对例6的学习，学会十进制化为k进制的方法：即“除k取余法”(k∈N，2≤k≤9)．1．辗转相除法与更相减损术
(1)辗转相除法：又叫欧几里得算法，是一种求两个正整数的____________的古老而有效的算法．
(2)更相减损术：我国古代数学专著《九章算术》中介绍的一种求两个正整数的____________的算法．最大公约数最大公约数2．秦九韶算法一元n次多项式(anxn－1＋an－1xn－2＋…＋a1)x＋a0(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0v2x＋an－3n个一次多项式3.进位制
(1)进位制
进位制是人们为了____________和____________方便而约定的记数系统，“满几进一”就是__________制，__________制的基数就是____________．
(2)其他进位制与十进制间的转化
①其他进位制化成十进制
其他进位制的数化成十进制时，表示成_________________
______________________的形式．
②十进制化成k进制的方法——“____________”．计数运算几进几几进基数的幂的乘积之和除k取余法不同位上数字与1．用更相减损术求294和84的最大公约数时，需做减法运算的次数是( )
A．2 B．3
C．4 D．5
解析：294－84＝210，210－84＝126，126－84＝42，84－42＝42，共做4次减法运算．C2．用秦九韶算法计算多项式f(x)＝3x6＋4x5＋5x4＋6x3＋7x2＋8x＋1当x＝0.4时的值时，需要做乘法和加法的次数分别是
( )
A．6，6 B．5，6
C．5，5 D．6，5A3．完成下列进位制之间的转化．
(1)1 034(7)＝________(10)；
(2)119(10)＝________(6)．3683154．当所给的多项式按x的降幂排列“缺项”时，用秦九韶算法改写多项式时，应注意什么？
解：所缺的项写成系数为零的形式，即写成0·xn的形式．1．对于任何一个数，我们可以用不同的进位制来表示．
2．表示各种进位制数一般在数字右下角加注来表示,如111 001(2)表示二进制数，34(5)表示5进制数．
3．电子计算机一般都使用二进制．
4．利用除k取余法，可以把任何一个十进制数化为k进制数，并且操作简单、实用．
5．通过k进制数与十进制数的转化，我们也可以将一个k进制数转化为另一个不同基数的M进制数．
6．利用秦九韶算法可以减少计算次数提高计算效率．求最大公约数1．(1)1 624与899的最大公约数是________．
解析：1 624＝899×1＋725，
899＝725×1＋174，
725＝174×4＋29，
174＝29×6，
故1 624与899的最大公约数是29.29(2)用辗转相除法求80和36的最大公约数，并用更相减损术检验所得结果．
秦九韶算法及其应用[解] ∵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.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＝1 124.5，
v4＝v3×6＋7.2＝6 754.2，
v5＝v4×6＋5＝40 530.2，
v6＝v5×6－13＝243 168.2.
所以f(6)＝243 168.2.进位制[互动探究] 将本例(1)中的二进制数101 101(2)转化为三进制数．3．(1)二进制数算式1 010(2)＋10(2)的值是( )
A．1 011(2) B．1 100(2)
C．1 101(2) D．1 000(2)
解析：二进制数的加法是逢二进一，所以选B.
(2)下列各组数中最小的数是( )
A．1 111(2) B．210(6)
C．1 000(4) D．101(8)
解析：统一化为十进制数为1 111(2)＝15；210(6)＝78；1 000(4)＝64；101(8)＝65.BAA[解析] 将多项式变式为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.
[错因与防范]
(1)考虑x＝－2而认为多项式的值为负值．
(2)易忽略多项式中系数为0的项，致使多项式改写不正确．
(3)解题时注意多项式变形后有几次乘法和几次加法．
(4)要注意所给多项式的项数，特别是系数为0的项．4．(1)用秦九韶算法计算多项式f(x)＝12＋35x－8x2＋6x4＋5x5＋3x6在x＝－4时的值时，v3的值为( )
A．－144 B．－136
C．－57 D．34
解析：根据秦九韶算法多项式可化为
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.B(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.2381．下列关于利用更相减损术求156和72的最大公约数的说法中正确的是( )
A．都是偶数必须约简
B．可以约简，也可以不约简
C．第一步作差为156－72＝84；第二步作差为72－84＝－12
D．以上都不对
解析：约简是为了使运算更加简捷，故不一定要约简，A错．C中第二步应为84－72＝12，故选B.B2．用辗转相除法计算294与84的最大公约数时，需要做的除法次数是( )
A．1 B．2
C．3 D．4
解析：294＝84×3＋42，84＝42×2，至此公约数已求出．
3．二进制数1 101 111(2)化成十进制数是________．
解析：1 101 111(2)＝1×20＋1×21＋1×22＋1×23＋0×24＋1×25＋1×26＝111.B1114．若k进制数123(k)与十进制数38相等，则k＝________．
解析：由k进制数123可知k≥4.
下面可用验证法：
若k＝4，则38(10)＝212(4)，不合题意；
若k＝5，则38(10)＝123(5)成立，所以k＝5.5本部分内容讲解结束按ESC键退出全屏播放