再帰関数の動的計画法（ループ配列）への書き換え

正解は「ア」です。 本問は、再帰関数 `func1` と同一の計算結果を、ループと3要素のバッファ配列 `data` を用いて反復的（動的計画法）に計算する `func2` を完成させる問題です。 1. 漸化式の確認： `func1(n)` の関係式は、 ・$$n \le 2$$ のとき：$$f(n) = 1$$ ・$$n \ge 3$$ のとき：$$f(n) = 2 \times f(n - 2) + f(n - 1)$$ 2. `func2` の配列 `data` の役割とトレース： 初期状態では `data = {1, 1, 1}` であり、それぞれ $$f(1)=1, f(2)=1, f(2)=1$$ に対応しています。 $$i = 3$$ のループに入った直後： ・`data 　1　 ← data 　2　 ` により、`data 　1　 ` には直前2つ前の値 $$f(1)$$ が入ります。 ・`data 　2　 ← data 　3　 ` により、`data 　2　 ` には直前1つ前の値 $$f(2)$$ が入ります。 ・新たな `data 　3　 `（$$f(3)$$）を計算するためには、漸化式より $$2 \times f(i - 2) + f(i - 1)$$ を計算する必要があるため、代入式は `2 × data 　1　 ＋ data 　2　 `（選択肢ア）となります。 以降のループ（$$i = 4, 5, \dots, n$$）でも、毎ステップ直前の2値が `data 　1　 ` と `data 　2　 ` に保持されて同様に正しく計算されます。 `2 × data 　2　 ＋ data 　1　 ` は $$2 \times f(i - 1) + f(i - 2)$$ となり、係数の位置が逆です。 `data` は要素数3の固定配列であるため、$$i \ge 4$$ で `data[i - 1]` などを参照すると「配列の領域外参照（エラー）」となります。 ウと同様に配列の境界外アクセスエラーが発生します。 前のステップの `data 　3　 ` を重複して加算してしまっており不適切です。 係数および余分な `data 　3　 ` の加算が含まれており不適切です。 領域外参照エラーが発生します。 領域外参照エラーが発生します。

次のプログラム中の 　a　 に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は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]
出典令和8年度 基本情報技術者試験 科目B 問3
ア
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]