当前位置:首页 >> 小学教育 >>

1.3算法案例


§

复习引入
1. 回顾算法的三种表示方法:

(1)、自然语言 (2)、程序框图 (三种逻辑结构) (五种基本语句 (3)、程序语言 )

2. 思考:
小学学过的求两个数的最大公约数的方法?
先用两个公有的质因数连续去除, 一直除到所得的商是互质数为止,然后 把所有的除数连乘起来.



例:求下面两个正整数的最大公约数: (1)求25和35的最大公约数 (2)求49和63的最大公约数
(1) 5 25 35 5 7 所以,25和35的最 大公约数为5 (2)7 49 63

7 9 所以,49和63的最 大公约数为7

例:如何算出8251和6105的最大公约数?

新课讲解:
一、辗转相除法(欧几里得算法) 1、定义: 所谓辗转相除法,就是对于给定的 两个数,用较大的数除以较小的数。若 余数不为零,则将余数和较小的数构成 新的一对数,继续上面的除法,直到大 数被小数除尽,则这时较小的数就是原 来两个数的最大公约数。

2、步骤:(以求8251和6105的最大公约数的过 程为例) 第一步 用两数中较大的数除以较小的数,求得 商和余数:8251=6105×1+2146 结论: 8251和6105的公约数就是6105和2146 的公约数,求8251和6105的最大公约数,只要 求出6105和2146的最大公约数就可以了。 第二步 对6105和2146重复第一步的做法 6105=2146×2+1813 同理6105和2146的最大公约数也是2146和1813 的最大公约数。

完整的过程
8251=6105×1+2146

显然37是 6105=2146×2+1813 148和37 的最大公 2146=1813×1+333 约数,也 就是8251 和6105的 1813=333×5+148 最大公约 数 333=148×2+37
148=37×4+0

例: 用辗转相除法求225和135的最大公约数
225=135×1+90 135=90×1+45 90=45×2 显然45是90和45的最大公约数,也就是225和135的最 大公约数

思考1:从上面的两个例子中可以看出计算的规 律是什么?
S1:用大数除以小数

S2:除数变成被除数,余数变成除数 S3:重复S1,直到余数为0

辗转相除法是一个反复执行直到余数等于0才停 止的步骤,这实际上是一个循环结构。 m = n × q + r 用程序框图表示出右边的过程
r=m MOD n 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 n=r r=0? 1813=333×5+148 否 333=148×2+37 148=37×4+0

m=n



思考:你能把辗转相除法编成一个计算机程
序吗? (1)、算法步骤:
第一步:输入两个正整数m,n(m>n). 第二步:计算m除以n所得的余数r.

第三步:m=n,n=r.
第四步:若r=0,则m,n的最大公约数等于m; 否则,返回第二步. 第五步:输出最大公约数m.

(2)、程序框图:
开始 输入m,n
r=m MOD n

m=n
n=r 否 r=0? 是 输出m 结束

(3)、程序: INPUT m,n
DO

r=m MOD n
m=n

n=r
LOOP UNTIL r=0 PRINT m END

二、更相减损术
1、背景介绍:
(1)、《九章算术》中的更相减损术:
可半者半之,不可半者,副置分母、子之数,以少 减多,更相减损,求其等也,以等数约之。

(2)、现代数学中的更相减损术:
第一步:任意给定两个正整数;判断他们是否都是 偶数。若是,则用2约简;若不是则执行第二步。 第二步:以较大的数减去较小的数,接着把所得的 差与较小的数比较,并以大数减小数。继续这个操 作,直到所得的数和差相等为止,则这个等数或这 个数与约简的数的乘积就是所求的最大公约数。

2、定义:
所谓更相减损术,就是对于给定的两个 数,用较大的数减去较小的数,然后将差和 较小的数构成新的一对数,再用较大的数减 去较小的数,反复执行此步骤直到差数和较 小的数相等,此时相等的两数便为原来两个 数的最大公约数。

3、方法:
例: 用更相减损术求98与63的最大公约数.
解:由于63不是偶数,把98和63以大数减小 数,并辗转相减

98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 所以,98和63的最大公约数等于7

练习:
1、用更相减损术求两个正数84与72的最大公约数. 思路分析:先约简,再求21与18的最大公约数, 然后乘以两次约简的质因数4。 2、求324、243、135这三个数的最大公约数。 思路分析:求三个数的最大公约数可以先求出两个 数的最大公约数,第三个数与前两个数的最大公约 数的最大公约数即为所求。

2、求324、243、135这三个数的最大公约数

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、 、 的最大公约数为27 . 243 135

2、求324、243、135这三个数的最大公约数

324 ? 243 ? 81,243 ? 81 ? 162 ,162 ? 81 ? 81, 则324 与243的最大公约数为81 . 135 ? 81 ? 54,81 ? 54 ? 27 ,54 ? 27 ? 27 , 则81与135的最大公约数为27 . 所以,三个数324、 、 最大公约数为27 . 243 135

***思考:你能根据更相减损术设计程序,求两 个正整数的最大公约数吗?
(1)、算法步骤 第一步:输入两个正整数a,b(a>b); 第二步:若a不等于b ,则执行第三步;否则转 到第五步; 第三步:把a-b的差赋予r; 第四步:如果b>r, 那么把b赋给a,把r赋给b;否 则把r赋给a,执行第二步;

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

(2)、程序框图

开始
输入a,b

a≠b? 是 r=a-b
a=r 否 r<b? 是 a=b b=r 输出b



结束

(3)、程序 INPUT "a,b=";a,b
WHILE a<>b r=a-b IF b>r THEN a=b b=r ELSE a=r END IF WEND PRINT b END

小结

比较辗转相除法与更相减损术的区别
(1)都是求最大公约数的方法,计算上辗转相除

法以除法为主,更相减损术以减法为主,计算次数

上辗转相除法计算次数相对较少,特别当两个数字
大小区别较大时计算次数的区别较明显。 (2)从结果体现形式来看,辗转相除法体现结果 是以相除余数为0则得到,而更相减损术则以减数与 差相等而得到。

1、求两个数的最大公约数的两种方法分别是



)和(

)。

2、两个数21672,8127的最大公约数是 ( ) A、2709 B、2606 C、2703 D、2706

怎样求多项式f(x)=x5+x4+x3+x2+x+1 当x=5时的值呢?

计算多项式f(x) =x5+x4+x3+x2+x+ 1当x = 5的值
算法1: 因为f(x) =x5+x4+x3+x2+x+1 所以f(5)=55+54+53+52+5+1 =3125+625+125+25+5+1 = 3906 算法2: f(5)=55+54+53+52+5+1 =5×(54+53+52+5+1 ) +1 =5×(5×(53+52+5 +1 )+1 ) +1 =5×(5×(5×(52+5 +1) +1 ) +1 ) +1 =5×(5×(5×(5 ×(5 +1) +1 )+1)+1) +1

算法1: 因为f(x) =x5+x4+x3+x2+x+1 所以f(5)=55+54+53+52+5+1
=3125+625+125+25+5+1 = 3906

共做了1+2+3+4=10次乘法运算,5次加法运算。
算法2: f(5)=55+54+53+52+5+1 =5×(54+53+52+5+1 ) +1 =5×(5×(53+52+5 +1 )+1 ) +1 =5×(5×(5×(52+5 +1) +1 ) +1 ) +1 =5×(5×(5×(5 ×(5 +1) +1 )+1)+1) +1

共做了4次乘法运算,5次加法运算。

《数书九章》——秦九韶算法 设 f (x) 是一个n 次的多项式 f ( x) ? an x n ? an ?1 x n ?1 ? ? ? a1 x ? a0
对该多项式按下面的方式进行改写: f ( x) ? an x n ? an ?1 x n ?1 ? ? ? a1 x ? a0
? (an x n?1 ? an?1 x n ?2 ? ? ? a1 ) x ? a0

这是怎样的 一种改写方 式?最后的 结果是什么 ?

?? ?

? (( an x n ?2 ? an ?1 x n ?3 ? ? ? a2 ) x ? a1 ) x ? a0
? (?(an x ? an?1 ) x ? an ?2 ) x ? ? ? a1 ) x ? a0

f ( x) ? (?(an x ? an?1 ) x ? an?2 ) x ? ? ? a1 ) x ? a0
要求多项式的值,应该先算最内层的一次多项式的值,即

v1 ? an x ? an ?1
然后,由内到外逐层计算一次多项式的值,即

v2 ? v1 x ? an ?2 v3 ? v2 x ? an ?3 ?? vn ? vn ?1 x ? a0

最后的一 项是什么 ?

这种将求一个n次多项式f(x)的值转化成求n个一 次多项式的值的方法,称为秦九韶算法。

算法步骤:
第一步:输入多项式次数n、最高次项的系数an和x 的值. 第二步:将v的值初始化为an,将i的值初始化为n-1. 第三步:输入i次项的系数ai 第四步:v=vx+ai,i=i-1.

第五步:判断i是否小于或等于0,若是,则返回第 三步;否则,输出多项式的值v。

程序框图:

开始
输入n,an,x

?v 0 ? a n i=n-1 ? ?v k ? v k ?1 x ? an? k ( k ? 1,2,? , n)
i=i-1 这是一个在秦九韶算法中 反复执行的步骤,因此可 用循环结构来实现。

V=an

v=vx+ai i ? 0? N 输出v
结束
输入ai

Y

程序
INPUT "n=";n INPUT "an=";a INPUT "x=";x v=a i=n-1 WHILE i>=0 PRINT "i=";i INPUT "ai=";a v=v*x+a i=i-1 WEND PRINT v END

开始
输入n,an,x
V=an

i=n-1 i=i-1

v=vx+ai i ? 0? N 输出v
结束
输入ai

Y

特点:通过一次式的反复计算,逐步得出高次多 项式的值,对于一个n次多项式,只需做n次乘 法和n次加法即可。

例1:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值. 解法一:首先将原多项式改写成如下形式 : f(x)=((((2x-5)x-4)x+3)x-6)x+7 然后由内向外逐层计算一次多项式的值,即 v0=2 v1=v0x-5=2×5-5=5

v2=v1x-4=5×5-4=21

v3=v2x+3=21×5+3=108
v4=v3x-6=108×5-6=534 所以,当x=5时,多 v5=v4x+7=534×5+7=2677 项式的值是2677.

例1:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.

解法二:列表
2

原多项式 的系数

x=5
2

-5 10 5

-4 25 21

3 105 108

-6 7 540 2670 534 2677
多项式 的值.

所以,当x=5时,多项式的值是2677.

练一练:用秦九韶算法求多项式 f(x)=2x6-5x5-4x3+3x2-6x当x=5时的值. 解:原多项式先化为:

f(x)=2x6-5x5 +0×x4-4x3+3x2-6x+0
3 -6 0 605 3040 15170 608 3034 15170 所以,当x=5时,多项式的值是15170. 注意:n次多项式有n+1项,因此缺少哪一项 应将其系数补0. 列表 2 x=5 2 -5 10 5 0 -4 25 125 25 121

例2 已知一个五次多项式为 f ( x) ? 4 x5 ? 2 x 4 ? 3.5x3 ? 2.6 x 2 ? 1.7 x ? 0.8

用秦九韶算法求这个多项式当x = 5的值。 解: 将多项式变形: f ( x) ? (((( 4 x ? 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 ? 2826 .2 图来描述呢? v5 ? 2826 .2 ? 5 ? 0.8 ? 14130 .2

所以,当x = 5时,多项式的值等于14130.2

开始

程序框图:
输入f(x)的系数: a0,a1,a2,a3,a4a5

输入x0

?v 0 ? a n ? ?v k ? v k ?1 x ? an? k ( k ? 1,2,? , n)
这是一个在秦九韶算法中 反复执行的步骤,因此可 用循环结构来实现。

n=1

v=a5
n=n+1 n≤5?
Y

v=vx0+a5-n
N

输出v
结束

练习、已知多项式f(x)=x5+5x4+10x3+10x2+5x+1 用秦九韶算法求这个多项式当x=-2时的值。

课堂小结:
1、秦九韶算法的方法和步骤

2、秦九韶算法的程序框图

[问题1]我们常见的数字都是十进制的, 但是并不是生活中的每一种数字都是十进制的 .比如时间和角度的单位用六十进位制,电子计 算机用的是二进制.那么什么是进位制?不同的 进位制之间又有什么联系呢? 进位制是人们为了计数和运算的方便而 约定的一种记数系统,约定满二进一,就是二 进制;满十进一,就是十进制;满十六进一,就 是十六进制;等等. “满几进一”,就是几进制,几进制的基数就是几. 可使用数字符号的个数称为基数.基数 都是大于1的整数.

如二进制可使用的数字有0和1,基数是2;
十进制可使用的数字有0,1,2,…,8,9等十个 数字,基数是10; 十六进制可使用的数字或符号有0~9等10 个数字以及A~F等6个字母(规定字母A~F对应 10~15),十六进制的基数是16. 注意:为了区分不同的进位制,常在数字 的右下脚标明基数. 如111001(2)表示二进制数,34(5)表示5进制数.

十进制数一般不标注基数.

[问题2]十进制数3721中的3表示3个千,7表示7 个百,2表示2个十,1表示1个一,从而它可以写成 下面的形式: 3721=3×103+7×102+2×101+1×100. 想一想二进制数1011(2)可以类似的写成什 么形式? 1011(2)=1×23+0×22+1×21+1×20.

同理: 3421(5)=3×53+4×52+2×51+1×50.
C7A16(16)=12×164+7×163+10×162+1×161+6 ×160

一般地,若k是一个大于1的整数,那么以k为 基数的k进制数可以表示为一串数字连写在一起 的形式 anan-1…a1a0(k) (0<an<k,0≤an-1,…,a1,a0<k) 意思是:(1)第一个数字an不能等于0; (2)每一个数字an,an-1,…,a1,a0都须小于k. k进制的数也可以表示成不同位上数字与 基数k的幂的乘积之和的形式,即 anan-1…a1a0(k)=an×kn+an-1×kn-1 注意这是一 1+a ×k0 . 个n+1位数. +…+a1×k 0

[问题3]二进制只用0和1两个数字,这 正好与电路的通和断两种状态相对应,因 此计算机内部都使用二进制.计算机在进 行数的运算时,先把接受到的数转化成二 进制数进行运算,再把运算结果转化为十 进制数输出.

那么二进制数与十进制数之间是如 何转化的呢?

例1:把二进制数110011(2)化为十进制数. 分析:先把二进制数写成不同位上数字与2 的幂的乘积之和的形式,再按照十进制数的运算 规则计算出结果.
解:110011(2)

=1×25+1×24+0×23+0×22+1×21+1×20
=1×32+1×16+1×2+1=51. [问题4]你会把三进制数10221(3)化为十进制数吗 ? 解:10221 =1×34+0×33+2×32+2×31+1×30
(3)

=81+18+6+1=106.

k进制数转化为十进制数的方法
先把k进制的数表示成不同位上数字 与基数k的幂的乘积之和的形式,即 anan-1…a1a0(k) =an×kn+an-1×kn-1+…+a1×k1+a0×k0 . 再按照十进制数的运算规则计算出结果.

例2.设计一个算法,把k进制数a(共有n位)化 为十进制数b.
算法步骤如下: 第一步,输入a, k和n的值. 第二步,将b的值初始化为0,i的值初始化为1. 第三步,b ? b ? ai ? k ,i ? i ? 1. 第四步,判断i ? n是否成立.若是,则执行第五步; 否则,返回第三步. 第五步,输出b的值.
i ?1

① 开始 输入a,k,n 把a的右数第i位数字赋给t b=b+t*ki-1 i=i+1 i>n? 是 否

b=0 i=1 ①

输出b
结束

INPUT a,k,n b=0 i=1 t=a MOD 10
DO b=b+t*k^(i-1) a=a\10 t=a MOD 10 i=i+1 LOOP UNTIL i>n PRINT b END

例3:把89化为二进制的数. 分析:把89化为二进制的数,需想办法将89 先写成如下形式

89=an×2n+an-1×2n-1+…+a1×21+a0×20 .
89=64+16+8+1=1×26+0×25+1×24 +1×23+0×22+0×21+1×20 =1011001(2). 但如果数太大,我们是无法这样凑出来的,怎么办? 89=44×2+1, 44=22×2+0, 22=11×2+0, 11=5×2+1, 5=2×2+1, 2=1×2+0, 1=0×2+1,

89=44×2+1, 44=22×2+0, 22=11×2+0, 11=5×2+1, 5=2×2+1, 2=1×2+0, 1=0×2+1, 89=44×2+1, 可以用2连续去除89 或所得商(一直到商为 =(22×2+0)×2+1 0为止),然后取余数 =((11×2+0)×2+0)×2+1 ---除2取余法. =(((5×2+1)×2+0)×2+0)×2+1 =((((2×2+1)×2+1)×2+0)× 2+0)×2+1

=(((((1×2)+0)×2+1)×2+1)×2+0)× 2+0)×2+1 =1×26+0×25+1×24+1×23+0×22+0×21+1×2 0=1011001 . (2)

例3:把89化为二进制的数. 我们可以用下面的除法算式表示除2取余法:

2 89 2 44 2 22 2 11 2 5 2 2 21 0

余数 1 0 0 1 1 0 1

把算式中各步所得的余数 从下到上排列,得到 89=1011001(2).
这种方法也可以推广为把 十进制数化为k进制数的 算法,称为除k取余法.

例4:把89化为五进制的数. 解:以5作为除数,相应的除法算式为: 余数 5 89 5 17 4 5 3 2 0 3 ∴ 89=324(5).

例5.设计一个程序,实现“除k取余法” (k ? N ,2 ? k ? 9) .
算法如下: 第一步,给定十进制正整数a和转化后的数的基数k . 第二步,求出a除以k的商q,余数r. 第三步,把得到的余数依次从右到左排列 . 第四步,若q ? 0,则a ? q,返回第二步;否则 否则,输出全部余数r排列得到的k进制数.

开始 输入a,k 求a除以k的商q


输出全部余数r排列得到的k进制数

结束

求a除以k的余数r
把得到的余数依次从右到左排列

a=q q=0?
是 ① 否

INPUT b=0 i=0 DO

“a,k=” ;a,k

q=a\k
r=a MOD k b=b+r*10^i i=i+1 a=q

LOOP UNTIL q=0
PRINT b END

[问题5]你会把三进制数10221(3)化为二进制数吗 ? 解:第一步:先把三进制数化为十进制数: 10221(3)=1×34+0×33+2×32+2×31+1×30
=81+18+6+1=106. 第二步:再把十进制数化为二进制数: 106=1101010(2). ∴10221(3)=106= 1101010(2).

小结
? 进位制的概念及表示方法;
anan-1…a1a0(k) =an×kn+an-1×kn-1+…+a1×k1+a0×k0 .

? 各种进位制之间的相互转化.

作业:
1.课本P45页A组T3.


相关文章:
1.3算法案例教案
1.3算法案例教案_数学_高中教育_教育专区。考试指南报——课堂网(www.k45.cn) 算法案例一. 【课标要求】通过阅读中国古代数学中的算法案例,体会中国古代数学对...
1.3 算法案例知识点,试题及答案
1.3 算法案例知识点,试题及答案_数学_高中教育_教育专区。一、知识要点及方法辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的: 1. 若 r...
1.3算法案例
1.3算法案例_数学_高中教育_教育专区。高二数学必修 3 编号:SX--02--06 1.3.1《算法案例》导学案撰稿:付阿丽 审核:付阿丽 时间:2011.08.16 姓名: 班级:...
1.3_算法案例
1.3_算法案例_高一数学_数学_高中教育_教育专区。1.3 算法案例 教学分析 在学生学习了算法的初步知识, 理解了表示算法的算法步骤、 程序框图和程序三种不同 ...
1.3算法案例
1.3算法案例_数学_高中教育_教育专区。1.3 算法案例 [自我认知]: 1.用辗转相除法求 840 与 1785 的最大公约数: 班次 姓名 2.用更相减损术求 612 与 ...
1.3 算法案例
1.3 算法案例_数学_高中教育_教育专区。1.3 算法案例 . 课时安排 3 课时 提出问题 (1)怎样用短除法求最大公约数? (2)怎样用穷举法(也叫枚举法)求最大...
1.3算法案例
1.3算法案例_高一数学_数学_高中教育_教育专区。1.3算法案例1.3 算法案例 教学目标:掌握三个案例,理解辗转相除法,更相减损术,秦九韶算法,进位制。 教学重、...
1.3算法案例1
1.3算法案例1_数学_高中教育_教育专区。1.3 算法案例 第一、二课时 辗转相除法与更相减损术 (1)教学目标 (a)知识与技能 1.理解辗转相除法与更相减损术中...
1.3 算法案例
1.3算法案例(三) 2页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 1.3 算法案例 隐藏>> 山东省泰安第一...
更多相关标签:
十六进制 | 1.3算法案例教案 | 辗转相除法 | 1.3算法案例ppt | 1 1 2 3 5 8递归算法 | 算法导论22.1 3 | 算法导论19.3 1 | 算法导论24.1 3 |