nbhkdz.com冰点文库

1.3.1 算法案例1


〖创设情景,揭示课题〗
[问题1]:求出18与30的最大公约数? 2 18 30 3 9 15 3 5 ∴18和30的最大公约 数是2×3=6. 先用两个数公有的质因数 连续去除,一直除到所得 的商是互质数为止,然后 把所有的除数连乘起来.

[问题2]:求8251与6105的最大公约数?

例1 求两个正整数8251和610

5的最大公约数。
分析:8251与6105两数都比较大,而且没 有明显的公约数,如能把它们都变小一点,根 据已有的知识即可求出最大公约数. 解:8251=6105×1+2146 显然8251与6105的最大公约数也必是2146 的约数,同样6105与2146的公约数也必是8251 的约数,所以8251与6105的最大公约数也是 6105与2146的最大公约数。

具体过程:
8251=6105×1+2146 显然37是148和37的最大公

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

以上我们求最大公约数 的方法就是辗转相除法。 也叫欧几里德算法,它是 由欧几里德在公元前300年 左右首先提出的。

辗转相除法定义:

所谓辗转相除法,就是对于给定的两个数, 用较大的数除以较小的数。若余数不为零,则 将余数和较小的数构成新的一对数,继续上面 的除法,直到大数被小数除尽,则这时较小的 数就是原来两个数的最大公约数。

思考一
你能把辗转相除法编成一个计算机程序吗?

辗转相除法是一个反复执行直到余数等于0才停止的步骤,这实际上 是一个循环结构。

m=n×q+r

用程序框图表示出右边的过程

8251=6105×1+2146
6105=2146×2+1813 2146=1813×1+333 1813=333×5+148

r=m MOD n

m=n
n=r r=0?



333=148×2+37 148=37×4+0

辗转相除法求最大公约数 算法:

? ? ? ?

第一步,给定两个正整数m,n 第二步,计算m除以n所得的余数r 第三步,m=n,n=r 第四步,若r=0,则m,n的最大公约数等 于m;否则返回第二步

程序:

程序框图
开始
输入两个正整数m,n

INPUT “m,n=”;m,n
DO

r=m MOD n
m=n

r=m MOD n
m=n n=r

n=r
LOOP UNTIL r=0 PRINT m END


r=0?


输出m

结束

思考二
? 你能用当型循环结构构造算法,求两个正 整数的最大公约数吗?试画出程序框图和 程序。

程序:
INPUT “m,n=”;m,n

程序框图
开始
输入两个正整数m,n

r=m MOD n
WHILE R<>0

r=m MOD n
r=m MOD n
n=r m=n r<>0?
否 是

m=n
n=r

r=m MOD n
WEND PRINT n END

输出n

结束

二、更相减损术
背景介绍:
(1)、《九章算术》中的更相减损术: 可半者半之,不可半者,副置分母、子之数,以少减多, 更相减损,求其等也,以等数约之。 (2)、现代数学中的更相减损术: 第一步:任意给定两个正整数;判断他们是否都是偶数。 若是,则用2约简;若不是则执行第二步。 第二步:以较大的数减较小的数,接着把所得的差与较小 的数比较,并以大数减小数。继续这个操作,直到所得的 减数和差相等为止,则这个等数就是所求的最大公约数。

3、方法:更相减损术 例2: 用更相减损术求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。

12

思考三:你能根据更相减损术设计程 序,求两个正整数的最大公约数吗?

程序:
开始
输入:a,b

INPUT “a,b”;a,b i=0

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

i=0

i=i+1
a MOD 2=0且b MOD 2=0? Y

a=a/2,b=b/2

b>a?
Y

N N

t=a,a=b,b=t a=a-b
N

a=b?
输出:a×2i 结束 Y

a=a/2 b=b/2 i=i+1 WEND DO IF b>a THEN t=a a=b b=t END IF a=a-b LOOP UNTIL a=b PRINT a*2^i END

小结

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

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

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


1.3.1算法案例

1.3算法案例(三) 2页 1财富值 1.3.1算法案例(一) 23页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...

高中数学必修3《1.3算法案例)》教案设计

高中数学必修3《1.3算法案例)》教案设计_数学_高中教育_教育专区。www.xkb1.com 新课标第一网系列资料 www.xkb1.com 新课标第一网不用注册,免费下载! 1.3...

1.3算法案例

教学重点 教学难点 教学设想 教学用具 黑板 教学方法 讲议结合 课时安排 4 1.3 算法案例 1、辗转相除法与更相减损术 板书设计 2、 秦九韶算法 3、各种进位...

人教版高中数学必修三《1.3算法案例(教、学案)

临清三中数学组 编写人:赵万龙 审稿人: 郭振宇 李怀奎 1.3 算法案例 【教学目标】 : 1.理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算...

高中数学必修三1.3算法案例

高中数学必修三1.3算法案例_高一数学_数学_高中教育_教育专区。1.3算法案例 1——辗转相除法与更相减损术》导学案【学习目标】 1、 会用辗转相除法和更相减...

高中数学必修三1.3算法案例练习

高中数学必修三1.3算法案例练习_数学_高中教育_教育专区。一、选择题 1.用辗转...( A. 1 B. 2 C. 3 D. 4 4.运行下面的程序,当输入 84,36 时,输出...

1.3 中国古代数学中的算法案例

1.3 中国古代数学中的算法案例_数学_高中教育_教育专区。1.3 中国古代数学中的算法案例 【入门向导】 秦朝末年,楚汉相争.一次,韩信率 1 500 名将士与楚王大将...

数学:1.3 《算法案例》教案(新人教A版必修3)

数学:1.3算法案例》教案(新人教A版必修3)_数学_高中教育_教育专区。1.3算法案例》教案 1.3 算法案例、二课时 辗转相除法与更相减损术 (1)...

1.3算法案例学案(完美版)_图文

河北衡水重点中学高一数学学案 1.3 算法案例 辗转相除法与更相减损术 教学目标 (a)知识与技能 1.理解辗转相除法与更相减损术中蕴含的数学原理,并能 根据这些...

6.示范教案(1.3 算法案例)

教学难点:体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力. 课时安排 3 课时 教学过程 第 1 课时 案例 1 辗转相除法与更相减损术 导入...