うごく基本情報

サンプル問題セット(2022年12月公開) 科目B 問3

配列 ・ 累積和 ・ トレース

次の記述中の[ ]に入れる正しい答えを,解答群の中から選べ。ここで,配列の要素番号は 1 から始まる。
関数 makeNewArray は,要素数 2 以上の整数型の配列を引数にとり,整数型の配列を返す関数である。関数 makeNewArray を makeNewArray({3, 2, 1, 6, 5, 4})として呼び出したとき,戻り値の配列の要素番号 5 の値は[ ]となる。

○整数型の配列: makeNewArray(整数型の配列: in)
  整数型の配列: out ← {}  // 要素数0の配列
  整数型: i, tail
  outの末尾 に in[1]の値 を追加する
  for (i を 2 から inの要素数 まで 1 ずつ増やす)
    tail ← out[outの要素数]
    outの末尾 に (tail + in[i]) の結果を追加する
  endfor
  return out
答え
ア5
イ6
ウ9
エ11
オ12
カ17
キ21

出典:基本情報技術者試験 科目B試験 サンプル問題セット(2022年12月公開) 問3

正解と解説を見る

正解:カ

ポイント:累積和:新しい配列の各要素=それまでの要素の合計。前の結果に次の値を足していく。

makeNewArray は、out の末尾の値 tail に in[i] を足したものを、out に追加していきます。つまり out[k] は in[1] から in[k] までの合計(累積和)です。
in={3, 2, 1, 6, 5, 4} のとき
out[1]=3
out[2]=3+2=5
out[3]=5+1=6
out[4]=6+6=12
out[5]=12+5=17
out[6]=17+4=21
問われている out[5] は 17 で(カ)。
よくある間違い:最後の要素 out[6]=21(キ)を答える、または in[5]=5(ア)を答える。

解説と下の表はこのサイトが作成したものです(表は、正解の選択肢を入れたプログラムを実際に実行した結果です)。

正解のプログラムを動かしてみる

makeNewArray({3, 2, 1, 6, 5, 4}) を呼び出したときに、1行ずつ何が起きるかの表です(全部で 21 手)。「真・偽」は、その行の条件の判定です。

手実行した行変わった値
11行目○整数型の配列: makeNewArray(整数型の配列: in)in = {3, 2, 1, 6, 5, 4}
22行目整数型の配列: out ← {} // 要素数0の配列out = {}
33行目整数型: i, tail
44行目outの末尾 に in[1]の値 を追加するout = {3}
55行目for (i を 2 から inの要素数 まで 1 ずつ増やす)真
i = 2
66行目tail ← out[outの要素数]tail = 3
77行目outの末尾 に (tail + in[i]) の結果を追加するout = {3, 5}
85行目for (i を 2 から inの要素数 まで 1 ずつ増やす)真
i = 3
96行目tail ← out[outの要素数]tail = 5
107行目outの末尾 に (tail + in[i]) の結果を追加するout = {3, 5, 6}
115行目for (i を 2 から inの要素数 まで 1 ずつ増やす)真
i = 4
126行目tail ← out[outの要素数]tail = 6
137行目outの末尾 に (tail + in[i]) の結果を追加するout = {3, 5, 6, 12}
145行目for (i を 2 から inの要素数 まで 1 ずつ増やす)真
i = 5
156行目tail ← out[outの要素数]tail = 12
167行目outの末尾 に (tail + in[i]) の結果を追加するout = {3, 5, 6, 12, 17}
175行目for (i を 2 から inの要素数 まで 1 ずつ増やす)真
i = 6
186行目tail ← out[outの要素数]tail = 17
197行目outの末尾 に (tail + in[i]) の結果を追加するout = {3, 5, 6, 12, 17, 21}
205行目for (i を 2 から inの要素数 まで 1 ずつ増やす)偽
i = 7
219行目return out

戻り値:{3, 5, 6, 12, 17, 21}

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