擬似言語トレースドリル

値ごとの個数を数える｜擬似言語のトレース解説と練習問題

レベル：基礎　／　タグ：for・配列・配列の操作・集計

関数 tally は、配列 data に 1 から kinds までの整数がそれぞれ何個あるかを数え、個数の配列を返す。data の要素は 1 以上 kinds 以下の整数である。配列の要素番号は 1 から始まる。

プログラム

1○整数型の配列: tally(整数型の配列: data, 整数型: kinds)
2 整数型の配列: count ← {kinds 個の 0}
3 整数型: i
4 for (i を 1 から dataの要素数 まで 1 ずつ増やす)
5 count[data[i]] ← count[data[i]] ＋ 1
6 endfor
7 return count

何をしているか

データの値を、個数を入れる配列の要素番号として使います。値が 2 なら count[2] を 1 増やします。最後に、count の各要素が、その値の個数になります。

トレースのコツ

  • count[data[i]] は内側から読みます。まず data[i] の値を求め、それを要素番号にして count を見ます。
  • 表には i、data[i]、count 全体の3つを書きます。
  • count の合計は、いつでも「ここまでに見た要素の数」と同じです。検算に使えます。

よくある間違い

  • count[i] を増やしてしまう。使うのは i ではなく data[i] の値です。
  • {kinds 個の 0} を読み飛ばす。最初はすべて 0 です。
  • 値として data[i] を足してしまう。数えているのは個数なので、増やすのはいつも 1 です。

例題：tally({1, 3, 3, 1, 2, 2, 1}, 4) を最後まで追う

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

#行したことdatakindscounti
12宣言{1, 3, 3, 1, 2, 2, 1}4{0, 0, 0, 0}—
23宣言{1, 3, 3, 1, 2, 2, 1}4{0, 0, 0, 0}未設定
34繰返しの初期化{1, 3, 3, 1, 2, 2, 1}4{0, 0, 0, 0}1
44条件判定（真）{1, 3, 3, 1, 2, 2, 1}4{0, 0, 0, 0}1
55代入{1, 3, 3, 1, 2, 2, 1}4{1, 0, 0, 0}1
64繰返しの更新{1, 3, 3, 1, 2, 2, 1}4{1, 0, 0, 0}2
74条件判定（真）{1, 3, 3, 1, 2, 2, 1}4{1, 0, 0, 0}2
85代入{1, 3, 3, 1, 2, 2, 1}4{1, 0, 1, 0}2
94繰返しの更新{1, 3, 3, 1, 2, 2, 1}4{1, 0, 1, 0}3
104条件判定（真）{1, 3, 3, 1, 2, 2, 1}4{1, 0, 1, 0}3
115代入{1, 3, 3, 1, 2, 2, 1}4{1, 0, 2, 0}3
124繰返しの更新{1, 3, 3, 1, 2, 2, 1}4{1, 0, 2, 0}4
134条件判定（真）{1, 3, 3, 1, 2, 2, 1}4{1, 0, 2, 0}4
145代入{1, 3, 3, 1, 2, 2, 1}4{2, 0, 2, 0}4
154繰返しの更新{1, 3, 3, 1, 2, 2, 1}4{2, 0, 2, 0}5
164条件判定（真）{1, 3, 3, 1, 2, 2, 1}4{2, 0, 2, 0}5
175代入{1, 3, 3, 1, 2, 2, 1}4{2, 1, 2, 0}5
184繰返しの更新{1, 3, 3, 1, 2, 2, 1}4{2, 1, 2, 0}6
194条件判定（真）{1, 3, 3, 1, 2, 2, 1}4{2, 1, 2, 0}6
205代入{1, 3, 3, 1, 2, 2, 1}4{2, 2, 2, 0}6
214繰返しの更新{1, 3, 3, 1, 2, 2, 1}4{2, 2, 2, 0}7
224条件判定（真）{1, 3, 3, 1, 2, 2, 1}4{2, 2, 2, 0}7
235代入{1, 3, 3, 1, 2, 2, 1}4{3, 2, 2, 0}7
244繰返しの更新{1, 3, 3, 1, 2, 2, 1}4{3, 2, 2, 0}8
254条件判定（偽）{1, 3, 3, 1, 2, 2, 1}4{3, 2, 2, 0}8
267戻る（{3, 2, 2, 0}）{1, 3, 3, 1, 2, 2, 1}4{3, 2, 2, 0}8

この例題で問われること

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

答え　{3, 2, 2, 0}

  • 戻り値になる count は、{0, 0, 0, 0} → {1, 0, 0, 0} → {1, 0, 1, 0} → {1, 0, 2, 0} → {2, 0, 2, 0} → {2, 1, 2, 0} → {2, 2, 2, 0} → {3, 2, 2, 0} と変わります。
  • 7行目で返す時点の値 {3, 2, 2, 0} が答えです。

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

答え　{1, 0, 2, 0}

  • 5行目は全部で7回実行されます。
  • 実行した直後の count は、順に {1, 0, 0, 0} → {1, 0, 1, 0} → {1, 0, 2, 0} → {2, 0, 2, 0} → {2, 1, 2, 0} → {2, 2, 2, 0} → {3, 2, 2, 0} です。
  • 3回目の直後なので、答えは {1, 0, 2, 0} です。

練習問題 標準（5問）

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

  1. 問題01　tally({1, 1, 2, 3, 3}, 3)
  2. 問題02　tally({1, 1, 1, 2}, 3)
  3. 問題03　tally({1, 2, 1, 2}, 3)
  4. 問題04　tally({3, 1, 1, 2}, 3)
  5. 問題05　tally({3, 2, 2, 1}, 3)
もっと解く（追加の10問）
  1. 問題06　tally({3, 3, 3, 2}, 3)
  2. 問題07　tally({1, 1, 3, 1, 2}, 3)
  3. 問題08　tally({3, 3, 2, 2}, 3)
  4. 問題09　tally({2, 2, 2, 2, 3}, 3)
  5. 問題10　tally({2, 1, 3, 3, 3}, 3)
  6. 問題11　tally({3, 2, 2, 1, 1}, 3)
  7. 問題12　tally({1, 1, 1, 1, 3}, 3)
  8. 問題13　tally({3, 2, 3, 2, 2}, 3)
  9. 問題14　tally({1, 2, 3, 3}, 3)
  10. 問題15　tally({3, 3, 3, 1, 1}, 3)

練習問題 じっくり（10問）

長めのトレースで力をつける。レベル：基礎

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

ほかのアルゴリズム