平成29年度 春期 基本情報技術者試験 午前 問6
テクノロジ／アルゴリズム関数 f(x, y) が次のとおり定義されているとき，f(775, 527) の値は幾らか。ここで，x mod y は x を y で割った余りを返す。 f(x, y)： if y ＝ 0 then return x else return f(y, x mod y)
出典：平成29年度 春期 基本情報技術者試験 午前 問6
- ア0
- イ31
- ウ248
- エ527
正解：イ
解説
この関数はユークリッドの互除法そのものです。f(775,527) を計算すると，775 mod 527＝248 なので f(527,248)，527 mod 248＝31 なので f(248,31)，248 mod 31＝0 なので f(31,0) を呼び出し，y＝0 の条件が成立してxの値である31を返します。
選択肢ごとの解説
- ア誤り。0になるのは775と527の最大公約数が1のときに近い誤解ですが，実際の計算結果は0ではありません。
- イ正しい。ユークリッドの互除法により，775 mod 527＝248，527 mod 248＝31，248 mod 31＝0 となり，最終的に31が返されます。
- ウ誤り。248は計算過程で一時的に現れる余りの値であり，最終的な戻り値ではありません。
- エ誤り。527は最初の引数yの値であり，再帰呼出しが進んだ最終結果ではありません。