アルゴリズムとプログラミング

基本情報技術者試験｜次の擬似言語は最大公約数を求める再帰手続である。gcd(252, 198)…

アルゴリズムとプログラミングアルゴリズムとプログラミング計算問題難易度：hard

次の擬似言語は最大公約数を求める再帰手続である。gcd(252, 198) を呼び出したとき、戻り値はどれか。mod は剰余を表す。

○整数型: gcd(整数型: a, 整数型: b)
  if (b が 0 と等しい)
    return a
  endif
  return gcd(b, a mod b)

ア18

イ54

ウ252

エ198

正解

ア．18

再帰版互除法は b=0 になるまで gcd(b, a mod b) を繰り返す。(252,198)→(198,54)→(54,36)→(36,18)→(18,0) と進み、最後に a=18 を返すためアが正しい。

?選択肢ごとの解説

ア ○再帰版互除法は b=0 になるまで gcd(b, a mod b) を繰り返す。(252,198)→(198,54)→(54,36)→(36,18)→(18,0) と進み、最後に a=18 を返すためアが正しい。

イ ×1 段目の余り 252 mod 198=54 を最終結果と取り違えた、再帰を最後までたどらなかった誤りである。

ウ ×最初の引数 a=252 をそのまま返した、基底条件に到達する前で打ち切った誤りである。

エ ×2 番目の引数 b=198 を答えた、再帰の引数交換を追えていない誤りである。

この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。

基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。

登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。

作成・校閲：ukamiru編集部 · 基本情報技術者試験過去問 · fe-b-algo-0073