数学：1.3《算法案例--辗转相除法与更相减损术》课件(2)(新人教A版必修3)

数学：1.3《算法案例--辗转相除法与更相减损术》课件(2)(新人教A版必修3)

1.3

算法案例第一课时

2011-10-5

数学：1.3《算法案例--辗转相除法与更相减损术》课件(2)(新人教A版必修3)

问题提出

1 5730 p= 2

t

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

数学：1.3《算法案例--辗转相除法与更相减损术》课件(2)(新人教A版必修3)

2011-10-5

数学：1.3《算法案例--辗转相除法与更相减损术》课件(2)(新人教A版必修3)

知识探究( 知识探究(一):辗转相除法

思考1:18与30的最大公约数是多少？ 思考1:18与30的最大公约数是多少？你 1:18 的最大公约数是多少 是怎样得到的？ 是怎样得到的？ 先用两个数公有的质因数连续去除， 先用两个数公有的质因数连续去除， 一直除到所得的商是互质数为止， 一直除到所得的商是互质数为止，然 后把所有的除数连乘起来即为最大公 约数. 约数.

2011-10-5

数学：1.3《算法案例--辗转相除法与更相减损术》课件(2)(新人教A版必修3)

思考2:对于8251与6105这两个数， 思考2:对于8251与6105这两个数，由于 2:对于8251 这两个数 其公有的质因数较大， 其公有的质因数较大，利用上述方法求 最大公约数就比较困难. 最大公约数就比较困难.注意到 8251=6105×1+2146,那么8251 6105这 8251与 8251=6105×1+2146,那么8251与6105这 两个数的公约数和6105 2146的公约数 6105与 两个数的公约数和6105与2146的公约数 有什么关系？ 有什么关系？

2011-10-5

数学：1.3《算法案例--辗转相除法与更相减损术》课件(2)(新人教A版必修3)

思考3:又6105=2146×2+1813,同理， 思考3:又6105=2146×2+1813,同理， 3: 6105与2146的公约数和2146与1813的公 的公约数和2146 6105与2146的公约数和2146与1813的公 约数相等.重复上述操作，你能得到8251 约数相等.重复上述操作，你能得到8251 6105这两个数的最大公约数吗 这两个数的最大公约数吗？ 与6105这两个数的最大公约数吗？ 6105× 2146, 8251=6105 1+2146 8251=6105×1+2146, 6105=2146×2+1813 1813, 6105=2146×2+1813, 2146=1813×1+333 333, 2146=1813×1+333, 1813=333×5+148 148, 1813=333×5+148, 333=148×2+37 37, 333=148×2+37, 148=37× 148=37×4+0.2011-10-5

数学：1.3《算法案例--辗转相除法与更相减损术》课件(2)(新人教A版必修3)

思考4:上述求两个正整数的最大公约数 思考4:上述求两个正整数的最大公约数 4: 的方法称为辗转相除法 欧几里得算法. 辗转相除法或 的方法称为辗转相除法或欧几里得算法. 一般地，用辗转相除法求两个正整数m 一般地，用辗转相除法求两个正整数m, 的最大公约数， n的最大公约数，可以用什么逻辑结构来 构造算法？其算法步骤如何设计？ 构造算法？其算法步骤

如何设计？ 第一步，给定两个正整数m n(m>n). 第一步，给定两个正整数m,n(m n). 第二步，计算m除以n所得的余数r. 第二步，计算m除以n所得的余数r. 第三步，m=n, 第三步，m=n,n=r. 第四步， r=0, 第四步，若r=0,则m,n的最大公约数等 否则，返回第二步. 于m;否则，返回第二步.2011-10-5

数学：1.3《算法案例--辗转相除法与更相减损术》课件(2)(新人教A版必修3)

思考5:该算法的程序框图如何表示？ 思考5:该算法的程序框图如何表示？ 5:该算法的程序框图如何表示开始 输入m, 输入 ，n 除以n的余数 求m除以 的余数 除以 的余数r m=n n=r r=0? ? 是 输出m 输出2011-10-5

否

结束

数学：1.3《算法案例--辗转相除法与更相减损术》课件(2)(新人教A版必修3)

思考6:该程序框图对应的程序如何表述？ 思考6:该程序框图对应的程序如何表述？ 6:该程序框图对应的程序如何表述开始 输入m, 输入 ，n 除以n的余数 求m除以 的余数 除以 的余数r m=n n=r r=0? ? 是 输出m 输出2011-10-5

否

m, INPUT m,n DO r=m MODn m=n n=r LOOP UNTIL r=0 PRINT m END

结束

数学：1.3《算法案例--辗转相除法与更相减损术》课件(2)(新人教A版必修3)

思考7:如果用当型循环结构构造算法， 思考7:如果用当型循环结构构造算法， 7:如果用当型循环结构构造算法 则用辗转相除法求两个正整数m 则用辗转相除法求两个正整数m,n的最 大公约数的程序框图和程序分别如何表 示？

2011-10-5

数学：1.3《算法案例--辗转相除法与更相减损术》课件(2)(新人教A版必修3)

开始输入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

2011-10-5

数学：1.3《算法案例--辗转相除法与更相减损术》课件(2)(新人教A版必修3)

知识探究( 知识探 …… 此处隐藏：875字，全部文档内容请下载后查看。喜欢就下载吧 ……