サンプル問題 科目B 問4
問題
次のプログラム中の [a] ～ [c] に入れる正しい答えの組合せを，解答群の中から選べ。
関数 gcd は，引数で与えられた二つの正の整数 num1 と num2 の最大公約数を，次の (1) ～ (3) の性質を利用して求める。
(1) num1 と num2 が等しいとき，num1 と num2 の最大公約数は num1 である。
(2) num1 が num2 より大きいとき，num1 と num2 の最大公約数は，(num1 － num2) と num2 の最大公約数と等しい。
(3) num2 が num1 より大きいとき，num1 と num2 の最大公約数は，(num2 － num1) と num1 の最大公約数と等しい。
出典：基本情報技術者試験 サンプル問題
解いてみる
(1)から(3)の性質を見ると、停止条件は(1)なので、この条件を満たすまで(2)か(3)の処理を繰り返すのだと思いました。[a]について考えると、それに当てはまるのは、ウかエです。
次に[b]は、その次の行でx - yを計算しているので、xの方が大きいことが分かり、答えはエです。
[c]は[a]が決まれば自動的に決まります。
この問題の何が難しいのか
このように、この問題はごく簡単に解くことができるのですが、なぜ解答群にアやイがあるのか考えてみました。
(1)から(3)の性質をよく見ると、繰り返して実行する、という表現はありません。さりげなく再帰的に定義しています。
ということは、この再帰的な定義を繰り返しで実現する、ということに気づくかどうかがポイントのように思いました。確かに、これに気づかないと、アやイを選んでしまうかも知れません。
これは、プログラム作成の経験が少ない人には難しいかも知れませんね。そういう場合にどうするかですが、このブログで何度も出てきたように、CPUの代わりになって具体的に試してみます。
実際に試してみる
解答群アから順に、それを選んで実行してみるとどうなるか、具体例で考えます。
解答群アを選択、gcd(6, 3)の場合
解答群アを選んだとして、gcd(6, 3)を実行してみます。赤文字は値が変わったところです。
#3がifになっているので、その後は1回しか実行しません。
#4はx < yの条件を選んだので、この場合のxとyの値では当てはまらず、elseに進みます。
#6では、小さい方から大きい方を引く y-x を計算して、結果は-3になります。何かが変と気づくところです。
#7で6を返します。これは、最大公約数を計算した結果が6ということを意味しますが、3になるのが正しいので、この答えは間違っています。
このように、解答群アは間違いです。
解答群イを選択の場合
では次に、解答群イを選んだ場合を同様に考えます。
gcd(6, 3)を計算
先ほどと同じgcd(6, 3)の計算をしてみます。
今度は#4で正しく判断できています。その結果#5で正しく計算できます。
すると#6で3を返すことになり、最大公約数3を正しく計算できました。
では、もう一つの例を考えます。今度は、gcd(6, 2)を計算します。
gcd(6, 2)を計算
6と2の最大公約数は2です。しかし、#6では4を返していて、間違っています。
したがって、解答群イは間違いです。
このように具体例を考えると、gcd(6, 3)のように、たまたまうまくいく場合があるので一例だけで決めるのは要注意です。
解答群ウを選択の場合
[a]を繰り返しにする必要があることに気づけた人は[b]を間違わない気がしますが、念のために解答群ウを選んでみます。
今度は#3が繰り返しになっています。
#6や#10でyの値を計算していますが、このようにどんどん小さくなり、xの値から離れていきます。すると、#3の条件を満たし続けるので、#3の繰り返しが無限ループになります。
このように、解答群ウは明らかに間違いです。
解答群エを選択の場合
最後に、解答群エを試します。
このように正しく2を返しています。
もう一例、今度は#4の条件が成立せず、elseの方に進む例です。
#5でelse側に進んでも正しく計算できています。
実際の試験でこのように問題を解くのは時間的に難しいかもしれませんが、ふだんから練習しておくと良いと思います。
