问题提出 1. 研究一个实际问题的算法，主要从算法步骤、程序框图和编写程序三方面展开 . 在程序框图中算法的基本逻辑结构有哪几种？在程序设计中基本的算法语句有哪几种？ 2.“ 求两个正整数的最大公约数”是数学中的一个基础性问题，它有各种解决办法，我们以此为案例，对该问题的算法作一些探究 .知识探究（一） : 辗转相除法思考 1:18 与 30 的最大公约数是多少？你是怎样得到的？ 先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数 . 思考 2: 对于 8251 与 6105 这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难 . 注意到8251=6105×1+2146 ，那么 8251 与 6105这两个数的公约数和 6105 与 2146 的公约数有什么关系？ 思考 3: 又 6105=2146×2+1813 ，同理， 6105 与 2146 的公约数和 2146 与1813 的公约数相等 . 重复上述操作，你能得到 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 ，思考 4: 上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法 . 一般地，用辗转相除法求两个正整数 m ， n 的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？ 第一步，给定两个正整数 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结束否思考 6: 该程序框图对应的程序如何表述？INPUT m ， nDOr=m MODnm=nn=rLOOP UNTIL r=0PRINT mEND开始输入 m ， n求 m 除以 n 的余数rm=nn=rr=0 ？是输出 m结束否思考 7: 如果用当型循环结构构造算法，则用辗转相除法求两个正整数 m ， n 的最大公约数的程序框图和程序分别如何表示？开始输入m ， n求 m 除以 n 的余数 rm=nn>0？否输出 m结束是n=rINPUT m ， nWHILE n>0r=m MODnm=nn=rWENDPRINT mEND知识探究（二） : 更相减损术 思考 1: 设两个正整数 m>n ，若 m-n=k ，则 m 与 n 的最大公约数和 n 与 k 的最大公约数相等 . 反复利用这个原理...
VIP
