高中数学1.4算法案例知识讲解素材

算法案例

【学习目标】

1. 理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析；

2. 基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序；

3. 了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质；

4. 了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联系进行各种进位制之间的转换.

【要点梳理】

要点一、辗转相除法

也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的. 利用辗转相除法求最大公约数的步骤如下：

第一步：用较大的数m 除以较小的数n 得到一个商q 0和一个余数r 0；

第二步：若r 0=0，则n 为m ，n 的最大公约数；若r 0≠0，则用除数n 除以余数r 0得到一个商q 1和一个余数r 1；

第三步：若r 1=0，则r 0为m ，n 的最大公约数；若r 1≠0，则用除数r 0除以余数r 1得到一个商q 2和一个余数r 2；

„„

依次计算直至r n =0，此时所得到的r n －1即为所求的最大公约数.

用辗转相除法求最大公约数的程序框图为：

INPUT “m=”;m

INPUT “n=”;n

IF m

x=m

m=n

n=x

END IF

r=m MOD n

WHILE r0

r=m MOD n

m=n

n=r

WEND

PRINT n

END

要点诠释：

辗转相除法的基本步骤是用较大的数除以较小的数，考虑到算法中的赋值语句可以对同一变量多次赋值，我们可以把较大的数用变量m 表示，把较小的数用变量n 表示，这样式子m =n ⋅q +r (0≤r

要点二、更相减损术

我国早期也有解决求最大公约数问题的算法，就是更相减损术.

更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也. 以等数约之.

翻译出来为：

第一步：任意给出两个正整数；判断它们是否都是偶数. 若是，用2约简；若不是，执行第二步. 第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数. 继续这个操作，直到所得的数相等为止，则这个数(等数) 就是所求的最大公约数.

理论依据：

由a -b =r →a =b +r ，得a , b 与b , r 有相同的公约数

更相减损术一般算法：

第一步，输入两个正整数a , b (a >b ) ；

第二步，如果a ≠b ，则执行S 3，否则转到S 5；

第三步，将a -b 的值赋予r ；

第四步，若b >r ，则把b 赋予a ，把r 赋予b ，否则把r 赋予a ，重新执行S 2；

第五步，输出最大公约数b .

程序:

INPUT “a=”，a

INPUT “b=”，b

WHILE ab

IF a>=b

ELSE

b=b-a

WEND

END

PRINT b

或者

INPUT “请输入两个不相等的正整数”；a ，b

i=0

WHILE a MOD 2=0 AND b MOD 2=0

a=a/2

b=b/2

i=i+1

WEND

DO

IF b

t=a

a=b

b=t

END IF

c=a－b

a=b

b=c

LOOP UNTIL a=b

PRINT a^i

END

要点诠释：

用辗转相除法步骤较少，而更相减损术虽然有些步骤较长，但运算简单.

要点三、秦九韶计算多项式的方法

f (x ) =a 2

n x n +a n -1

n -1x +a n -2x n -+ +a 1x +a 0

=(a -1n -3

n x n +a n -2

n -1x +a n -2x + +a 1) x +a 0

=((a n x n -2+a n -3

n -1x + +a 2) x +a 1) x +a 0

=

=( ((a n x +a n -1) x +a n -2) x + +a 1) x +a 0

令v k =( ((a n x +a n -1) x +a n -2) x + +a v 0=a n

n -(k -1) ) x +a n -k ，则有⎨⎧

⎩v k =v -k 1x +a ，

-n

k =1, 2, n . 这样，我们便可由v 0依次求出v 1, v 2, v n ； 其中k

v 1=v 0x +a n -1,

v 2=v 1x +a n -2,

v 3=v 2x +a n -3,

v n =v n -1x +a 0

要点诠释：

显然，用秦九韶算法求n 次多项式的值时只需要做n 次乘法和n 次加法运算

要点四、进位制

进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值. 可使用数字符号的个数称为基数，基数为n ，即可称n 进位制，简称n 进制. 现在最常用的是十进制，通常使用10个阿拉伯数字0-9进行记数.

对于任何一个数，我们可以用不同的进位制来表示. 比如：十进数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的.

表示各种进位制数一般在数字右下角加注来表示, 如111001(2)表示二进制数,34(5)表示5进制数.

1.k 进制转换为十进制的方法：

把k 进制数a 转化为十进制a n a n -1a a 2a 1a 0(k ) =a n ⨯k n +a n -1⨯k n -1+ +a 2⨯k 2+a 1⨯k +a 0，

数b 的算法程序为：

INPUT “ a,k,n=”;a,k,n

i=1

b=0

WHILE i

t=GET a[i]

b=b+t*k^(i-1)

i=i+1

WEND

PRINT b

END

2. 十进制转化为k 进制数b 的步骤为：

第一步，将给定的十进制整数除以基数k ，余数便是等值的k 进制的最低位；

第二步，将上一步的商再除以基数k ，余数便是等值的k 进制数的次低位；

第三步，重复第二步，直到最后所得的商等于0为止，各次所得的余数，便是k 进制各位的数，最后一次余数是最高位，即除k 取余法.

要点诠释：

1、在k 进制中，具有k 个数字符号. 如二进制有0，1两个数字.

2、在k 进制中，由低位向高位是按“逢k 进一”的规则进行计数.

3、非k 进制数之间的转化一般应先转化成十进制，再将这个十进制数转化为另一种进制的数，有的也可以相互转化.

【典型例题】

类型一：辗转相除法与更相减损术

例1．分别用辗转相除法和更相减损术求378与90的最大公约数．

【答案】18

【解析】 用辗转相除法：

378=90×4+18，90=18×5．

∴378与90的最大公约数是18．

用更相减损术：

∵378与90都是偶数，

∴用2约分后得189和45．

189－45=144，144－45=99，99－45=54，54－45=9，45－9=36，36－9=27，27－9=18，18－9=9． ∴378与90的最大公约数为2×9=18．

【总结升华】比较辗转相除法与更相减损术的区别

(1)都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显；

(2)从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.

由该题可以看出，辗转相除法得最大公约数的步骤较少.

对比两种方法控制好算法的结束，辗转相除法是到达余数为0，更相减损术是到达减数和差相等. 举一反三：

【变式1】（1）用更相减损术求两个正数84与72的最大公约数．

（2）利用辗转相除法求3869与6497的最大公约数与最小公倍数．

【解析】 （1） 因为84=21×4，72=18×4，

所以21－18=3，

18－3=15，

15－3=12，

12－3=9，

9－3=6，

6－3=3．

所以21和18的最大公约数等于3．

所以84和72的最大公约数等于12．

【总结升华】先约简，再求21与18的最大公约数，然后乘以约简的4得84与72的最大公约数．

（2）6497=3869×1+2628，

3869=2628×1+1241，

2628=1241×2+146，

1241=146×8+73，

146=73×2+0．

所以3 869与6 497的最大公约数为73，

最小公倍数为3 869×6497÷73=344341．

例2．求三个数：168，54，264的最大公约数．

【思路点拨】运用更相减损术或辗转相除法，先求168和54的最大公约数a ，再求a 与264的最大公约数．

【答案】6

【解析】

采用更相减损术先求168和54的最大公约数．

（168，54）→（114，54）→（60，54）→（6，54）→（6，48）→（6，42）→（6，36）→（6，

30）→（6，24）→（6，18）→（6，12）→（6，6）．

故168和54的最大公约数为6．

采用辗转相除法求6和264的最大公约数．

∵264=44×6+0，

∴6为264与6的最大公约数，也是这三个数的最大公约数．

【总结升华】 求最大公约数通常有两种方法：一是辗转相除法；二是更相减损术，对于3个数的最大公约数的求法，则是先求其中两个数的最大公约数m ，再求m 与第三个数的最大公约数．同样可推广到求3个以上数的最大公约数．

举一反三：

【变式1】求三个数324，243，135的最大公约数．

【答案】27

【解析】∵324=243×1+81，

243=81×3+0，

∴324与243的最大公约数为81．

又135=81×1+54，

81=54×1+27，

54=27×2+0，

∴81与135的最大公约数为27．

∴三个数324，243，135的最大公约数为27．

更相减损术：

∵324－243=81，

243－81=162，

162－81=81，

∴81是324和243的最大公约数．

又135－81=54，

81－54=27，

54－27=27，

∴27是81与135的最大公约数．

∴三个数324，243，135的最大公约数为27．

例3. 甲、乙、丙三种溶液分别重147g 、343g 、133g ，现要将它们分别全部装入小瓶中，每个小瓶装入液体的质量相同，问每瓶最多装多少？

【思路点拨】由题意，每个小瓶最多能装的溶液的质量应是三种溶液质量的最大公约数.

【答案】7g

【解析】

先求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 .

【总结升华】本题关键是分析清楚题意，找出三个数的最大公约数. 求三个以上(含三个数) 的数的最大公约数时，可依次通过求两个数的最大公约数与第三个数的最大公约数来求得.

类型二：秦九韶算法

例4．利用秦九韶算法求f (x ) =1+x +0.5x 2+0.16663x 3+0.04168x 4+0.00835x 5在x=0.2时的值．写出详细计算过程．

【思路点拨】秦九韶算法是我国南宋的数学家秦九韶首先提出来的．

（1）特点：它通过一次式的反复计算，逐步计算高次多项式的求值问题，即将一个n 次多项式的求值问题，归结为重复计算n 个一次式(a i x +a i -1) ．即f (x ) =( ((a n x +a n -1) x +a n -2) x + a 1) x +a 0．

（2）具体方法如下：已知一个一元n 次多项式f (x ) =a n x n +a n -1x n -1+ +a 1x +a 00．当x=x0，我们可按顺序一项一项地计算，然后相加，求得f (x 0) ．

【答案】1.2214024

【解析】

v0=0.00835，

v1=v0x+0.04168=0.00835×0.2+0.04168=0.043 35，

v2=v1x+0.16663=0.04335×0.2+0.16663=0.1753，

v3=v2x+0.5=0.1753×0.2+0.5=0.53506，

v4=v3x+1=0.53506×0.2+1=1.107012，

v5=v4x+1=1.107012×0.2+1=1.2214024．

【总结升华】秦九韶算法的原理是

⎨⎧v 0=a n ．

⎩v k =v k -1x +a n -k (k =1,2,3, , n )

在运用秦九韶算法进行计算时，应注意每一步的运算结果，像这种一环扣一环的运算，如果错一步，则下一步，一直到最后一步就会全部算错．同学们在计算这种题时应格外小心．

举一反三：

【变式1】用秦九韶算法求多项式f (x ) =8x +5x +3x +2x +1当x=2时的值．

【答案】1397

【解析】

f (x ) =8x 7+5x 6+0⋅x 5+3x 4+0⋅x 3+0⋅x 2+2x +1=((((((8x +5) x +0) x +3) x +0) x +0) x +2) x +1．

v0=8，

v1=8×2+5=21，

v2=21×2 4-0=42，

v3=42×2 4-3=87， 764

v4=87×2+0=174，

v5=174×2+0=348，

v6=348×2+2=698，

v7=698×2+1=1397，

所以，当x=2时，多项式的值为1397．

【变式2】用秦九韶算法计算多项式f (x ) =6x 6+5x 5+4x 4+3x 3+2x 2+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．（1）试把十进制数136转化为二进制数；

（2）试把十进制数1 234转化为七进制数．

【答案】（1）10001000

【解析】 （1）由于136=2×68+0，

68=2×34+0．

34=2×17+0．

17=2×8+1．

8=2×4+0．

4=2×2+0．

2=2×1+0．

1=2×0+1．

所以136=10001000（2）．

（2）1234=7×176+2，

176=7×25+1．

25=7×3+4．

3=7×0+3．

所以1234=3412（7）．

【总结升华】（1）应注意搞清每一次除法中的被除数、除数，当商为零时停止除法，把每步所得的余数倒着排成一个数，就是相应的二进制数．

（2）十进制数转化为七进制数与转化为二进制数的方法类似，要认真体会其原理．

举一反三：

【变式1】（1）把十进制数89转化为二进制数；

（2）将十进制数2l 转化为五进制数．

【解析】（1）用除2取余法：

2∴89=2×(2×(2×(2×(2×(2×(2×0+1)+0)+1)+1)+0)+0)+1=2×(2×(2×(2×2×(2×

65432100+2+0)+1)+1)+0)+0)+1 =„„=1×2+0×2+1×2+1×2+0×2×0×2+1×2=1011001(2)

（2）用除5取余法，可得

∴21=41（5）．

例6．把210121l （3）转化为八进制数．

【答案】3326（8）

【解析】 先将三进制数转化为十进制数，再将十进制数转化为八进制数．

2101211（3）

653210 =2×3+1×3+1×3+2×3+1×3+1×3

=1458+243+27+18+3+1

=1750．

1750=8×218+6．

218=8×27+2．

27=8×3+3．

∴1750=8×218+6

=8（8×27+2）+6

=8（8（8×3+3）+2）+6

2 =8（3×8+3×8+2）+6

32 =3×8+3×8+2×8+6

=3326（8），

∴2101211（3）=3326（8）．

【总结升华】从本例的解答中，大家要有两个提高．

第一，把三进制数转化为八进制数，十进制数起了桥梁和纽带的作用，具体体现是2101211（3）=1750=3326（8）．

第二，在把1750转化为3326（8）时，我们没有列竖式，大家要从中体会一下方法的内在规律． 举一反三：

【变式1】在十进制中，2004=4⨯10+0⨯10+0⨯10+2⨯10，那么在五进制中数码2 004折合成十进制为（ ）

A ．29 B．254 C．602 D．2 004

【答案】B

解析：2004=4⨯5+0⨯5+0⨯5+2⨯5=254，故选B ． 01230123

【变式2】（1）将二进制数111 1（2）转化成十进制数；

16个1

（2）将七进制数235（7）转化成八进制数．

【答案】（1）2-1（2）174（8）

【解析】对于（1），按照形式a n a n ―1a n ―2„a 1a 0（2）=an ×2a n ―1×2+„+a1×2+an 计算即可；对于（2），n+n ―126先将七进制数转化成十进制数，再将所得十进数转化成八进制数．

（1）111 1=1⨯215+1⨯214+ +1⨯21+1⨯20=216-1．

16个1(2)

（2）235（7）=2×72+3×7+5=124，利用除8取余法得124=174（8），过程如图所示，所以235（7）转化成八制数为174（8）．