1.3.1 辗转相除法与相减损术
1、在对16和12求最大公约数时,整个操作如下:(16,12)(4,12)(4,8)(4,4),由此可以看出12和16的最大公约数是( )
A、 4 B、 12 C、 16 D、 8
2、下列各组关于最大公约数的说法中不正确的是( )
A、16和12的最大公约数是4 B、78和36的最大公约数是6
C、85和357的最大公约数是34 D、105和315的最大公约数是105
3、我国古代数学家求两个正整数最大公约数的算法,被称为 ,又称为
4、运算速度快是计算机一个很重要的特点,而算法好坏的一个重要标志是
5、算法
S1输入,x,y
S2m=max{x,y}
S3n=min{x,y}
S4若m/n=[m/n]([x]表示x的整数部分)
则输出n,否则执行S5
S5r=m-[m/n]*n
S6m=n
S7n=r
S8执行S4
S9输出n
上述算法的含义是 。
6、试写出一个算法,并画出流程图,使得能够输入n个正整数值,即可求出它们的最大公约数。
7、用当型和直到型语句,写出求两正整数的最大公约数的算法程序。
8、求两个整数x(x0)和y(y>0)的整数商和余数(规定只能用加法和减法运算)。
9、试用更相减损术求80和36的最大公约数。
参考答案
1.A
2.C
3、更相减损之术 等值算法
4、运算次数
5、求x,y的最大公约数
6、略解:
Read n ,a
For i=2 to n
Read b
If ab then m=a:a=b:b=m
Do
r=mod(a,b)
a=b:b=r
Loop Until r=0
If a=1 then prind a
Goto End
Next i
Print a
End
7、
INPUT m,n
(当型)r=m/n的余数
WHILE r0
m=n
n=r
r=m/n的余数
WEND
PRINT n
END
(直到型)
INPUT m,n
DO r=m/n的余数
m=n
n=r
LOOPUNTIL r=0
PRINT m
END
8、
解:算法:
S1使q=0,r=2
S2当ry时,重复下面操作
S3r=r-y
S4q=q+1
S5输出x
程序框图
INPUT q=0
r=x
y=y
DOr=r-y
q=q+1
LOOP UNTILry
RIINT r
END
9、
解:80-36=44,
44-36=8,
36-8=28,
28-8=20,
20-8=12,
12-8=4,
8-4=4。
因此80和36的最大公约数是4。