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

11.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:当两个数的公有质因数较大时,我们怎 样去求两个数的最大公约数呢? 辗转相除法:用于求两个正整数的最大公约数 的一种算法,是由欧几里得在公元前300年 左右首先提出的,因而又叫做欧几里得算法. 定义:所谓的辗转相除法,就是对于给定的两个 数,用较大的数除以较小的数,若余数不为零, 则将余数和较小的数构成新的数对,继续上 面的除法,直到大数被小数除尽,则这是较小 的数就是原来两个数的最大公约数.

辗转相除法的理论基础:
定理: 已知m,n,r为正整数,若m=nq+r(0≤r<n)(即r=m MOD n),则(m,n)=(n,r)。

分析:m=nq+r r=m-nq

…… ① …… ②

例1、求8251和6105的最大公约数。 解: (8251,6105) 8251=6105×1+2146 =(6105,2146) 6105=2146 ×2+1813 =(2146,1813) 2146=1813 ×1+333 =(1813,333) 1813=333 ×5+148 =(333,148) 333=148 ×2+37 =(148,37) 148=37 ×4 =37

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

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

思考4:你能根据辗转相除法的算法步骤画出它的 程序框图以及相应的程序语句吗?

开始 输入:m,n INPUT m,n r=1 r=m MOD n WHILE r<>0 r=m MOD n m=n m=n n=r n=r WEND PRINT m r=0? Y END 输出:m 结束

N

程序: INPUT “m,n=”;m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END

探究二,更相减损术
<九章算术> “可半者半之,不可半者,副置分

母、子之数,以少减多,更相减损,求其 等也,以等数约之。”
同理:a,b,c为正整数,若a-b=c,则(a,b)=(b,c)。 “更相减损术”(也是求两个正整数的最大公约数的算法) 步骤: 第一步:任意给定两个正整数;判断他们是否都是偶数。 若是,则用2约简;若不是则执行第二步。 第二步:以较大的数减较小的数,接着把所得的差与较 小的数比较,并以大数减小数。继续这个操作,直到所 得的减数和差相等为止,则这个等数就是所求的最大公 约数。

例2、用更相减损术求98与63的最大公约数 (自己按照步骤求解) 解:由于63不是偶数,把98和63以大数减小数,并辗转相减。 (98,63) =(63,35) 98-63=35 63-35=28 =(35,28)

35-28=7
28-7=21 21-7=14 14-7=7

=(28,7)
=(21,7) =(14,7) =(7,7) =

7

所以,98和63的最大公约数等于7。

练习:用更相减损术求下列两数的最大公约数:

(1)(225,135) 45 (3)(72,168) 24

(2)(98,196) 98 (4)(153,119) 17

思考:更相减损直到何时结束?运用的是哪种算法结构? 更相减损是一个反复执行直到减数等于差时停止的步骤, 这实际也是一个循环结构

讨论:你能根据更相减损术的算法步骤 画出其程序框图并写出程序语句吗?
INPUT m,n
开始
输入:m,n N m≠n? Y M>n? Y m=m-n

WHILE m<>n IF m>n THEN m=m-n

N

ELSE
n=n-m
n=n-m

END IF WEND

输出:m 结束

PRINT m END

区别: ? 计算上辗转相除法以除法为主,更相减损术以减法为主; ? 在计算次数上,辗转相除法计算次数相对较少,特别当 两个数大小差别较大时计算次数的区别较明显; ? 从结果输出的时候看,辗转相除法当余数为0时输出除 数,更相减损术当差和减数相等时输出差。 联系:都是求最大公约数的方法。因为做一次除法与做若干 次减法效果相同,商就是减法的次数,余数就是最后的 差,由此可知二者是完全统一的!

思考:辗转相除法与更相减损术有 什么区别和联系?

例3,求三个数319,377,116的最 大公约数(计算,不编程)
辗转相除法 更相减损术

1,4830与3289的最大公约数为_______ 2,用更相减损术求87与27的最大公约数时, 反复相减,直至求出最大公约数,需要进 行减法运算的次数是______ 3,用辗转相除法求87与27的最大公约数,需 要进行除法运算的次数是_____ 4,46,115,276的最大公约数是____

算 法 案 例
第二课时

探究三、秦九昭算法
?

思考1,在初中,我们是如何求一个多项式的 值的?

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

探究:以f(x)=a5x5+a4x4+…+a1x+a0为例
秦九昭算法问题: 秦九昭(约1202~1261)是我国南宋时期享誉世界 的数学家,在他的代表作《数学九章》中介绍了 计算一个n次多项式值的算法,即“秦九韶算 法”。它的特点是:通过一次式的反复计算,逐 步得出高次多项式的值,对于一个n次多项式, 只需做n次乘法和n次加法即可。 秦九韶算法是求一元多项式值的一种方法,现在它 仍是世界上多项式求值最先进的方法,这一成就 比西方同样的算法早五六百年,且该算法很容易 在计算机上实现!

新课讲解:

怎样求多项式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?1 x ? ? ? a1 x ? a0 一种改写方 对该多项式按下面的方式进行改写: 式?最后的 结果是什么? n n ?1 f ( x) ? an x ? an?1 x ? ? ? 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次多项式,只需做n次乘 法和n次加法即可。

例: 已知一个五次多项式为
5 4 3

f ( x) ? 5x ? 2 x ? 3.5x ? 2.6 x ? 1.7 x ? 0.8
2

用秦九韶算法求这个多项式当x = 5的值。 解: 将多项式变形:

f ( x) ? ((((5 x ? 2) x ? 3.5) x ? 2.6) x ? 1.7) x ? 0.8

按由里到外的顺序,依此计算一次多项式当x = 5时的值:

v0 ? 5 v1 ? 5 ? 5 ? 2 ? 27 v2 ? 27 ? 5 ? 3.5 ? 138.5 v3 ? 138.5 ? 5 ? 2.6 ? 689.9 v4 ? 689.9 ? 5 ? 1.7 ? 3451.2 v5 ? 3451.2 ? 5 ? 0.8 ? 17255.2

你从中看到了 怎样的规律? 怎么用程序框 图来描述呢?

所以,当x = 5时,多项式的值等于17255.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
结束

思考:你能设计程序把“秦九韶算法”表示出来
吗?

(1)、算法步骤:
第一步:输入多项式次数n、最高次项的系数an和x 的值. 第二步:将v的值初始化为an,将i的值初始化为n-1. 第三步:输入i次项的系数an. 第四步:v=vx+ai, i=i-1. 第五步:判断i是否大于或等于0,若是,则返回第 三步;否则,输出多项式的值v。

(2)程序框图:

开始

输入n,an,x

V=an

i=n-1 i=i-1

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

Y

结束

(3)程序:
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

练习:
1:

2:

3:

4:

5:

6,用秦九昭算法求多项式 f(x)=x4+2x3+3x2+x+1,当x=2时的值时,第 一次运算的步骤是( ) A 1×2 B 24 C 2+2 D 1×2+2 7,用秦九昭算法求多项式 f(x)=a3x3+a2x2+a1x+a0,当x=x0时的值最多要 做____次乘法运算,_____次加法运算。 8,用秦九昭算法,求 f(x)=3x5-2x3+2x2-1当x=2时的值。

4, 用秦九昭算法求 f ( x) ? an x ? an ?1 x
n

n ?1

? ? ? a1 x ? a0

当x ? x0时的值,计算公式是( ) ?v0 ? a0 A, ? ?vk ? vk ?1 x ? an ? k (k ? 1,2,3, ? , n) ?v0 ? an B, ? ?vk ? vk ?1 x ? an ? k (k ? 1,2,3, ? , n) ?v0 ? an C, ? ?vk ? vk ?1 x ? ak (k ? 1,2,3, ? , n) ?v0 ? a0 D, ? ?vk ? vk ?1 x ? ak (k ? 1,2,3, ? , n)

10,用秦九昭算法计算多项式f(x)=12+35x8x2+79x3+6x4+5x5+3x6在x=-4时的值时,v3 的值为( ) A -845 B 220 C -57 D 34
?

探究四、进位制
情境创设 这个问题中,提高了二进制的概念,那 古时候,当边境有敌人来犯时,守边的官兵 么什么是二进制呢?它与我们常用的十 通过在烽火台上点火向国内报告,如图: 进制有什么关系呢?它们之间是否可以 烽火台上点火表示数字 1,不点火表示数字 互相转化呢?请带着以上问题阅读书 0,约定二进制数对应的十进制数的单位是 P40 1000 ,请你计算一下,这组烽火台表示有 多少敌人入侵?

探究一、进位制的概念
思考1,我们在学习过程中所处理的数据一般 都是几进制的,你能说说它有什么规律吗? 你还能举出哪些有关进位制的例子? 谈谈你对进位制的认识! 进位制是人们为了计算和运算方便而约定的 记数系统,约定满二进一,就是二进制; 满十进一,就是十进制等。即“满几进一” 就是几进制,几进制的基数就是几。

探究二、进位制之间的转换
思考1:根据十进制的表示方法,你能把k进 制的数转化为十进制吗? 例1,把二进制数101011(2)转化为十进制数 例2,把五进制数10243(5)转化为十进制数 思考2:通过上面的学习,已经知道如何将k 进制数转化为十进制数,对于情境创设中 的问题你能解决吗? 思考3:根据例题,怎样改进算法让计算机来 执行呢?(把k进制数a(共有n位)化为十 进制数b)

思考4:怎样把十进制数转化为其他非 十进制数呢?
例1把89转化为二进制数 例2,把3147转化为八进制数 思考5:你能根据上面的举例设计出把一个十 进制的数转化为k进制数的算法吗?

除k取余法
思考6:对于非十进制数之间如何进行转换呢?

练习
1,以下各数可能是七进制数的是( ) A 7601 B 2138 C 2008 D 1632 2,将数30012(4)转化为十进制数为( ) A 524 B 774 C 256 D 260 3,把十进制数15转化为二进制数为_____ 4,把11011011(2)转换为十进制数 5,把67转化为二进制数 6,二进制数算式1010(2)+10(2)的值是__

7,完成下列进位制之间的转化: (1)314(5)=______(10)=_______(7) (2)325(6)=________(2) 8,将四个数111111(2),210(6),1000 (4),71(8),按从小到大排列为____ 9,把10110(4)转化为十进制数 10,已知175(k)=125,求k的值



更多相关文章:
第11课时5.4.1算法案例一(韩信点兵)已对
11 课时 5.4 算法案例重点难点重点:通过案例分析,体会算法思想,熟练算法设计,...【解】 算法如下: m←2 While Mod(m,5)≠2 或 Mod(m,7)≠3 或 Mod...
第11课时—算法案例(2)
南师大附校 高二数学教案 必修 3 算法案例(2) §1.4 算法案例(2) 教学目标: (1)理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法 分析...
1.3_算法案例
1.3_算法案例_高一数学_数学_高中教育_教育专区。1.3 算法案例 教学分析 在...下面来求 20 与 9 的最大公约数, 20-9=11, 11-9=2, 9-2=7, 7-2...
《1.3 算法案例》第二课时
必修3 数学(适用新课标人教版) 1.3 算法案例一、选择题 1、下列各组关于最...(3)45,385. 必修 3 数学(适用新课标人教版) 11、试写出一个算法,并画出...
6.示范教案(1.3 算法案例)
6.示范教案(1.3 算法案例)_数学_高中教育_教育专区。1.3 算法案例 整体设计...下面来求 20 与 9 的最大公约数, 20-9=11, 11-9=2, 9-2=7, 7-2...
1.3 算法案例
基本算法语句与算法案例练... 3页 免费 1.1.2程序框图与算法的基本... 36...下面来求 20 与 9 的最大公约数, 20-9=11, 11-9=2, 9-2=7, 7-2...
苏教版数学必修3算法案例(全套)
§1.4 算法案例(1) 教学目标:(1)介绍中国古代算法的案例-韩信点兵-孙子问题;...11 2.有一堆火柴棒,根的数,最后余下两根;五根无根的数,最后余下...
银行家算法例子+答案
银行家算法例子+答案。软件工程1、设系统中有 3 种类型的资源(A,B,C)和 5...3 4? ? 0 6? ? 0 0? 0 0? ? V '= (7 4 11) 按照上述同样的...
第10课时-§1.3算法案例——进位制
(理科数学)备课组教案课题:§1.3 算法案例——进位制 教学目标: 知识与能力:...二进制数要满足“满二进一”的原则 89=2×44+1 44=2×22+0 22=2×11+...
更多相关标签:
1.3算法案例    1.3算法案例教案    1.3算法案例ppt    算法导论 22.3 11    算法导论11.3    算法导论 11.3 2    算法案例ppt    智能算法30个案例分析    

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

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