うごく基本情報

令和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 手)。「真・偽」は、その行の条件の判定です。

手実行した行変わった値
17行目○整数型: func2(整数型: n)n = 11
28行目整数型の配列: data ← {1, 1, 1}data = {1, 1, 1}
39行目整数型: i
412行目for (iを3からnまで1ずつ増やす)真
i = 3
513行目data[1] ← data[2]
614行目data[2] ← data[3]
715行目data[3] ← 2 × data[1] + data[2]data = {1, 1, 3}
812行目for (iを3からnまで1ずつ増やす)真
i = 4
913行目data[1] ← data[2]
1014行目data[2] ← data[3]data = {1, 3, 3}
1115行目data[3] ← 2 × data[1] + data[2]data = {1, 3, 5}
1212行目for (iを3からnまで1ずつ増やす)真
i = 5
1313行目data[1] ← data[2]data = {3, 3, 5}
1414行目data[2] ← data[3]data = {3, 5, 5}
1515行目data[3] ← 2 × data[1] + data[2]data = {3, 5, 11}
1612行目for (iを3からnまで1ずつ増やす)真
i = 6
1713行目data[1] ← data[2]data = {5, 5, 11}
1814行目data[2] ← data[3]data = {5, 11, 11}
1915行目data[3] ← 2 × data[1] + data[2]data = {5, 11, 21}
2012行目for (iを3からnまで1ずつ増やす)真
i = 7
2113行目data[1] ← data[2]data = {11, 11, 21}
2214行目data[2] ← data[3]data = {11, 21, 21}
2315行目data[3] ← 2 × data[1] + data[2]data = {11, 21, 43}
2412行目for (iを3からnまで1ずつ増やす)真
i = 8
2513行目data[1] ← data[2]data = {21, 21, 43}
2614行目data[2] ← data[3]data = {21, 43, 43}
2715行目data[3] ← 2 × data[1] + data[2]data = {21, 43, 85}
2812行目for (iを3からnまで1ずつ増やす)真
i = 9
2913行目data[1] ← data[2]data = {43, 43, 85}
3014行目data[2] ← data[3]data = {43, 85, 85}
3115行目data[3] ← 2 × data[1] + data[2]data = {43, 85, 171}
3212行目for (iを3からnまで1ずつ増やす)真
i = 10
3313行目data[1] ← data[2]data = {85, 85, 171}
3414行目data[2] ← data[3]data = {85, 171, 171}
3515行目data[3] ← 2 × data[1] + data[2]data = {85, 171, 341}
3612行目for (iを3からnまで1ずつ増やす)真
i = 11
3713行目data[1] ← data[2]data = {171, 171, 341}
3814行目data[2] ← data[3]data = {171, 341, 341}
3915行目data[3] ← 2 × data[1] + data[2]data = {171, 341, 683}
4012行目for (iを3からnまで1ずつ増やす)偽
i = 12
4117行目return data[3]

戻り値:683

サイトで、1行ずつ予想しながら動かす →