kl800.com省心范文网

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


算 法 案 例
第一课时

复习引入
1.前面我们已经研究了算法,主要从算法 步骤、程序框图和编写程序三方面展开. 在程序框图中算法的基本逻辑结构有哪几 种?在程序设计中基本的算法语句有哪几 种?2.“求两个正整数的最大公约数”是 数学中的一个基础性问题,它有各种解决 办法,我们以此为案例,对该问题的算法 作一些探究.

2. 思考: 小学学过求两个正数的最大公约数的方法? 1)列举法: 2)短除法:

例:求下面两个正整数的最大公约数:

(1)用列举法求25和35的最大公约数 (2)用断除法求18和30的最大公约数
例:求下面两个正 整数的最大公约数:
(2) 2 3 18 9 3 30 15 5

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

如果两个数公有的质因数较大时(如8251与 6105),使用上述方法比较困难,因此,我们 今天要学习用另一种方法去求两数的公因数。

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

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

例1 求两个正数8251和6105的最大公约数。
解:8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 148=37×4+0
显然37是148和37的最大 公约数,也就是8251和 6105的最大公约数

辗转相除法是一个反复执行直到余数等于0才停 止的步骤,这实际上是一个循环结构。
用程序框图表示出右边的过程

m=n×q+r

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

r=m MOD n

m=n
n=r r=0? 否

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



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

算法步骤:
第一步:输入两个正整数m,n(m>n).
第二步:计算m除以n所得的余数r. 第三步:m=n,n=r. 第四步:若r=0,则m,n的最大公约数 等于m;

(2)、程序框图:
开始 输入m,n 求m除以n的余数r m=n n=r r=0? 是 否

否则转到第二步.

输出m

(3)、程序:
开始 输入m,n 求m除以n的余数r

INPUT m,n

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

DO r=m MOD n m=n n=r
LOOP UNTIL r=0

PRINT END

m

练习1:利用辗转相除法求两数4081与 20723的最大公约数.

? 解:20723=4081×5+318;
?

4081=318×12+265;

?

318=265×1+53;

? 265=53×5+0. ?所以,53为4081与20723的最大公

约数

二、更相减损术
1、背景介绍: (1)、《九章算术》中的更相减损术: 可半者半之,不可半者,副置分母、子之数,以少 减多,更相减损,求其等也,以等数约之。

(2)、现代数学中的更相减损术:
第一步:任意给定两个正整数;判断他们是否都是 偶数。若是,则用2约简;若不是则执行第二步。 第二步:以较大的数减较小的数,接着把所得的差 与较小的数比较,并以大数减小数。继续这个操作, 直到所得的减数和差相等为止,则这个等数就是所 求的最大公约数。

2、更相减损术

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

例2: 用更相减损术求98与63的最大公约数.

3、方法:

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

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

(1)、算法步骤 第一步:输入两个正整数a,b(a>b); 第二步:若a不等于b ,则执行第三步;否则转 到第五步; 第三步:把a-b的差赋予r;

第四步:如果b>r, 那么把b赋给a,把r赋给b;否 则把r赋给a,执行第二步; 第五步:输出最大公约数b.

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



结束

(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则得到,而更相减 损术则以减数与差相等而得到。

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


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

《算法案例 进位制》课件(... 17页 免费 人教版数学必修三课件:高... 20页...: 1.理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法...

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

数学1.3《算法案例》教案(新人教A版必修3)_年级数学_数学_小学教育_教育...(b)过程与方法 在辗转相除法与更相减损术求最大公约数的学习过程中对比我们...

高中数学:1.1.1《算法的概念》教案新人教版A必修3.doc

高中数学:1.1.1《算法的概念》教案新人教版A必修3.doc_数学_高中教育_教育...用自然语言描述算法. 多媒体课件 教学过程: 一、〖创设情境〗 引例 1:解二...

2016-2017学年新人教A版必修3高中数学 1.3算法案例教案...

2016-2017学年新人教A版必修3高中数学 1.3算法案例教案(精品)_数学_高中教育_教育专区。《算法案例——辗转相除法与更相减损术》教案 、教学目标: 1.理解...

2016-2017学年新人教A版必修3高中数学 1.3.1算法案例辗...

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

...高中数学人教A版必修3导学案 《1.3.1算法案例》

吉林省舒兰市第中学高中数学人教A版必修3导学案 《1.3.1算法案例》_数学_高中教育_教育专区。【学习目标】1.理解辗转相除法与更相减损术的含义,了解其执行...

《1.3算法案例(1)》教学案-公开课-优质课(人教A版必修...

《1.3算法案例(1)》教学案-公开课-优质课(人教A版必修三精品)_高一数学_...(二)研探新知 1.辗转相除法 例1 求两个正数8251和6105的最大公约数. (...

2016-2017学年新人教A版 必修3高中数学 1.3算法案例教...

2016-2017学年新人教A版 必修3高中数学 1.3算法案例教案(精品)_高二数学_数学_高中教育_教育专区。《算法案例——辗转相除法与更相减损术》教案 、教学目标:...

高中数学 1.3《算法案例--辗转相除法与更相减损术》测...

高中数学 1.1《算法与程序... 9页 10财富值喜欢此文档的还喜欢 高中数学新人教A版必修3学... 5页 1财富值 1.3 算法案例》一1 6页 免费 第章...

山东省高中数学《1.3 算法案例》教案1 新人教A版必修3

课时安排 3 课时 教学过程 第 1 课时 案例 1 辗转相除法与更相减损术 导入新课 思路 1(情境导入) 大家喜欢打乒乓球吧,由于东、西方文化及身体条件的不同,...