【优化方案】高中数学 第一章 算法初步 1.3算法案例学案 新人教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．4 D．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，6 B．5，6

C．5，5 D．6，5

答案：A

3．完成下列进位制之间的转化．

(1)1 034(7)＝________(10)；

(2)119(10)＝________(6)．

解析：(1)1 034(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．表示各种进位制数一般在数字右下角加注来表示，如111 001(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)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的最大公约数，并用更相减损术检验所得结果．

解：辗转相除法：

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＝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)化为十进制数；

(2)把十进制数458转化为四进制数．

(链接教材P41例3、例4)

[解] (1)101 101(2)＝1×25＋0×24＋1×23＋1×22＋0×21＋1×20＝32＋8＋4＋1＝45，

所以二进制数101 101(2)转化为十进制数为45. (2)

458＝13 022(4)．

[互动探究] 将本例(1)中的二进制数101 101(2)转化为三进制数．

解：101 101(2)＝1×25＋0×24＋1×23＋1×22＋0×21＋1×20＝45，

∴45＝1 200(3)，∴101 101(2)＝1 200(3)．

方法归纳

(1)将k进制转化为十进制的方法是：先将这个k进制数写成各个数位上的数字与k的幂的乘积之和的形式，再按照十进制的运算规则计算出结果．(2)十进制转化为k进制，采用除k取余法，也就是除基数，倒取余．

3．(1)二进制数算式1 010(2)＋10(2)的值是( )

A．1 011(2) B．1 100(2)

C．1 101(2) D．1 000(2)

解析：选B.二进制数的加法是逢二进一，所以选B.

(2)下列各组数中最小的数是( )

A．1 111(2) B．210(6)

C．1 000(4) D．101(8)

解析：选A.统一化为十进制数为1 111(2)＝15；210(6)＝78；1 000(4)＝64；101(8)＝65.

易错警示 因忽略零系数项而致误

利用秦九韶算法求多项式f(x)＝x6－5x5＋6x4＋x2＋3x＋2当x＝－2时的值为( )

A．320 B．－160

C．－320 D．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的项，致使多项式改写不正确．