9512.net
甜梦文库
当前位置:首页 >> 数学 >>

1.3算法案例



§

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

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

一、输入语句
1、一般格式:

INPUT “提示内容”;变量 二、输出语句
1、一般格式:

INPUT “x=” ;x

PRINT “提示内容”;表达式

三、赋值语句

1、一般格式:

变量=表达式

程序框图

条件语句的一般格式 IF 条件 THEN

满足条件?




语句体(步骤A)
END IF

步骤A

程序框图

条件语句的一般格式 IF 条件 THEN 语句体1(步骤A) ELSE 语句体2(步骤B) END IF

满足条件? 是 步骤A

否 步骤B

两种循环语句:
(1)Until(直到型)循环 循环体 满足条件?

( 2)

DO 循环体 LOOP UNTIL 条件



While(当型)循环

循环体
满足条件?



WHILE 条件 循环体 WEND

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

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

5 7 所以,25和35的最 大公约数为5

例:如何算出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 1813=333×5+148 和6105的 最大公约 数 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 、 243 、 135 的最大公约数为 27.

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

***思考:你能根据更相减损术设计程序,求两 个正整数的最大公约数吗?
(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 次的多项式 n n?1 f ( x) ? an x ? an?1x ? ?? a1x ? a0
对该多项式按下面的方式进行改写: f ( x) ? an xn ? an?1xn?1 ? ?? a1x ? a0
? (an xn?1 ? an?1xn?2 ? ?? a1 ) x ? a0

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

? ??

? ((an xn?2 ? an?1xn?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=an

?v 0 ? a n i=n-1 ? ?v k ? v k ?1 x ? a n? k ( k ? 1,2, ? , n)

i=i-1
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) ? 4x5 ? 2x 4 ? 3.5x3 ? 2.6x 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 ? a n? 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 注意这是一 个n+1位数. 1 0 +…+a1×k +a0×k .

[问题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取余法: 余数 1 0 0 1 1 0 1

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

把算式中各步所得的余数 从下到上排列,得到 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) 算法案例一. 【课标要求】通过阅读中国古代数学中的算法案例,体会中国古代数学对...
高中数学必修3《1.3算法案例)》教案设计
高中数学必修3《1.3算法案例)》教案设计_数学_高中教育_教育专区。www.xkb1.com 新课标第一网系列资料 www.xkb1.com 新课标第一网不用注册,免费下载! 1.3...
1.3算法案例
建业外国语中学教学案 高一数学必修三 序号: 1.3 撰稿人: 班级: 刘小颖 课姓 算法案例型: 新授课 名: 审核人: 使用日期: 刘小颖 一、标学装 (1)理解辗转...
1.3 算法案例知识点,试题及答案
1.3 算法案例知识点,试题及答案_数学_高中教育_教育专区。一、知识要点及方法辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的: 1. 若 r...
人教版高中数学必修三《1.3算法案例(教、学案)
临清三中数学组 编写人:赵万龙 审稿人: 郭振宇 李怀奎 1.3 算法案例 【教学目标】 : 1.理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算...
必修3数学教案设计全册-高中数学必修3《1.3算法案例》教案设计
必修3数学教案设计全册-高中数学必修3《1.3算法案例》教案设计_数学_高中教育_教育专区。新课标第一网系列资料 www.xkb1.com 1.3 算法案例 整体设计 教学分析...
1.3.2算法案例(秦九韶算法)[1]
总场中学高中部有效课堂教学 总场中学高中部有效课堂教学 教学案 课 算法案例—秦九韶算法 题:1.3.2 算法案例 秦九韶算法 1.3.2 算法案例 秦九韶算法 算法...
高中数学必修3教学设计:1.3《算法案例---秦九韶算法》
〔教案〕 教学目标: 1.3 算法案例――-秦九韶算法 (1) 在学习中国古代数学中的算法案例的同时,进一步体会算法的 特点。 (2) 体会中国古代数学对世界数学发展...
1.3算法案例
1.3算法案例_数学_高中教育_教育专区。为您服务教育网 http://www.wsbedu.com/ 1.3 算法案例 [学习目标导航] 学习提示 1. 通过对中国古代算法研究的学习,了...
更多相关标签:
十六进制    1.3算法案例教案    辗转相除法    1.3算法案例ppt    1 1 2 3 5 8递归算法    算法导论22.1 3    算法导论19.3 1    算法导论24.1 3    

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图