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算法案例1_数学_高中教育_教育专区。1.3 算法案例 第一、二课时 辗转相除法与更相减损术 (1)教学目标 (a)知识与技能 1.理解辗转相除法与更相减损术中...

1.3.1算法案例

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

1.3_算法案例

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

1.3算法案例

1.3算法案例_高一数学_数学_高中教育_教育专区。1.3算法案例1.3 算法案例 教学目标:掌握三个案例,理解辗转相除法,更相减损术,秦九韶算法,进位制。 教学重、...

§1.3.1算法案例1 一课一练

§1.3.1 算法案例 1 1、下列各组关于最大公约数的说法中不正确的是 A、16 和 12 的最大公约数是 4 B、78 和 36 的最大公约数是 6 C、85 和 357...

1.3算法案例(1)

1.3 算法案例(1) 数学组: 时间: 课型:新授课 教学目标 1.知识目标 2.能力目标 3.德育目标 理解算法案例的算法步骤和程序框图. 引导学生得出自己设计的算法...

1.3 算法案例知识点,试题及答案

1.3 算法案例知识点,试题及答案_数学_高中教育_教育专区。一、知识要点及方法辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的: 1. 若 r...

1.3算法案例

建业外国语中学教学案 高一数学必修三 序号: 1.3 撰稿人: 班级: 刘小颖 课姓 算法案例型: 新授课 名: 审核人: 使用日期: 刘小颖 、标学装 (1)理解辗转...

《1.3 算法案例(1)》测试题

1.3 算法案例(1)》测试题_数学_高中教育_教育专区。《1.3 算法案例(1)》测试题 一、选择题 1.下列说法中正确的个数( ). ⑴辗转相除法也叫欧几里德...