令和8年度 公開問題 科目B 問3
次のプログラム中の[ ]に入れる正しい答えを,解答群の中から選べ。ここで,配列の要素番号は 1 から始まる。
関数 func1 に与える引数と,関数 func2 に与える引数とが同じとき,二つの関数は同じ値を返す。プログラムでは,配列の領域外を参照してはならないものとする。
○整数型: func1(整数型: n)
if (nが2以下)
return 1
endif
return 2 × func1(n - 2) + func1(n - 1)
○整数型: func2(整数型: n)
整数型の配列: data ← {1, 1, 1}
整数型: i
/* nが3より小さいときは繰返し処理を実行しない */
for (iを3からnまで1ずつ増やす)
data[1] ← data[2]
data[2] ← data[3]
data[3] ← [ a ]
endfor
return data[3]
| a | |
|---|---|
| ア | 2 × data[1] + data[2] |
| イ | 2 × data[2] + data[1] |
| ウ | 2 × data[i - 1] + data[i - 2] |
| エ | 2 × data[i - 2] + data[i - 1] |
| オ | data[3] + 2 × data[1] + data[2] |
| カ | data[3] + 2 × data[2] + data[1] |
| キ | data[3] + 2 × data[i - 1] + data[i - 2] |
| ク | data[3] + 2 × data[i - 2] + data[i - 1] |
出典:令和8年度 基本情報技術者試験 科目B 公開問題 問3
正解と解説を見る
正解:ア
ポイント:再帰を繰返しに直すときは、「直前の値たち」を変数に持ち、ずらしながら次の値を作る。
func1 は、n が 2 以下なら 1、それ以外は f(n)=2×f(n-2)+f(n-1) という漸化式です。func2 は、同じ値を配列 data の3つの要素を使って繰返しで求めます。
ループの1回目(i=3)の前は data={1, 1, 1} です。ループの中では、まず data[1] ← data[2]、data[2] ← data[3] と一つずつ前へずらします。ずらした後は、data[1] が f(i-2)、data[2] が f(i-1) を表します。新しい f(i) は 2×f(i-2)+f(i-1) なので、data[3] ← 2 × data[1] + data[2](ア)です。
確かめ:i=3 で 2×1+1=3、i=4 で data={1, 3, ?} → 2×1+3=5、i=5 で {3, 5, ?} → 2×3+5=11。func1 も f(3)=3、f(4)=5、f(5)=11 で一致します。
イ:2×data[2]+data[1] は係数が逆で、f(4)=2×3+1=7 になってしまいます。
ウ・エ:data は要素数3なので、i が大きくなると data[i-1] などが範囲外になります。
オ〜ク:data[3] をさらに足すと、f(i-1) を二重に数えてしまいます。
解説と下の表はこのサイトが作成したものです(表は、正解の選択肢を入れたプログラムを実際に実行した結果です)。
正解のプログラムを動かしてみる
func2(11) を呼び出したときに、1行ずつ何が起きるかの表です(全部で 41 手)。「真・偽」は、その行の条件の判定です。
| 手 | 実行した行 | 変わった値 |
|---|---|---|
| 1 | 7行目○整数型: func2(整数型: n) | n = 11 |
| 2 | 8行目整数型の配列: data ← {1, 1, 1} | data = {1, 1, 1} |
| 3 | 9行目整数型: i | |
| 4 | 12行目for (iを3からnまで1ずつ増やす) | 真 i = 3 |
| 5 | 13行目data[1] ← data[2] | |
| 6 | 14行目data[2] ← data[3] | |
| 7 | 15行目data[3] ← 2 × data[1] + data[2] | data = {1, 1, 3} |
| 8 | 12行目for (iを3からnまで1ずつ増やす) | 真 i = 4 |
| 9 | 13行目data[1] ← data[2] | |
| 10 | 14行目data[2] ← data[3] | data = {1, 3, 3} |
| 11 | 15行目data[3] ← 2 × data[1] + data[2] | data = {1, 3, 5} |
| 12 | 12行目for (iを3からnまで1ずつ増やす) | 真 i = 5 |
| 13 | 13行目data[1] ← data[2] | data = {3, 3, 5} |
| 14 | 14行目data[2] ← data[3] | data = {3, 5, 5} |
| 15 | 15行目data[3] ← 2 × data[1] + data[2] | data = {3, 5, 11} |
| 16 | 12行目for (iを3からnまで1ずつ増やす) | 真 i = 6 |
| 17 | 13行目data[1] ← data[2] | data = {5, 5, 11} |
| 18 | 14行目data[2] ← data[3] | data = {5, 11, 11} |
| 19 | 15行目data[3] ← 2 × data[1] + data[2] | data = {5, 11, 21} |
| 20 | 12行目for (iを3からnまで1ずつ増やす) | 真 i = 7 |
| 21 | 13行目data[1] ← data[2] | data = {11, 11, 21} |
| 22 | 14行目data[2] ← data[3] | data = {11, 21, 21} |
| 23 | 15行目data[3] ← 2 × data[1] + data[2] | data = {11, 21, 43} |
| 24 | 12行目for (iを3からnまで1ずつ増やす) | 真 i = 8 |
| 25 | 13行目data[1] ← data[2] | data = {21, 21, 43} |
| 26 | 14行目data[2] ← data[3] | data = {21, 43, 43} |
| 27 | 15行目data[3] ← 2 × data[1] + data[2] | data = {21, 43, 85} |
| 28 | 12行目for (iを3からnまで1ずつ増やす) | 真 i = 9 |
| 29 | 13行目data[1] ← data[2] | data = {43, 43, 85} |
| 30 | 14行目data[2] ← data[3] | data = {43, 85, 85} |
| 31 | 15行目data[3] ← 2 × data[1] + data[2] | data = {43, 85, 171} |
| 32 | 12行目for (iを3からnまで1ずつ増やす) | 真 i = 10 |
| 33 | 13行目data[1] ← data[2] | data = {85, 85, 171} |
| 34 | 14行目data[2] ← data[3] | data = {85, 171, 171} |
| 35 | 15行目data[3] ← 2 × data[1] + data[2] | data = {85, 171, 341} |
| 36 | 12行目for (iを3からnまで1ずつ増やす) | 真 i = 11 |
| 37 | 13行目data[1] ← data[2] | data = {171, 171, 341} |
| 38 | 14行目data[2] ← data[3] | data = {171, 341, 341} |
| 39 | 15行目data[3] ← 2 × data[1] + data[2] | data = {171, 341, 683} |
| 40 | 12行目for (iを3からnまで1ずつ増やす) | 偽 i = 12 |
| 41 | 17行目return data[3] |
戻り値:683