整数x，y（x＞y≧0）に対して，次のように定義された関数F(x,y)がある。F(231,15)の値は幾らか。ここで，x mod yはxをyで割った余りである。 F(x,y) = x （y=0のとき）、F(y, x mod y) （y＞0のとき）

選択肢

• ア2
• イ3
• ウ5
• エ7

正解と解説

正解：イ 3

この再帰関数はユークリッドの互除法そのもので、最終的に最大公約数を返す。実際に追うと231を15で割った余りは6、次に15を6で割った余りは3、次に6を3で割った余りは0となり、第2引数が0になった時点の第1引数3が値となる。231＝3×7×11、15＝3×5なので最大公約数3と一致する。

選択肢ごとの解説

• ア231も15も偶数ではなく、2は公約数になり得ない。
• イ互除法の計算結果であり、231と15の最大公約数と一致する。これが正解。
• ウ15は5で割り切れるが231は割り切れないため、5は公約数ではない。
• エ231は7で割り切れるが15は割り切れないため、7は公約数ではない。

同じ分野の他の問題

• 次のプログラム中の a と b に入れる正しい答えの組合せを、解答群の中から選べ。ここで、配列の要素番号は1から始まる。…2026年度 公開問題 科目B 問5
• 次のプログラム中の に入れる正しい答えを、解答群の中から選べ。ここで、配列の要素番号は1から始まる。 関数func1に与…2026年度 公開問題 科目B 問3
• 次のプログラム中の に入れる正しい答えを、解答群の中から選べ。 関数complementは、引数として渡された8ビット型…2026年度 公開問題 科目B 問2
• 次のプログラム中の に入れる正しい答えを、解答群の中から選べ。ここで、配列の要素番号は1から始まる。 次のプログラムは、…2026年度 公開問題 科目B 問1
• 次のプログラム中の に入れる正しい答えを、解答群の中から選べ。 関数changeは、10より大きい整数を引数nで受け取り…2025年度 公開問題 科目B 問2