1．
求最大公约数
(1)辗转相除法
程序框图与程序语句
程序：
INPUT “m，n=”;m,n
DO
r=m MOD n
m=n
n=r
LOOP UNTIL r=0
END
(2)更相减损术
更相减损术程序：
INPUT “请输入两个不相等的正整数”；a，b
i=0
WHILE a MOD 2=0 AND b MOD 2=0
a=a/2
b=b/2
i=i+1
WEND
DO
IF b<a THEN
t=a
a=b
b=t
END IF
c=a－b
a=b
b=c
LOOP UNTIL a=b
PRINT a^i
END
对于两个正整数如何选择合适的方法求他们的最大公约数
|
方法 |
适用范围及特点 |
|
短除法 |
适合两个较小的正整数或两个质因数较少的正整数，简便易操作。 |
|
穷举法 |
适合计算机操作，但一一验证过于繁琐。 |
|
辗转相除法 |
适用于两个较大的正整数，以除法为主，辗转相除法计算次数相对较少，特别当两个数字大小差别较大时计算次数较明显。 |
|
更相减损术 |
适用于两个较大的正整数，更相减损术以减法为主，计算次数上相对于辗转相处法较多。 |
6] －3 0 15
[－3 6] 0 15
[－3 0 6] 15
[－3 0 6 15]
用冒泡排序法排序：
|
6 |
|
6 |
|
6 |
|
6 |
|
6 |
|
6 |
|
6 |
|
15 |
|
15 |
|
15 |
|
－3 |
|
－3 |
|
0 |
|
0 |
|
0 |
|
15 |
|
15 |
|
6 |
|
6 |
|
6 |
|
0 |
|
0 |
|
－3 |
|
15 |
|
15 |
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
|
15 |
|
15 |
|
15 |
|
－3 |
|
－3 |
|
－3 |
|
－3 |
|
－3 |
|
－3 |
|
－3 |
题型4：进位值
例7．把十进制数89化为三进制数，并写出程序语句.
解析：具体的计算方法如下：
89=3×29+2
29=3×9+2
9=3×3+0
3=3×1+0
1=3×0+1
所以:89(10)=1011001(3)。
点评：根据三进制数满三进一的原则，可以用3连续去除89及其所的得的商，然后按倒序的先后顺序取出余数组成数据即可。
例8．将8进制数314706(8)化为十进制数，并编写出一个实现算法的程序。
解析：314706(8)=3×85+1×84+4×83+7×82+0×81+6×80=104902。
所以，化为十进制数是104902。
点评：利用把k进制数转化为十进制数的一般方法就可以把8进制数314706(8)化为十进制数，然后根据该算法，利用GET函数，应用循环结构可以设计程序。