第一章 算法初步

§1.3 算法案例--辗转相除法和更相减损术

制作人：计琳

【我们的任务】

1、阅读并体会辗转相除法和更相减损术的操作原理；

2、会用辗转相除法和更相减损术求两个数的最大公约数；

3、能根据辗转相除法和更相减损术设计完整的程序框图并写出算法程序。

【重点】自然语言、程序框图和算法语句表达辗转相除法和更相减损术。

【难点】辗转相除法和更相减损术的原理。

【自主导学与探究】

阅读教材P34～P37的有关内容，自主完成教材例1，思考并回答下列问题：

（一）辗转相除法

（1）辗转相除法，又叫欧几里得法，是一种求两个正整数的 的古老而有效的算法。

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

试一试：用辗转相除法求225和135的最大公约数．

问题一：辗转相除法的关键步骤是做带余除法：被除数＝除数×商＋余数。其中被除数，除数和除数、余数有相同的最大公约数，即gcd（被除数，除数）＝gcd（除数，余数）（gcd是greatest common divisor即最大公约数的缩写），为什么呢？（可以通过多媒体技术查询资料）

问题二：辗转相除法中，这样的带余除法进行到什么时候为止呢？为什么？

（3）辗转相除法的算法步骤：

第一步，给定 ；