アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20121216 実施分 問6
次の流れ図は，2数A，Bの最大公約数を求めるユークリッドの互除法を，引き算の繰返しによって計算するものである。Aが876，Bが204のとき，何回の比較で処理は終了するか。
流れ図: 開始 → [A→L, B→S] → 判断(L:S)。L>S のとき [L−S→L] を実行して判断へ戻る。L<S のとき [S−L→S] を実行して判断へ戻る。L=S のとき [A,B,L の出力] → 終了。
- ア 4
- イ 9
- ウ 10
- エ 11
出典：基本情報技術者試験 科目A免除 修了試験 20121216 実施分 問6
答えと解説を見る
正解：エ
覚える知識
ユークリッドの互除法のトレースと初期値関係
ユークリッドの互除法は、2数の差(または剰余)を繰り返し、等しくなった値を最大公約数とする。
この問題で必要なこと
A=876,B=204で大きい方から小さい方を引く操作を繰り返し、比較が11回目でL=S=12となり終了する。
ひっかけ
引き算回数と比較回数を混同させる。
この知識の出題：本試験系 6 回・免除試験 19 回（公開問題での観測値）