平成24年度 秋期 午前 問2
アルゴリズム
最大公約数に関する問題
与えられた正の整数 x₀，x₁（x₀＞x₁）の最大公約数を，次の手順で求める。x₀＝175，x₁＝77 の場合，手順(2)は何回実行するか。ここで，"A→B"は，A を B に代入することを表す。
〔手順〕 (1) 2 → i (2) x(i−2) を x(i−1) で割った剰余 → x(i) (3) x(i)＝0 ならば x(i−1) を最大公約数として終了する。 (4) i＋1 → i として (2) に戻る。
- ア3
- イ4
- ウ6
- エ7
答えと解説を見る
✓ これが正解イ4
解説
剰余は21、14、7、0と続き、割り算は4回行います。
この手順は、大きいほうを小さいほうで割った剰余を次の割る数に送り、剰余が0になったときの割る数を最大公約数とする求め方です。数えるときの軸は一つで、どこまでを1回と数えるかを設問の指示どおりに読み取ることです。数える対象は割り算そのものを行う手順であり、終わりを判断するのはその割り算を済ませた後ですから、剰余が0になった最後の割り算も回数に入ります。実際に追うと、175を77で割った剰余は21、77を21で割ると14、21を14で割ると7、14を7で割ると0です。0が出たところで終わるので、割り算を行ったのは4回で、そのときの割る数である7が最大公約数になります。
ほかの選択肢はなぜ違うのか
- ア3：剰余が0になった最後の一手を数え落とすとこの数になります。0という値も割り算を実際に行って初めて得られるものなので、その回も数に含めます。
- ウ6：この条件からこの数は導けません。得られる剰余は21、14、7、0の四つだけで、割る数は毎回小さくなっていくため、五手以上続く余地がありません。
- エ7：これは求まった最大公約数そのものの値です。問われているのは手順を実行した回数なので、計算の結果として出た数をそのまま答えにはできません。
出典：平成24年度 秋期 基本情報技術者試験 午前 問2（改変：原典の図表をテキストに書き起こした）
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）