アルゴリズム (全80問中15問目)
No.15
次の流れ図は，2数 A，B の最大公約数を求めるユークリッドの互除法を，引き算の繰返しによって計算するものである。Aが876，Bが204のとき，何回の比較で処理は終了するか。
出典：平成31年春期 問7
- 4
- 9
- 10
- 11
- [出題歴]
- 基本情報技術者 H15秋期 問15
- 基本情報技術者 H20春期 問15
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
エ
解説
問題文の流れ図を比較回数に注目しながらトレース(追跡)していくと、次のようになります。
- (開始時にL←876，S←204で初期化)
876＞204 … L←876－204＝672 - 672＞204 … L←672－204＝468
- 468＞204 … L←468－204＝264
- 264＞204 … L←264－204＝60
- 60＜204 … S←204－60＝144
- 60＜144 … S←144－60＝84
- 60＜84 … S←84－60＝24
- 60＞24 … L←60－24＝36
- 36＞24 … L←36－24＝12
- 12＜24 … S←24－12＝12
- 12＝12 … A，B，Lの出力