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。
本文來自：逍遙右腦記憶 /gaoer/56791.html
相關閱讀：函數的和差積商的導數學案練習題
橢圓定義在解題中的應用
合情推理
基本算法語句
基本計數原理