応用情報技術者 2015年 秋期 午前2 問06
問題文
次に示すユークリッドの互除法(方法 1, 方法 2)で、正の整数、の最大公約数は、それぞれとのどちらの変数に求まるか。ここで、は、で割った余りを表す。
選択肢
ア：
イ：
ウ：（正解）
エ：
ユークリッドの互除法における最大公約数の求め方【午前2 解説】
要点まとめ
- 結論：方法1では最大公約数は変数「n」に、方法2では変数「m」に求まる。
- 根拠：方法1はループ終了時に「r=0」となり、その時の「n」が最大公約数である。方法2はループ条件が「r=0」になるまで続き、終了時の「m」が最大公約数となる。
- 差がつくポイント：ループの終了条件と変数の更新順序を正確に理解し、どの変数に最大公約数が格納されるかを見極めることが重要。
正解の理由
方法1はループの判定が「r=0」であり、終了時の「n」が最大公約数です。これは「r」が余りであり、余りが0になる直前の「n」が最大公約数だからです。一方、方法2はループが「r=0」になるまで続き、終了時の「m」が最大公約数となります。変数の入れ替え順序が異なるため、最大公約数が格納される変数も異なります。したがって、方法1は「n」、方法2は「m」に最大公約数が求まるため、選択肢はウが正解です。
よくある誤解
ユークリッドの互除法は単純に余りが0になった時の変数を答えればよいと誤解しがちですが、変数の更新順序により最大公約数が格納される変数は異なります。
解法ステップ
- 方法1のフローを確認し、ループ終了条件と変数の更新順序を把握する。
- 方法1の終了時に「r=0」となり、その時の「n」が最大公約数であることを理解する。
- 方法2のフローを確認し、ループ条件と変数の更新順序を把握する。
- 方法2の終了時に「r=0」となり、その時の「m」が最大公約数であることを理解する。
- 以上の理解から、方法1は「n」、方法2は「m」に最大公約数が求まると判断する。
選択肢別の誤答解説
- ア（方法1=m、方法2=m）：方法1の終了時の最大公約数は「n」であり、「m」ではないため誤り。
- イ（方法1=m、方法2=n）：両方とも逆になっているため誤り。
- ウ（方法1=n、方法2=m）：正解。方法1は「n」、方法2は「m」に最大公約数が格納される。
- エ（方法1=n、方法2=n）：方法2は「m」に最大公約数があるため誤り。
補足コラム
ユークリッドの互除法は最大公約数を効率的に求めるアルゴリズムで、変数の入れ替えと余りの計算を繰り返します。プログラム実装時は変数の更新順序に注意し、終了時にどの変数が最大公約数を保持しているかを正確に把握することが重要です。
FAQ
Q: なぜ最大公約数は余りが0になった時の変数に格納されるのですか？
A: 余りが0になる直前の除数が最大公約数であり、互除法はこの性質を利用しているためです。
A: 余りが0になる直前の除数が最大公約数であり、互除法はこの性質を利用しているためです。
Q: 方法1と方法2で変数の更新順序が違う理由は？
A: アルゴリズムの設計による違いで、どちらも正しく最大公約数を求められますが、変数の役割が異なるためです。
A: アルゴリズムの設計による違いで、どちらも正しく最大公約数を求められますが、変数の役割が異なるためです。
関連キーワード: ユークリッドの互除法、最大公約数、アルゴリズム、変数更新、余り計算
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！