基本情報技術者試験 基本情報技術者試験 平成29年度 春期 午前 午前 問6: 関数 f(x, y) が次のとおり定義されているとき，f(775, 527) の値は幾らか。ここで，x mod y は x を y で割った余りを返す。 f(x

問題本文

関数 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)

選択肢

• ア.0
• イ.31
• ウ.248
• エ.527

正解

イ. 31

解説

ユークリッド互除法。f(775,527) → f(527,248) → f(248,31) → f(31,0) → return 31。最大公約数 31。イが正解。