j.Co M
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、算法
Ｓ１ 输入，ｘ，ｙ
Ｓ２ ｍ＝ｍａｘ{ｘ，ｙ}
Ｓ３ ｎ＝ｍｉｎ{ｘ，ｙ}
Ｓ４ 若ｍ／ｎ＝[ｍ／ｎ]（[ｘ]表示ｘ的整数部分）
则输出ｎ，否则执行Ｓ５
Ｓ５ ｒ＝ｍ－[ｍ／ｎ]＊ｎ
Ｓ６ ｍ＝ｎ
Ｓ７ ｎ＝ｒ
Ｓ８ 执行Ｓ４
Ｓ９ 输出ｎ
上述算法的含义是 。
6、试写出一个算法，并画出流程图，使得能够输入n个正整数值，即可求出它们的最大公约数。
7、用当型和直到型语句，写出求两正整数的最大公约数的算法程序。
8、求两个整数ｘ（ｘ≥０）和ｙ（ｙ＞０）的整数商和余数（规定只能用加法和减法运算）。
9、试用更相减损术求80和36的最大公约数。
参考答案
1.A
2.C
3、更相减损之术 等值算法
4、运算次数
5、求ｘ，ｙ的最大公约数
6、略解：
Read n ,a
For i=2 to n
Read b
If aDo
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 ｍ，ｎ
（当型） ｒ＝ｍ／ｎ的余数
ＷＨＩＬＥ ｒ≠０
ｍ＝ｎ
ｎ＝ｒ
ｒ＝ｍ／ｎ的余数
ＷＥＮＤ
ＰＲＩＮＴ ｎ
ＥＮＤ
（直到型）
INPUT ｍ，ｎ
ＤＯ ｒ＝ｍ／ｎ的余数
ｍ＝ｎ
ｎ＝ｒ
ＬＯＯＰ ＵＮＴＩＬ ｒ＝０
ＰＲＩＮＴ ｍ
ＥＮＤ
8、
解：算法：
Ｓ１ 使ｑ＝０，ｒ＝２
Ｓ２ 当ｒ≥ｙ时，重复下面操作
Ｓ３ ｒ＝ｒ－ｙ
Ｓ４ ｑ＝ｑ＋１
Ｓ５ 输出ｘ
程序框图
INPUT ｑ＝０
ｒ＝ｘ
ｙ＝ｙ
ＤＯ ｒ＝ｒ－ｙ
ｑ＝ｑ＋１
ＬＯＯＰ ＵＮＴＩＬ ｒ≥ｙ
ＲＩＩＮＴ ｒ
ＥＮＤ
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。
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、算法
Ｓ１ 输入，ｘ，ｙ
Ｓ２ ｍ＝ｍａｘ{ｘ，ｙ}
Ｓ３ ｎ＝ｍｉｎ{ｘ，ｙ}
Ｓ４ 若ｍ／ｎ＝[ｍ／ｎ]（[ｘ]表示ｘ的整数部分）
则输出ｎ，否则执行Ｓ５
Ｓ５ ｒ＝ｍ－[ｍ／ｎ]＊ｎ
Ｓ６ ｍ＝ｎ
Ｓ７ ｎ＝ｒ
Ｓ８ 执行Ｓ４
Ｓ９ 输出ｎ
上述算法的含义是 。
6、试写出一个算法，并画出流程图，使得能够输入n个正整数值，即可求出它们的最大公约数。
7、用当型和直到型语句，写出求两正整数的最大公约数的算法程序。
8、求两个整数ｘ（ｘ≥０）和ｙ（ｙ＞０）的整数商和余数（规定只能用加法和减法运算）。
9、试用更相减损术求80和36的最大公约数。
参考答案
1.A
2.C
3、更相减损之术 等值算法
4、运算次数
5、求ｘ，ｙ的最大公约数
6、略解：
Read n ,a
For i=2 to n
Read b
If aDo
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 ｍ，ｎ
（当型） ｒ＝ｍ／ｎ的余数
ＷＨＩＬＥ ｒ≠０
ｍ＝ｎ
ｎ＝ｒ
ｒ＝ｍ／ｎ的余数
ＷＥＮＤ
ＰＲＩＮＴ ｎ
ＥＮＤ
（直到型）
INPUT ｍ，ｎ
ＤＯ ｒ＝ｍ／ｎ的余数
ｍ＝ｎ
ｎ＝ｒ
ＬＯＯＰ ＵＮＴＩＬ ｒ＝０
ＰＲＩＮＴ ｍ
ＥＮＤ
8、
解：算法：
Ｓ１ 使ｑ＝０，ｒ＝２
Ｓ２ 当ｒ≥ｙ时，重复下面操作
Ｓ３ ｒ＝ｒ－ｙ
Ｓ４ ｑ＝ｑ＋１
Ｓ５ 输出ｘ
程序框图
INPUT ｑ＝０
ｒ＝ｘ
ｙ＝ｙ
ＤＯ ｒ＝ｒ－ｙ
ｑ＝ｑ＋１
ＬＯＯＰ ＵＮＴＩＬ ｒ≥ｙ
ＲＩＩＮＴ ｒ
ＥＮＤ
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。
