HOME»基本情報技術者平成20年春期»午前問15
基本情報技術者平成20年春期 午前問15
問15
次の流れ図は，2数 A，Bの最大公約数を求めるユークリッドの互除法を，引き算の繰返しによって計算するものである。 Aが876，Bが204のとき，何回の比較で処理は終了するか。
- 4
- 9
- 10
- 11
- [出題歴]
- 基本情報技術者 H15秋期 問15
- 基本情報技術者 H31春期 問7
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
エ
解説
問題文の流れ図を比較回数に注目しながらトレース(追跡)していくと次のようになります。
- (開始時に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の出力