平成29年度 春期 午前 問6
アルゴリズム
流れ図に関する問題
次の流れ図の処理で，終了時の x に格納されているものはどれか。ここで，与えられた a，b は正の整数であり，mod(x,y) は x を y で割った余りを返す。
流れ図
（ 開始 ）
↓
〔 x ← a 〕
〔 y ← b 〕
↓
┌── ループ1 ： y ＝ 0 ──┐ ← ループ端（上）。書かれているのは繰返しの終了条件
│ 〔 t ← mod(x, y) 〕 │
│ 〔 x ← y 〕 │
│ 〔 y ← t 〕 │
└── ループ1 ────────┘ ← ループ端（下）
↓
（ 終了 ）- アa と b の最小公倍数
- イa と b の最大公約数
- ウa と b の小さい方に最も近い素数
- エa を b で割った商
答えと解説を見る
✓ これが正解イa と b の最大公約数
解説
余りで置き換える手順なので最大公約数が残ります。
設問は、2 つの正の整数を受け取る流れ図を示し、終了時に x に残っているものを選ばせています。処理の中身は、x を y で割った余りを求め、y を x に、余りを y に入れ替えて繰り返すというものです。ループ端に書かれた条件は繰返しの終了条件なので、y が 0 になった時点で抜けます。小さい数を流すのが確実です。a が 24、b が 18 なら、余りは 6、次の周で 0 となり、終了時の x は 6 です。24 と 18 の両方を割り切れる最も大きな数が、まさに 6 です。7 と 5 のように共通の約数を持たない組でも、最後に x は 1 となって同じ読みが成り立ちます。割った余りは、もとの数から相手の倍数を引いたものなので、両者に共通する約数は入れ替えても変わらず、残った x がその値になります。
ほかの選択肢はなぜ違うのか
- アa と b の最小公倍数：24 と 18 で流すと 72 になるはずですが、手順が返すのは 6 です。どちらの倍数にもなる最も小さい数を求める計算は、この図のどこにも現れません。
- ウa と b の小さい方に最も近い素数：24 と 18 の組では 17 や 19 が該当しますが、手順の結果は 6 です。割り切れるかどうかを一つずつ試す処理も、素数かどうかを判定する処理も図にありません。
- エa を b で割った商：商を求めるなら 24 を 18 で割った 1 が残るはずですが、変数に入れているのは商ではなく余りです。取り出している値そのものが違います。
出典：平成29年度 春期 応用情報技術者試験 午前 問6
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）