平成24年度春期 情報処理安全確保支援士 午前Ⅰ 問3

午前I 問03：最大公約数は“余りでバトン渡し”して探そう

最大公約数は、`gcd(a、b)=gcd(b、a mod b)` の形で、割った余りを次の相手に渡していくよ。余りが 0 になったとき、そのときの割る数が最大公約数だよ。

この問題で問われていること

1回割って終わりではなく、余りが 0 になるまで同じ手順をくり返せるかがポイントだよ。数字のバトンリレーを追いかけるつもりで、順番に計算していこう。

Euclid’s Algorithm

Euclid’s algorithm computes the greatest common divisor by repeatedly replacing the larger value with the remainder

gcd(a、b)=gcd(b、a mod b)

確認ポイント

• 引き算だけの方法ではありません。
• 余りが 0 になるまで続ける。
• 互除法の手順を押さえる。

正解

ウ

出典

問題文と解答は IPA 公開の過去問題冊子・解答例を基にしています。

選択肢ア

2回では足りないよ。gcd(135,35)から始めて、まだ余りが0にならないので次へ次へと呼び出しが続くんだ。たとえるなら、窓口で1回聞いただけでは解決せず、別の窓口に何回か回される感じだね。実際は4回呼ばれるので、2は不正解だよ。

選択肢イ

3回では最後の確認を数え忘れているよ。gcd(30,5)で終わりではなく、30を5で割った余りが0なので gcd(5,0) も呼び出されるんだ。最後に『もう余りはないね』と確認する窓口まで行く感じだよ。だから3は不正解だよ。

選択肢ウ（正解）

4回が正解だよ。135÷35の余りは30、35÷30の余りは5、30÷5の余りは0なので、呼び出しは gcd(135,35)、gcd(35,30)、gcd(30,5)、gcd(5,0) の4つになるんだ。荷物を次の担当へ渡していって、余り0というゴールに着くまでを全部数えるイメージだよ。

選択肢エ

5回は数えすぎだよ。呼び出しは gcd(135,35) → gcd(35,30) → gcd(30,5) → gcd(5,0) までで、gcd(5,0)になった時点で終了するんだ。最後に答えを返すだけで、新しい窓口にはもう行かないイメージだよ。だから5は不正解だよ。