高效课堂一线名师 · 名校学案 · 联校开发 高中数学 · 必修 3 人民教育出版社高效课堂1.3 算法案例高效课堂1.3.4 十进制化 K 进制1.3.1 辗转相除法和更相减损术1.3.2 秦九韶算法1.3.3 K 进制化十进制1.3 算法案例高效课堂1.3.1 辗转相除法和更相减损术高效课堂复习1. 研究一个实际问题的算法，主要从哪几方面展开？2. 在程序框图中算法的基本逻辑结构有哪几种？3. 在程序设计中基本的算法语句有哪几种？算法步骤、程序框图和编写程序三方面展开 .顺序结构、条件结构、循环结构输入语句、输出语句、赋值语句、条件语句、循环语句高效课堂一、辗转相除法 思考 1:18 与 30 的最大公约数是多少？你是怎样得到的？ 先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数 . 高效课堂 思考 2: 对于 8251 与 6105 这两个数，它们的最大公约数是多少？你是怎样得到的？ 由于它们公有的质因数较大，利用上述方法求最大公约数就比较困难 . 有没有其它的方法可以较简单的找出它们的最大公约数呢？高效课堂 思考 3 ：注意到 8251=6105×1+2146 ，那么8251 与 6105 这两个数的公约数和 6105 与 2146 的公约数有什么关系？ 我们发现 6105=2146×2+1813 ，同理， 6105 与2146 的公约数和 2146 与 1813 的公约数相等 . 思考 4 ：重复上述操作，你能得到 8251 与6105 这两个数的最大公约数吗？2146=1813×1+333 ，148=37×4+0.333=148×2+37 ，1813=333×5+148 ，8251=6105×1+2146 ，6105=2146×2+1813 ，高效课堂 上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法 .第一步，给定两个正整数 m ， n(m>n).第二步，计算 m 除以 n 所得的余数 r. 第三步， m=n ， n=r. 第四步，若 r=0 ，则 m ， n 的最大公约数等于m ；否则，返回第二步 . 思考 5: 你能把辗转相除法编成一个计算机程序吗？高效课堂程序框图开始输入m ， n求 m 除以 n 的余数 rm=nn=rr=0？是输出 m结束否INPUT m ， nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND高效课堂 思考 6: 如果用当型循环结构构造算法，则用辗转相除法求两个正整数 m 、 n 的最大公约数的程序框图和程序分别如何表示？高效课堂开始输入m ， n求 m 除以 n 的余数 rm=nn>0 ？否输出 m结束是n=rINPUT m ， nWHILE n...
