基本情報技術者試験 - 令和8年公開問題(科目B) - 問3
問題
次のプログラム中の [ ] に入れる正しい答えを,解答群の中から選べ。ここで,配列の要素番号は 1 から始まる。
関数 func1 に与える引数と,関数 func2 に与える引数とが同じとき,二つの関数は同じ値を返す。プログラムでは,配列の領域外を参照してはならないものとする。
〔プログラム〕
解答群
関数 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]
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] |
正解と解説
正解設問1 ア
分野テクノロジ系 › 基礎理論 › アルゴリズムとプログラミング › プログラミング
解説
■ 問題の概要
func1 は、自分自身を呼び出す「再帰」という方法で値を計算する関数です。func2 は、同じ計算を繰返し処理で行う関数です。空欄には、func1 と同じ結果になる式を入れます。
■ func1 の計算内容
func1(n) は、次のように計算されます。- nが2以下のとき:1
- nが3以上のとき:2 × func1(n-2) + func1(n-1)
つまり、「2つ前の値の2倍」と「1つ前の値」を足したものが次の値になります。実際に計算すると、次のようになります。
func1(1) = 1
func1(2) = 1
func1(3) = 2 × 1 + 1 = 3
func1(4) = 2 × 1 + 3 = 5
func1(5) = 2 × 3 + 5 = 11
■ func2 の仕組み
func2 では、要素数3の配列 data に「2つ前の値」「1つ前の値」「今の値」を入れて、少しずつ前へずらしながら計算します。繰返しの中の最初の2行で、値が一つずつ前へずれます。この時点で、data[1] が「2つ前の値」、data[2] が「1つ前の値」になっています。したがって、新しい値 data[3] は 2 × data[1] + data[2] で求められます。
■ トレースで確認
n = 5 の場合を追ってみます。最初:data = {1, 1, 1}
i = 3:ずらすと {1, 1, ?}、data[3] ← 2 × 1 + 1 = 3 → {1, 1, 3}
i = 4:ずらすと {1, 3, ?}、data[3] ← 2 × 1 + 3 = 5 → {1, 3, 5}
i = 5:ずらすと {3, 5, ?}、data[3] ← 2 × 3 + 5 = 11 → {3, 5, 11}
戻り値は 11 で、func1(5) と一致します。
■ 選択肢の検討
- 「ア」:2つ前の値の2倍と1つ前の値を足しており、正しい式です。
- 「イ」:2倍する値と、そのまま足す値が逆になっています。
- 「ウ」「エ」「キ」「ク」:i は5などの大きな値になるため、data[i-1] などは配列(要素数3)の範囲外を参照してしまいます。
- 「オ」「カ」:古い data[3] の値まで足しているため、値が大きくなりすぎます。
正解は「ア」です。