基本情報技術者試験過去問 令和8年度（2026年）科目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] ←
endfor
return data[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]
- ア
- イ
- ウ
- エ
- オ
- カ
- キ
- ク
正解と解き方・学習ポイント（AI解説）
unc1は、nが3以上のとき func1(n) = 2 × func1(n − 2) ＋ func1(n − 1) を返す再帰関数です。func2では、ループのたびに data[1] と data[2] を左にずらして直前の2つの値を保持し、その2つから次の値を計算して data[3] に入れます。シフト後は data[1] が func1(n − 2)、data[2] が func1(n − 1) に対応するので、空欄は 2 × data[1] ＋ data[2] です。
Point
この問題は、再帰関数で表された漸化式を、配列の値を更新しながら計算する繰返し処理に直すとき、配列の各要素がどの項に対応するかを正しく対応付けられるかを確認するものです。特に、代入によるシフトの後に data[1] と data[2] が何を表すかを整理できることが必要です。
解くために必要な知識
この問題を解くには、再帰関数の定義を漸化式として読み取り、その漸化式を繰返し処理に置き換えるときの「保持する値」と「更新順」を理解している必要があります。
用語の整理
| 用語 | 意味 |
|---|---|
| 再帰関数 | 関数の中で自分自身を呼び出す関数です。小さい入力で返す値（終了条件）を持ち、それを使って大きい入力の値を計算します。 |
| 漸化式 | あるnの値を、より小さいnの値で表す式です。例として f(n) = 2 × f(n − 2) ＋ f(n − 1) のような形です。 |
| 配列 | 複数の値を要素番号で管理する入れ物です。この問題では要素番号は1から始まります。 |
| 配列の領域外参照 | 配列に存在しない要素番号を参照することです。例えば要素数3の配列で data[4] は参照できません。 |
解くための考え方
再帰の式を「直前の値の組合せ」として読む
この問題の func1 は、nが3以上のとき次の式です。
- func1(n) = 2 × func1(n − 2) ＋ func1(n − 1)
つまり、次の値は「2つ前」と「1つ前」の2つがあれば計算できます。
ループに直すときは「過去2つを保存する」
過去2つを保存して毎回更新すれば、再帰呼出しを使わずに同じ値を計算できます。
-
2つ前を入れる場所
-
1つ前を入れる場所
-
新しい値を入れる場所
本問の func2 の data[1]、data[2]、data[3] はこの3つの役割に対応させる作りです。
更新順序に注意する
func2のループでは、data[1] と data[2] を先に更新してから data[3] を代入します。そのため、空欄には「更新後の data[1] と data[2]」を使った式を書く必要があります。
問題の解法手順
この問題では、ループ内で data[1] と data[2] が更新された後に data[3] を計算する点を押さえます。
解く手順
1. func1の定義を整理する
-
nが2以下のとき
- func1(n) = 1
-
nが3以上のとき
- func1(n) = 2 × func1(n − 2) ＋ func1(n − 1)
確認用に小さいnで計算します。
| n | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| func1(n) | 1 | 1 | 3 | 5 | 11 |
2. func2のdataが保持すべき値を決める
配列 data は要素数3で、ループごとに次の更新をします。
-
data[1] ← data[2]
-
data[2] ← data[3]
-
data[3] ← （空欄）
この更新により、シフト後は次の対応になるようにするのが自然です。
| シフト後の要素 | 表す値 |
|---|---|
| data[1] | func1(i − 2) |
| data[2] | func1(i − 1) |
| data[3] | func1(i) |
3. 漸化式をそのままdataに当てはめる
func1(i) = 2 × func1(i − 2) ＋ func1(i − 1) なので、上の対応表を使うと次になります。
- data[3] = 2 × data[1] ＋ data[2]
4. 検算する
初期値 data = {1, 1, 1} です。
-
i = 3
- シフト後 data[1] = 1、data[2] = 1
- data[3] = 2 × 1 ＋ 1 = 3
- func1(3) = 3 と一致します。
-
i = 4
- 次のシフト後 data[1] = 1、data[2] = 3
- data[3] = 2 × 1 ＋ 3 = 5
- func1(4) = 5 と一致します。
よって空欄は 2 × data[1] ＋ data[2] です。
選択肢ごとの解説
- ア：正解
シフト後に data[1] が func1(n − 2)、data[2] が func1(n − 1) を表すように更新されます。漸化式 func1(n) = 2 × func1(n − 2) ＋ func1(n − 1) にそのまま対応するので正しいです。
- イ：不正解
不正解です。2倍している対象が1つ前の値になっており、func1(n) = 2 × func1(n - 2) + func1(n - 1) の形と一致しません。
- ウ：不正解
不正解です。dataは要素番号1から3までの配列です。iが4以上になると data[i - 1] はdata[3]より大きい要素番号を参照する可能性があり、領域外参照になります。
- エ：不正解
不正解です。dataは要素番号1から3までの配列です。iが4以上になると data[i - 1] や data[i - 2] がdata[3]より大きい要素番号を参照する可能性があり、領域外参照になります。
- オ：不正解
不正解です。func1の定義式は「2つ前と1つ前」だけで次の値を計算します。data[3]（更新前の現在値）を加算する形は、func1の定義式と一致しません。
- カ：不正解
不正解です。func1の定義式に含まれないdata[3]の加算が入っており、func1と同じ値になりません。
- キ：不正解
不正解です。data[i - 1]などはiが4以上で領域外参照になる可能性があります。また、func1の定義式にないdata[3]の加算も含まれています。
- ク：不正解
不正解です。data[i - 2]やdata[i - 1]はiが4以上で領域外参照になる可能性があります。また、func1の定義式にないdata[3]の加算も含まれています。
まとめ
unc1は、nが3以上のとき func1(n) = 2 × func1(n − 2) ＋ func1(n − 1) を返す再帰関数です。func2では、ループのたびに data[1] と data[2] を左にずらして直前の2つの値を保持し、その2つから次の値を計算して data[3] に入れます。シフト後は data[1] が func1(n − 2)、data[2] が func1(n − 1) に対応するので、空欄は 2 × data[1] ＋ data[2] です。
シフト後に data[1] が func1(n − 2)、data[2] が func1(n − 1) を表すように更新されます。漸化式 func1(n) = 2 × func1(n − 2) ＋ func1(n − 1) にそのまま対応するので正しいです。
不正解です。2倍している対象が1つ前の値になっており、func1(n) = 2 × func1(n - 2) + func1(n - 1) の形と一致しません。
不正解です。dataは要素番号1から3までの配列です。iが4以上になると data[i - 1] はdata[3]より大きい要素番号を参照する可能性があり、領域外参照になります。
不正解です。dataは要素番号1から3までの配列です。iが4以上になると data[i - 1] や data[i - 2] がdata[3]より大きい要素番号を参照する可能性があり、領域外参照になります。
不正解です。func1の定義式は「2つ前と1つ前」だけで次の値を計算します。data[3]（更新前の現在値）を加算する形は、func1の定義式と一致しません。
不正解です。func1の定義式に含まれないdata[3]の加算が入っており、func1と同じ値になりません。
不正解です。data[i - 1]などはiが4以上で領域外参照になる可能性があります。また、func1の定義式にないdata[3]の加算も含まれています。
不正解です。data[i - 2]やdata[i - 1]はiが4以上で領域外参照になる可能性があります。また、func1の定義式にないdata[3]の加算も含まれています。