辗转相除法的算法步骤是,对于给定的两个正整数m、n(m>n),用m除以n得到余数r,若余数r不为0,就将n和r构成新的一对数(m=n,n=r),继续上面的除法,直到余数为0,这时m就是原来两个数的最大公约数。因为这个算法需要反复进行除法运算,故被形象地命名为“辗转相除法”。小曲设计了辗转相除法的算法,请根据下面算法回答问题。
描述一 | 描述二 | 描述三 |
①输入两个正整数m,n(m>n); ②计算m除以n所得的余数r; ③m=n, n=r; ④若r=0,则m,n的最大公约数等于m;否则转到步骤②; ⑤输出最大公约数m; ⑥结束。 |
|
|