当前位置:首页 >> 数学 >>

1.3算法案例ppt


1.3

算法案例

1.3

算法案例

1.3.1 辗转相除法和更相减损术 1.3.2 秦九韶算法 1.3.3 K进制化十进制

1.3.4 十进制化K进制

1.3.1 辗转相除法 和更相减损术

复习 1.研究一个实际问题的算法

,主要从哪几方面展开?

算法步骤、程序框图和编写程序三方面展开.
2.在程序框图中算法的基本逻辑结构有哪几种? 顺序结构、条件结构、循环结构 3.在程序设计中基本的算法语句有哪几种? 输入语句、输出语句、赋值语句、条件语句、循环语句

情境创设
? 韩信是秦末汉初的著名军事家.据说有一次汉高祖 刘邦在卫士的簇拥下来到练兵场,刘邦问韩信有什 么方法,不要逐个报数,就能知道场上的士兵的人数, 韩信先令士兵排成3列纵队,结果有2人多余,接着 下令排成5列纵队,结果又多出3人,随后他又下令 改为7列纵队,这次又剩下2人无法成整行.在场的 人都哈哈大笑,以为韩信不能清点出准确的人数,不 料笑声刚落,韩信高声报告共有士兵2333人.众人 听了一楞,不知道韩信用什么方法这么快就能得到 正确的结果的.今天,我们将以这些古典案例的思想, 设计出适宜计算机的运行程序,提高我们对基本算 法结构和算法语句在实际中的运用能力.

探究一,辗转相除法
思考1:在小学中我们是如何求出两个正整数 的最大公约数的呢?

算法案例之求最大公约数
例、求18与24的最大公约数:

解:2 1 8 2 4 用公有质因数2除, 3 9 12 用公有质因数3除, 3 4 3和4互质不除了。 得:18和24最大公约数是:2×3=6

短除法

求以下几组正整数的最大公约数。 (注:若整数m和n满足n整除m,则(m,n)=n。用(m,n)来表示 m和n的最大公约数。)

(1)(18,30)6; (2)(24,16) 8; (3)(63,63) (4)(72,8) 8; 63; 7; (5)(301,133 ) 想一想,如何求8251与6105的最大公约数?

思考2:对于8251与6105这两个数,它们的最大 公约数是多少?你是怎样得到的?

由于它们公有的质因数较大,利用上述方法求 最大公约数就比较困难.有没有其它的方法可以较简 单的找出它们的最大公约数呢?

思考3:注意到8251=6105×1+2146,那么8251 与6105这两个数的公约数和6105与2146的公约数有 什么关系?

我们发现6105=2146×2+1813,同理,6105与 2146的公约数和2146与1813的公约数相等. 思考4:重复上述操作,你能得到8251与6105这 两个数的最大公约数吗? 8251=6105×1+2146, 1813=333×5+148, 6105=2146×2+1813, 333=148×2+37, 2146=1813×1+333, 148=37×4+0. 定义:所谓的辗转相除法,就是对于给定的两个数, 用较大的数除以较小的数,若余数不为零,则将余数 和较小的数构成新的数对,继续上面的除法, 直到大数 被小数除尽,则这是较小的数就是原来两个数的最大公约数

思考4:辗转相除直到何时结束? 主要运用的是哪种算法结构?
辗转相除法是一个反复执行直到余数等于0停止的步骤, 这实际上是一个循环结构 辗转相除法求两个数的最大公约数,其算法可以描述如下: ① 输入两个正整数m和n; ② 求余数r:计算m除以n,将所得余数存放到变量r中; ③更新被除数和余数:m=n,n=r。 ④判断余数r是否为0:若余数为0则输出结果,否则转 向第②步继续循环执行。 如此循环,直到得到结果。

思考5:你能把辗转相除法编成一个计算机程序吗? 第一步,给定两个正整数m,n(m>n). 第二步,计算m除以n所得的余数r. 第三步,m=n,n=r. 第四步,若r=0,则m,n的最大公约数等于m; 否则,返回第二步.

开始
程序框图 INPUT m,n DO r=m MOD n m=n n=r LOOP UNTIL PRINT m END 输入m,n 求m除以n的余数r m=n

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

思考6:如果用当型循环结构构造算法,则用辗 转相除法求两个正整数m、n的最大公约数的程序框 图和程序分别如何表示?

开始 输入m,n n=r m=n 求m除以n的余数r 是 r≠0 ? 否 输出m 结束

INPUT WHILE

m ,n r<>0

r=m MOD n m=n n=r WEND PRINT END m

练习:用辗转相除法求下列两数的最大公约数: (1)(225,135) 45 (2)(98,196) 98 24 (3)(72,168) (4)(153,119) 17

二、更相减损术 《九章算术》是中国古代的数学专著,其中的 “更相减损术”也可以用来求两个数的最大公约数, 即“可半者半之,不可半者,副置分母、子之数, 以少减多,更相减损,求其等也.以等数约之.” 意思是: 第一步:任意给定两个正整数,判断它们是否 都是偶数. 若是,用2约简;若不是,执行第二步. 第二步:以较大的数减去较小的数,接着把差 与较小的数比较,并以大数减小数.继续这个操作, 直到所得的数相等为止,则这个等数或这个数与约 简的数的乘积就是所求的最大公约数.

例1:用更相减损术求98与63的最大公约数. 因为63不是偶数,所以

98-63=35, 63-35=28, 35-28=7,
28-7=21,

21-7=14, 14-7=7.

所以最大公约数是7.

例2 分别用辗转相除法和更相减损术求168与93 的最大公约数. 辗转相除法:
168=93×1+75, 93=75×1+18, 75=18×4+3, 18=3×6. 更相减损术: 168-93=75, 93-75=18, 75-18=57, 57-18=39, 39-18=21, 21-18=3, 18-3=15, 15-3=12, 12-3=9, 9-3=6, 6-3=3.

例3 用更相减损术求80与36的最大公 约数.

例4 求325,130,270三个数的最大公约数.

因为325=130×2+65,130=65×2,所以325与130 的最大公约数是65.
因为270=65×4+10,65=10×6+5,10=5×2,所 以65与270最大公约数是5. 故325,130,270三个数的最大公约数是5.

练习:用更相减损术求两个正整数m,n的最大公 约数,可以用什么逻辑结构来构造算法?其算法步骤 如何设计?
第一步,给定两个正整数m,n(m>n). 第二步,计算m-n所得的差k. 第三步,比较n与k的大小,其中大者用m表示, 小者用n表示. 第四步,若m=n,则m,n的最大公约数等于m; 否则,返回第二步. 讨论:该算法的程序框图如何表示?

开始 输入m,n m≠n? 是 k=m-n n>k? 是 m=n n=k 否

m=k



输出m 结束 讨论:该程 序框图对应的程 序如何表述?

开始

输入m,n m≠n? 是 k=m-n
n>k? 是 m=n n=k 否

m=k



输出m 结束

INPUT m,n WHILE m≠n k=m-n IF n>k THEN m=n n=k ELSE m=k END IF WEND
PRINT END m

小结

1、辗转相除法.

2、更相减损术.

布置作业:
P45练习:1. P48习题1.3A组:1.

1.3.2

秦九韶算法

复习 1、什么是辗转相除法和更相减损术?

2、辗转相除法和更相减损术,是求两个正整 数的最大公约数的优秀算法,我们将算法转化为 程序后,就可以由计算机来执行运算,实现了古 代数学与现代信息技术的完美结合.

探究三、秦九昭算法
? 思考1,在初中,我们是如何求一个多项式的 值的?

? 思考2,已知一个n 次多项式 f(x)=anxn+an-1xn-1+…+a1x+a0当x=x0时,除 了用代入法求解外是否还有更好的方法呢?

秦九韶算法的基本思想
思考1:对于多项式f(x)=x5+x4+x3+x2+x+1,求 f(5)的值. 分析:把5代入多项式,若先计算各项的值, 然后再相加,那么一共要做: 4+3+2+1=10次乘法运算,5次加法运算.

思考2:另一种做法是先计算x2的值,然后依 次计算x2·x,(x2·x)·x,((x2·x)·x)·x的 值,这样每次都可以利用上一次计算的结果,这 时一共做了:

4次乘法运算,5次加法运算.

思考3:有没有更有效的算法呢?利用后一种算 法求多项式f(x)=anxn+an-1xn-1+?+a1x+a0的值,这 个多项式应写成哪种形式? f(x)=anxn+an-1xn-1+?+a1x+a0 =(anxn-1+an-1xn-2+?+a2x+a1)x+a0

=((anxn-2+an-1xn-3+?+a2)x+a1)x+a0
= ? =(?((anx+an-1)x+an-2)x+?+a1)x+a0. 这就是我国南宋时期数学家秦九韶在他的著作 《数书九章》中提出的算法.

思考4:对于f(x)=(?((anx+an-1)x+ an-2)x+?+a1)x+a0,
由内向外逐层计算一次多项式的值,其算法步骤如何? 第一步,计算v1=anx+an-1. 第二步,计算v2=v1x+an-2. 第三步,计算v3=v2x+an-3. … 第n步,计算vn=vn-1x+a0. 上述方法称为秦九韶算法.

思考5:在秦九韶算法中,记v0=an,那么第k步的 算式是什么?

vk=vk-1x+an-k (k=1,2,?,n)

例1 已知一个5次多项式为

f ?x? ? 4x 5 ? 2x 4 ? 3.5x 3 ? 2.6x 2 ? 1.7 x ? 0.8
用秦九韶算法求f(5)的值. 解:f(x)=((((4x+2)x+3.5)x-2.6)x+1.7)x-0.8.
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. 所以f(5)= =14130.2.

练习:阅读下列程序,说明它解决的实际问题是什么?
INPUT “x=”;a n=0 y=0 WHLE n<5 y=y+(n+1)*a∧n n=n+1 WEND PRINT y END
4 3 2 ? ? f x ? 5 x ? 4 x ? 3 x ? 2x ? 1 求多项式

在x=a时的值.

二、秦九韶算法的程序设计 思考1:用秦九韶算法求多项式的值,可以用什 么逻辑结构来构造算法?其算法步骤如何设计? 第一步,输入多项式的次数n,最高次项的系数 an和x的值. 第二步,令v=an,i=n-1.

第三步,输入i次项的系数ai.
第四步,v=vx+ai,i=i-1.

第五步,判断i≥0是否成立.若是,则返回第三 步;否则,输出多项式的值v.

开始
程序框图

输入n、an、x的值
v=an i=n-1 i=i-1 v=vx+ai

讨论:请参照程 序框图,写出该算法 程序.

输入ai i≥0? 否 是 输出v 结束

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 输入ai i≥0? 否 是 输出v 结束

小结 1.秦九韶算法计算多项式的值及程序设计. 2.计算机的一个很重要的特点就是运算速度快, 但评价算法好坏的一个重要标志是运算的次数,如 果一个算法从理论上需要超出计算机允许范围内的 运算次数,那么这样的算法就只能是一个理论算法. 在多项式求值的各种算法中,秦九韶算法是一个优 秀算法.

布置作业: P45练习:2. P48习题1.3A组:2.

1.3.3 K进制化十进制

复习

1.简述辗转相除法和更相减损术的用途及内容.

2、秦九韶算法的用途及内容.

将这些算法转化为程序,就可以由计算机来完 成相关运算.

进位制的概念 进位制是为了计数和运算方便而约定的记数系 统. 约定满二进一,就是二进制;

满十进一,就是十进制;
七天为一周,就是七进制;

十二个月为一年,就是十二进制; 六十秒为一分钟,六十分钟为一个小时,就是 六十进制;等等.
一般地,“满几进一”就是几进制.

“满K进一”就是K进制,其中k称为k进制的基数. 那么k是一个什么范围内的数?
思考1:十进制使用0~9十个数字,那么二进制、 五进制、七进制分别使用哪些数字? 与十进制类似,其它的进位制也可以按照位置原 则计数. 在十进制中10表示十,在二进制中10表示2.一 般地,若k是一个大于1的整数,则以k为基数的k进 制数可以表示为一串数字连写在一起的形式: anan-1?a1a0(k). 思考2:其中各个数位上的数字an,an-1,?,a1, a0的取值范围如何?

例如:十进制数3721表示的数可以写成:

3×103+7×102+2×101+1×100. 例1:把二进制数110011(2)化为十进制数. 110011(2)=1×25+1×24+0×23+0×22+1×21+1×20
=51 练习:把八进制数 5671(8)化为十进制数.

5671(8)=5×83+6×82+7×81+1×80=3001.

探究:如何将k进制数anan-1?a1a0(k)写成各数位 上的数字与基数k的幂的乘积之和的形式?

an an-1……a1a0(k)
= an×kn+ an-1×kn-1+ ……+ a1×k1+ a0×k0 讨论:在二进制中,0+0,0+1,1+0,1+1的值分 别是多少?

例2:二进制数110011(3)化为十进制数是什么数? 110011(3) =1×35+1×34+0×33+0×32+1×31+1×30 =243+81+3+1 =328. 讨论: an an-1……a1a0(2) 中ai化为十进制数是什么数?

ai2i-1

探究:如何改进上述算法,把其他进位制化为十 进制数?请举例说明. 练习:将下列各进制数化为十进制数. (1)10304(4) ; (2)4321(5). 10304(4)=1×44+3×42+4×40=308. 4321(5)=4×53+3×52+2×51+1×50=586.

例3:设计一个算法,把2进制数a(共有n位)化 为十进制数b,并转化成程序框图,写出程序.
第一步,输入a,2和n的值. 第二步,令b=0,i=1. 第三步,b=b+ai2i-1,i=i+1. 第四步,判断i>n 是否成立.若是,则执行第五 步;否则,返回第三步. 第五步,输出b的值.

练习:设计一个算法,把k进制数a(共有n位) 化为十进制数b. 第一步,输入a,k和n的值.

第二步,令b=0,i=1.
第三步,b=b+aiki-1,i=i+1. 第四步,判断i>n 是否成立.若是,则执行第五步; 否则,返回第三步. 第五步,输出b的值.

开始

输入a,k,n

程序框图

b=0 i=1

把a的右数第i位数字赋给t
b=b+t· ki-1 i=i+1 i>n? 是 输出b 结束 否

开始

INPUT “a,k,n=”;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

输入a,k,n b=0 i=1 把a的右数第i位数字赋给t

b=b+t· ki-1
i=i+1

i=i+1 LOOP UNTIL i>n PRINT b END

i>n? 是 输出b
结束



例4:已知20a1(2)=b10(3),求数字a,b的值. 20a1(2)=2×23+a×2+1=2a+17. b10(3)=b×32+1×3=9b+3. 所以2a+17=9b+3,即9b-2a=14. 故a=2,b=2.

小结 1、k进制数使用0~(k-1)共k个数字,但左 侧第一个数位上的数字(首位数字)不为0.

2、用 an an-1……a1a0(k) 表示k进制数,其中k 称为基数,十进制数一般不标注基数.
3、把k进制数化为十进制数的一般算式是: an an-1……a1a0(k) = an×kn+ an-1×kn-1+ ……+ a1×k1+ a0×k0

布置作业: P48习题1.3B组:1.

1.3.4 十进制化K进制

复习

1、“满几进一”就是几进制.
2、k进制使用0,1,??k-1这k个数字. 3、k进制数化为十进制数的一般算式:

an an-1……a1a0(k)
= an×kn+ an-1×kn-1+ ……+ a1×k1+ a0×k0 4、利用k进制数化十进制数的一般算式,可以 构造算法,设计程序,通过计算机就能把任何 一个k进制数化为十进制数.

练习:把二进制数100101(2)化为十进制数. 100101(2)=25+22+1=37.

讨论:怎样把十进制数89化为二进制数?

例1:把十进制数89化为二进制数.

观察下面的算式你有什么发现吗?

89=2×(2×(2×(2×(2×2+1)+1)+0)+0)+1 =1×26+0×25+1×24+1×23+0×22+0×21+1×20

=1011001(2).

例1:把十进制数89化为二进制数. 根据二进制“满二进一”的原则,可以用2连续去 除89或所得商,然后取余数. 余数 89 2 1 2 44 0 2 22 0 2 11 上述化十进 1 2 5 制数为二进制数 1 2 2 的算法叫做除2 0 2 1 取余法. 1 0

练习:把十进制数196化为五进制数. 除二取余法也可以推广为把十进制数化为k进 制数的算法,称为除k取余法. 5 5 5 5 196=1241(5) 196 39 7 1 0 余数 1 4 2 1

推广:怎样把十进制数转化为k进制数? 若十进制数a除以k所得的商是q0,余数是r0, 即a=k·q0+ r0; q0除以k所得的商是q1,余数是r1, 即q0=k·q1+ r1; ?? qn-1除以k所得的商是0,余数是rn, 即qn-1= rn, 那么十进制数a化为k进制数是:

a=rnrn-1?r1r0(2)

例2:根据上面的分析,将十进制数a化为二进 制数的算法步骤如何设计?

第一步,输入十进制数a的值. 第二步,求出a除以2所得的商q,余数r. 第三步,把所得的余数依次从右到左排列.
第四步,若q≠0,则a=q,返回第二步;否则, 输出全部余数r排列得到的二进制数.

练习:设计一个程序,实现“除k取余法”(k∈N, 2≤k≤9). 第一步,输入十进制数a和转化后的数的基数k. 第二步,求出a除以k所得的商q,余数r. 第三步,把所得的余数依次从右到左排列.

第四步,若q≠0,则a=q,返回第二步;否则, 输出全部余数r排列得到的k进制数.

开始

程序框图

输入a,k
求a除以k的商q 求a除以k的余数r

把所得的余数依次从右到左排列 a=q q=0? 是 输出全部余数r排 列得到的k进制数 结束 否

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

求a除以k的余数r
把所得的余数依次从右到左排列 a=q q=0? 是 输出全部余数r排 列得到的k进制数 结束



INPUT a,k b=0 i=0 DO q=a\k r=a MOD k b=b+r*10∧i i=i+1 a=q LOOP UNTIL q=0 PRINT b END

练习 将十进制数258分别转化为四进制数和六进制数.

4 4 4 4 4

258

余数

64 16 4 1 0

2 0 0 0 1

6 6 6 6

258 43 7 1 0

余数

0 1 1 1

258=10002(4)=1110(6)

练习 将五进制数1234(5)转化为七进制数. 1234(5)=1×53+2×52+3×5+4=194. 7 7 194 27 0 余数 5 6 3

7 3

1234(5)=365(7)

小结 1、进位制的概念及转化方法.

2、通过k进制数与十进制数的相互转化,实现 计算机操作.

布置作业: P45练习:3. P48习题1.3A组:3,4.


相关文章:
1.3算法案例
1.3算法案例_数学_高中教育_教育专区。为您服务教育网 http://www.wsbedu.com/ 1.3 算法案例 [学习目标导航] 学习提示 1. 通过对中国古代算法研究的学习,了...
高中数学必修3《1.3算法案例)》教案设计
1.3 算法案例 整体设计 教学分析 在学生学习了算法的初 步知识,理解了表示算法的算法www.xkb1.com 新课标第一网系列资料 www.xkb1.com 新课标第一网不用...
6.示范教案(1.3 算法案例)
1.3 算法案例 整体设计 教学分析 在学生学习了算法的初步知识, 理解了表示算法的算法步骤、 程序框图和程序三种不同 方式以后,再结合典型算法案例,让学生经历设计...
3-1(算法)
65页 1财富值 1.3算法案例 4页 免费 1.3算法案例 51页 免费 1.2.3算法...算法的表示方法 教学难点 流程图 教学准备 PPT 课件 算法 一、算法及其特性 1...
高中数学必修三导学案 1.2、算法案例
高中数学必修三导学案 1.2、算法案例_数学_高中教育_教育专区。高中数学必修三...四.例题分析(一)求最大公约数 对于两个正整数如何选择合适的方法求他们的最大...
1.3.2算法案例(秦九韶算法)[1]
1.3.2算法案例(秦九韶算法)[1]_理学_高等教育_教育专区。总场中学高中部...对数学进行虔心钻研,并广泛搜集历学、数学、星象、音律、营造等资料,进行分析、...
2016年高中数学 第一章 算法初步 1.3算法案例学案 新人教A版必修3
搜试试 3 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高中教育 高考...2016年高中数学 第一章 算法初步 1.3算法案例学案 新人教A版必修3_高考_高中...
Sha3算法
算法作为 SHA - 3 的加密标 准,现在我们分析一下...Merkle-Damgard 称, 在处理消息文本时,对 SHA-1 ...类方法 sha3AsCstring 使用实例方法 ...
实验三算法与分析设计
1; maze[0][0] = -1; 《算法分析与设计》实验报告 2 0 1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 1 0 1 0 1 1 ...
更多相关标签:
算法案例ppt | 1.3算法案例 | 1.3算法案例教案 | 智能算法30个案例分析 | 算法案例 | pagerank算法应用案例 | 算法的概念和案例 | 启发式算法的应用案例 |