擬似言語トレースドリル

累積和｜擬似言語のトレース解説と練習問題

レベル：入門　／　タグ：for・配列・配列の操作

関数 prefix は、配列 data の各要素を「先頭からその要素までの合計」に置き換えて返す。配列の要素番号は 1 から始まる。

プログラム

1○整数型の配列: prefix(整数型の配列: data)
2 整数型: i
3 for (i を 2 から dataの要素数 まで 1 ずつ増やす)
4 data[i] ← data[i － 1] ＋ data[i]
5 endfor
6 return data

何をしているか

各要素を「先頭からその要素までの合計」に置き換えます。1つ前の要素にはすでに合計が入っているので、それに自分の値を足すだけで済みます。

トレースのコツ

  • 配列を書き換えながら進みます。data[i － 1] は書き換えた後の値です。元の値ではありません。
  • 1回ごとに配列全体を書き直すと、取り違えません。
  • 最後の要素は、配列全体の合計になります。検算に使えます。

よくある間違い

  • data[i － 1] に元の配列の値を使う。そうすると「隣どうしの和」になってしまいます。
  • 繰返しを 1 から始めてしまい、存在しない 0 番目を見にいく。1番目は、それ自身が合計なので変わりません。
  • 途中の回の配列を聞かれているのに、最後の結果を答える。

例題：prefix({5, 4, 7, 2, 7, 7}) を最後まで追う

上のプログラムを prefix({5, 4, 7, 2, 7, 7}) で呼び出したときの、全ステップのトレース表です。太字は、その文で値が変わった変数です。

#行したことdatai
12宣言{5, 4, 7, 2, 7, 7}未設定
23繰返しの初期化{5, 4, 7, 2, 7, 7}2
33条件判定（真）{5, 4, 7, 2, 7, 7}2
44代入{5, 9, 7, 2, 7, 7}2
53繰返しの更新{5, 9, 7, 2, 7, 7}3
63条件判定（真）{5, 9, 7, 2, 7, 7}3
74代入{5, 9, 16, 2, 7, 7}3
83繰返しの更新{5, 9, 16, 2, 7, 7}4
93条件判定（真）{5, 9, 16, 2, 7, 7}4
104代入{5, 9, 16, 18, 7, 7}4
113繰返しの更新{5, 9, 16, 18, 7, 7}5
123条件判定（真）{5, 9, 16, 18, 7, 7}5
134代入{5, 9, 16, 18, 25, 7}5
143繰返しの更新{5, 9, 16, 18, 25, 7}6
153条件判定（真）{5, 9, 16, 18, 25, 7}6
164代入{5, 9, 16, 18, 25, 32}6
173繰返しの更新{5, 9, 16, 18, 25, 32}7
183条件判定（偽）{5, 9, 16, 18, 25, 32}7
196戻る（{5, 9, 16, 18, 25, 32}）{5, 9, 16, 18, 25, 32}7

この例題で問われること

問　prefix({5, 4, 7, 2, 7, 7}) を呼び出したときの戻り値はどれか。

答え　{5, 9, 16, 18, 25, 32}

  • 戻り値になる data は、{5, 4, 7, 2, 7, 7} → {5, 9, 7, 2, 7, 7} → {5, 9, 16, 2, 7, 7} → {5, 9, 16, 18, 7, 7} → {5, 9, 16, 18, 25, 7} → {5, 9, 16, 18, 25, 32} と変わります。
  • 6行目で返す時点の値 {5, 9, 16, 18, 25, 32} が答えです。

問　4行目を3回目に実行した直後の、変数 data の値はどれか。

答え　{5, 9, 16, 18, 7, 7}

  • 4行目は全部で5回実行されます。
  • 実行した直後の data は、順に {5, 9, 7, 2, 7, 7} → {5, 9, 16, 2, 7, 7} → {5, 9, 16, 18, 7, 7} → {5, 9, 16, 18, 25, 7} → {5, 9, 16, 18, 25, 32} です。
  • 3回目の直後なので、答えは {5, 9, 16, 18, 7, 7} です。

練習問題 標準（10問）

本試験と同じくらいの量。レベル：入門

  1. 問題01　prefix({1, 1, 7, 4, 4})
  2. 問題02　prefix({5, 1, 4, 1, 6, 3})
  3. 問題03　prefix({3, 2, 9, 3, 2, 8})
  4. 問題04　prefix({4, 8, 1, 1, 3, 4})
  5. 問題05　prefix({6, 8, 6, 5})
  6. 問題06　prefix({4, 6, 9, 2, 1, 6})
  7. 問題07　prefix({7, 5, 2, 9, 8})
  8. 問題08　prefix({6, 5, 7, 7, 1, 1})
  9. 問題09　prefix({3, 7, 8, 6, 5})
  10. 問題10　prefix({1, 4, 3, 7, 6, 4})
もっと解く（追加の20問）
  1. 問題11　prefix({3, 5, 2, 8, 7})
  2. 問題12　prefix({7, 2, 1, 1})
  3. 問題13　prefix({8, 3, 7, 2, 2, 7})
  4. 問題14　prefix({3, 9, 7, 6})
  5. 問題15　prefix({9, 4, 7, 6, 7, 7})
  6. 問題16　prefix({2, 8, 5, 3, 9})
  7. 問題17　prefix({4, 4, 4, 6, 4, 5})
  8. 問題18　prefix({6, 7, 8, 4, 2})
  9. 問題19　prefix({3, 9, 4, 9, 1, 8})
  10. 問題20　prefix({6, 4, 7, 3, 9, 2})
  11. 問題21　prefix({1, 6, 8, 1, 8, 6})
  12. 問題22　prefix({9, 1, 7, 7, 9, 7})
  13. 問題23　prefix({1, 3, 1, 1})
  14. 問題24　prefix({1, 9, 2, 3, 7, 6})
  15. 問題25　prefix({7, 3, 7, 6})
  16. 問題26　prefix({6, 9, 1, 7, 2})
  17. 問題27　prefix({6, 5, 9, 2, 8})
  18. 問題28　prefix({7, 9, 2, 8})
  19. 問題29　prefix({3, 1, 5, 7})
  20. 問題30　prefix({2, 8, 5, 7})

ほかのアルゴリズム