nbhkdz.com冰点文库

数学:1.3.1《算法案例(辗转相除法)》课件1(新人教版A必修3)

时间:2011-05-20


算 法 案 例
第一课时

复习引入 1. 回顾算法的三种表示方法: 回顾算法的三种表示方法: )、自然语言 (1)、自然语言 )、 )、程序框图 三种逻辑结构) (2)、程序框图 (三种逻辑结构) )、 )、程序语言 (3)、程序语言 )、 (五种基本语句) 五种基本语句)

2. 思考: 思考: 小学学过的求两个数的最大公

约数的方法? 小学学过的求两个数的最大公约数的方法?

先用两个数公有的质因数 连续去除, 连续去除,一直除到所得的商 是互质数为止, 是互质数为止,然后把所有的 除数连乘起来. 除数连乘起来

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

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

思考:除了用这种方法外还有没有其它方法? 思考:除了用这种方法外还有没有其它方法? 的最大公约数? 例:如何算出8251和6105的最大公约数? 如何算出 和 的最大公约数

新课讲解: 新课讲解: 一、辗转相除法(欧几里得算法) 辗转相除法(欧几里得算法)

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

2、步骤: (以求 、步骤: 以求8251和6105的最大公约数的过程为例) 的最大公约数的过程为例) 和 的最大公约数的过程为例 第一步 用两数中较大的数除以较小的数,求得商 用两数中较大的数除以较小的数, 和余数 8251=6105×1+2146 × 结论: 的公约数就是6105和2146的 结论: 8251和6105的公约数就是 和 的公约数就是 和 的 公约数, 的最大公约数, 公约数,求8251和6105的最大公约数,只要求出 和 的最大公约数 6105和2146的公约数就可以了。 的公约数就可以了。 和 的公约数就可以了 第二步 对6105和2146重复第一步的做法 和 重复第一步的做法 6105=2146×2+1813 × 同理6105和2146的最大公约数也是 的最大公约数也是2146和1813 同理 和 的最大公约数也是 和 的最大公约数。 的最大公约数。

完整的过程 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 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

显然37是 显然 是148和37的最大 和 的最大 公约数,也就是8251和 公约数,也就是 和 6105的最大公约数 的最大公约数

辗转相除法是一个反复执行直到余数等于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

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

(2)、程序框图: (2)、程序框图:
开始 输入m,n 输入 r=m MOD n m=n n=r 否 r=0? 是 输出m 输出 结束

(3)、程序: (3)、程序:
INPUT “m,n=“;m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END

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

开始
输入m, 输入 ,n

n=r m=n 除以n的余数 求m除以 的余数 除以 的余数r n>0? ? 否 输出m 输出 结束 是

m, INPUT m,n WHILE n>0 0 r=m MODn m=n n=r WEND PRINT m END

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

2、更相减损术 、

算理:所谓更相减损术, 算理:所谓更相减损术,就是对于给 定的两个数, 定的两个数,用较大的数减去较小的 数,然后将差和较小的数构成新的一 对数,再用较大的数减去较小的数, 对数,再用较大的数减去较小的数, 反复执行此步骤直到差数和较小的数 相等, 相等,此时相等的两数便为原来两个 数的最大公约数。 数的最大公约数。

例: 用更相减损术求98与63的最大公约数. 用更相减损术求98与63的最大公约数. 98 的最大公约数 解:由于63不是偶数,把98和63以大数减小数, 由于63不是偶数, 98和63以大数减小数, 63不是偶数 以大数减小数 并辗转相减 98-63= 98-63=35 63-35= 63-35=28 35-28= 35-28=7 28- 28-7=21 21- 21-7=21 14- 14-7=7 所以,98和63的最大公约数等于7 所以,98和63的最大公约数等于7 的最大公约数等于

3、方法: 、方法:

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

(1)、算法步骤 、 第一步:输入两个正整数 第一步:输入两个正整数a,b(a>b); 第二步: 不等于b 则执行第三步; 第二步:若a不等于 ,则执行第三步;否则转 不等于 则执行第三步 到第五步; 到第五步; 第三步: 的差赋予r; 第三步:把a-b的差赋予 的差赋予 第四步:如果 那么把b赋给 赋给a,把 赋给 赋给b;否 第四步:如果b>r, 那么把 赋给 把r赋给 否 则把r赋给 赋给a,执行第二步; 则把 赋给 ,执行第二步; 第五步:输出最大公约数 第五步:输出最大公约数b.

(2)、 (2)、程序框图
开始
输入a,b 输入 a≠b? 是 r=a-b a=r 否 r<b? 是 a=b b=r 输出b 输出 结束 否

(3)、 (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、用更相减损术求两个正数84与72的最大公约数. 、用更相减损术求两个正数 与 的最大公约数 的最大公约数.

思路分析:先约简,再求 与 的最大公 思路分析:先约简,再求21与18的最大公 约数,然后乘以两次约简的质因数 然后乘以两次约简的质因数4。 约数 然后乘以两次约简的质因数 。
2、求324、243、135这三个数的最大公约数。 、 、 、 这三个数的最大公约数。 这三个数的最大公约数

思路分析: 思路分析:求三个数的最大公约数可以先求出 两个数的最大公约数, 两个数的最大公约数,第三个数与前两个数的 最大公约数的最大公约数即为所求。 最大公约数的最大公约数即为所求。

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

小结 1.辗转相除法 辗转相除法, 1.辗转相除法,就是对于给定的两个正整 用较大的数除以较小的数, 数,用较大的数除以较小的数,若余数不为 则将余数和较小的数构成新的一对数, 零,则将余数和较小的数构成新的一对数, 继续上面的除法,直到大数被小数除尽为止, 继续上面的除法,直到大数被小数除尽为止, 这时的较小的数即为原来两个数的最大公约 数. 更相减损术, 2. 更相减损术,就是对于给定的两个正 整数,用较大的数减去较小的数, 整数,用较大的数减去较小的数,然后将差 和较小的数构成新的一对数, 和较小的数构成新的一对数,继续上面的减 直到差和较小的数相等, 法,直到差和较小的数相等,此时相等的两 数即为原来两个数的最大公约数. 数即为原来两个数的最大公约数.


...章算法初步1.3算法案例第一、二课时《辗转相除法与...

人教A版高中数学必修三章算法初步1.3算法案例、二课时《辗转相除法与更相减损术》教案_教学案例/设计_教学研究_教育专区。1.3 算法案例、二课时 ...

...学年新人教A版 必修3高中数学 1.3 算法案例 第一课...

2016-2017学年新人教A版 必修3高中数学 1.3 算法案例课时 辗转相除法与更相减损术说课稿(精品)_高二数学_数学_高中教育_教育专区。高中数学 1. 3 算法...

2016-2017学年新人教A版必修3高中数学 1.3.1 辗转相除...

2016-2017学年新人教A版必修3高中数学 1.3.1 辗转相除法与更相减损术教案 ...课题 更相减损术与辗转相除法 授课时间 课型 新授 1.理解算法案例的算法步骤...

...中学高中数学 1.3 算法案例 第一课时 辗转相除法与...

河南省确山县第二高级中学高中数学 1.3 算法案例课时 辗转相除法与更相减损术学案 新人教A版必修3_高二数学_数学_高中教育_教育专区。河南省确山县第二高...

算法案例 辗转相除法与更相减损术秦九韶算法与进位制第...

算法案例 辗转相除法与更相减损术秦九韶算法与进位制第1课时练习-数学高一必修3章算法初步1.3人教A版_数学_高中教育_教育专区。人教 A 版 第1.3 ...

人教A版高中数学必修三算法案例第1课时辗转相除法与更...

人教A版高中数学必修三算法案例1课时辗转相除法与更相减损术课时练习_教学案例/设计_教学研究_教育专区。1.3.1 辗转相除法与更相减损术 一、选择题 1.用...

人教A版数学必修三教案:§1.3算法案例(辗转相除法与更...

人教A版数学必修三教案:§1.3算法案例(辗转相除法...(二)推进新课、新知探究、提出问题 (1)怎样用短...《九章算术》是中国古 http://www.xiexingcun.com...

人教A版高中数学必修三第一章算法案例(1)第一、二课时...

人教A版高中数学必修三算法案例(1)、二课时辗转相除法与更相减损教案_教学案例/设计_教学研究_教育专区。第、二课时 辗转相除法与更相减损术 (1)...

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

《1.3 算法案例(1)》测试题_数学_高中教育_教育专区。《1.3 算法案例(1)...程序时,要用到循环语句 A.1 B.2 C.3 D.4 考查目的:考查辗转相除法的...

算法案例——辗转相除法

算法案例——辗转相除法_初一数学_数学_初中教育_...苏教版普通高中课程标准实验教科书必修 3章第...整数 a, b(a ? b) 的最大公约数的个算法。...