j.Co M
1.3 案例算法
案例1 輾轉(zhuǎn)相除法與更相減損術(shù)
1、在對16和12求最大公約數(shù)時，整個操作如下：（16，12）→（4，12）→（4，8）→（4，4），由此可以看出12和16的最大公約數(shù)是（ ）
A、 4 B、 12 C、 16 D、 8
2、下列各組關(guān)于最大公約數(shù)的說法中不正確的是（ ）
A、16和12的最大公約數(shù)是4 B、78和36的最大公約數(shù)是6
C、85和357的最大公約數(shù)是34 D、105和315的最大公約數(shù)是105
3、我國古代數(shù)學(xué)家求兩個正整數(shù)最大公約數(shù)的算法，被稱為 ，又稱為
4、運算速度快是計算機(jī)一個很重要的特點，而算法好壞的一個重要標(biāo)志是
5、算法
Ｓ１　　輸入，ｘ，ｙ
Ｓ２　�。恚剑恚幔鴞ｘ，ｙ}
Ｓ３　　ｎ＝ｍｉｎ{ｘ，ｙ}
Ｓ４　　若ｍ／ｎ＝[ｍ／ｎ]（[ｘ]表示ｘ的整數(shù)部分）
則輸出ｎ，否則執(zhí)行Ｓ５
Ｓ５　�。颍剑恚璠ｍ／ｎ]＊ｎ
Ｓ６　�。恚剑�
Ｓ７　　ｎ＝ｒ
Ｓ８　　執(zhí)行Ｓ４
Ｓ９　　輸出ｎ
上述算法的含義是　　　　　　　　　。
6、試寫出一個算法，并畫出流程圖，使得能夠輸入n個正整數(shù)值，即可求出它們的最大公約數(shù)。


7、用當(dāng)型和直到型語句，寫出求兩正整數(shù)的最大公約數(shù)的算法程序。



8、求兩個整數(shù)ｘ（ｘ≥０）和ｙ（ｙ＞０）的整數(shù)商和余數(shù)（規(guī)定只能用加法和減法運算）。

9、試用更相減損術(shù)求80和36的最大公約數(shù)。


參考答案

1.A
2.C
3、更相減損之術(shù) 等值算法
4、運算次數(shù)
5、求ｘ，ｙ的最大公約數(shù)
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　　�。恚�ｎ
（當(dāng)型）　�。颍剑恚�ｎ的余數(shù)
ＷＨＩＬＥ�。颉伲�
ｍ＝ｎ
ｎ＝ｒ
ｒ＝ｍ／ｎ的余數(shù)
ＷＥＮＤ
ＰＲＩＮＴ　　�。�
ＥＮＤ
（直到型）
INPUT　　�。�，ｎ
ＤＯ　　�。颍剑恚�ｎ的余數(shù)
ｍ＝ｎ
ｎ＝ｒ
ＬＯＯＰ　�。眨危裕桑獭　　。颍剑�
ＰＲＩＮＴ　　　　　ｍ
ＥＮＤ
8、
解：算法：
Ｓ１　　使ｑ＝０，ｒ＝２
Ｓ２　　當(dāng)ｒ≥ｙ時，重復(fù)下面操作
Ｓ３　　ｒ＝ｒ－ｙ
Ｓ４　�。瘢剑瘢�１
Ｓ５　　輸出ｘ
程序框圖
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的最大公約數(shù)是4。


本文來自：逍遙右腦記憶 http://www.portlandfoamroofing.com/gaoer/56791.html

相關(guān)閱讀：算法的三種基本邏輯結(jié)構(gòu)和框圖表示