基本情報技術者試験 - 令和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] ← [   ]
 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] の値まで足しているため、値が大きくなりすぎます。
 正解は「ア」です。
ホーム画面への追加方法
1.ブラウザの 共有ボタンのアイコン 共有ボタンをタップ
2.メニューの「ホーム画面に追加」をタップ
閉じる