擬似言語トレースドリル

2進数を10進数に直す｜擬似言語のトレース解説と練習問題

レベル：基礎　／　タグ：for・if・文字・配列・基数変換

関数 toDecimal は、2進数の各桁を上の桁から順に格納した文字の配列 bits を受け取り、その値を10進数の整数で返す。配列の要素番号は 1 から始まる。

プログラム

1○整数型: toDecimal(文字型の配列: bits)
2 整数型: value ← 0
3 整数型: i
4 for (i を 1 から bitsの要素数 まで 1 ずつ増やす)
5 value ← value × 2
6 if (bits[i] ＝ "1")
7 value ← value ＋ 1
8 endif
9 endfor
10 return value

何をしているか

上の桁から1文字ずつ読み、それまでの値を 2 倍してから、その桁が "1" なら 1 を足します。桁の重み（8、4、2、1）を先に計算しなくても、最後には正しい値になります。

トレースのコツ

  • 表には i、bits[i]、value を書きます。
  • 1回の繰返しで value は「2倍」と「1を足す」の最大2回変わります。行ごとに分けて書きます。
  • 最後に、普通の方法（桁の重みを足す）で検算します。

よくある間違い

  • 足してから 2 倍してしまう。順番が逆だと、最後の桁まで 2 倍されます。
  • "1"（文字）と 1（数）を混同する。比べているのは文字です。
  • "0" の桁で 2 倍するのを忘れる。2 倍は毎回行います。

例題：toDecimal({"1", "0", "0", "0", "0", "1"}) を最後まで追う

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

#行したことbitsvaluei
12宣言{"1", "0", "0", "0", "0", "1"}0—
23宣言{"1", "0", "0", "0", "0", "1"}0未定義
34繰返しの初期化{"1", "0", "0", "0", "0", "1"}01
44条件判定（真）{"1", "0", "0", "0", "0", "1"}01
55代入{"1", "0", "0", "0", "0", "1"}01
66条件判定（真）{"1", "0", "0", "0", "0", "1"}01
77代入{"1", "0", "0", "0", "0", "1"}11
84繰返しの更新{"1", "0", "0", "0", "0", "1"}12
94条件判定（真）{"1", "0", "0", "0", "0", "1"}12
105代入{"1", "0", "0", "0", "0", "1"}22
116条件判定（偽）{"1", "0", "0", "0", "0", "1"}22
124繰返しの更新{"1", "0", "0", "0", "0", "1"}23
134条件判定（真）{"1", "0", "0", "0", "0", "1"}23
145代入{"1", "0", "0", "0", "0", "1"}43
156条件判定（偽）{"1", "0", "0", "0", "0", "1"}43
164繰返しの更新{"1", "0", "0", "0", "0", "1"}44
174条件判定（真）{"1", "0", "0", "0", "0", "1"}44
185代入{"1", "0", "0", "0", "0", "1"}84
196条件判定（偽）{"1", "0", "0", "0", "0", "1"}84
204繰返しの更新{"1", "0", "0", "0", "0", "1"}85
214条件判定（真）{"1", "0", "0", "0", "0", "1"}85
225代入{"1", "0", "0", "0", "0", "1"}165
236条件判定（偽）{"1", "0", "0", "0", "0", "1"}165
244繰返しの更新{"1", "0", "0", "0", "0", "1"}166
254条件判定（真）{"1", "0", "0", "0", "0", "1"}166
265代入{"1", "0", "0", "0", "0", "1"}326
276条件判定（真）{"1", "0", "0", "0", "0", "1"}326
287代入{"1", "0", "0", "0", "0", "1"}336
294繰返しの更新{"1", "0", "0", "0", "0", "1"}337
304条件判定（偽）{"1", "0", "0", "0", "0", "1"}337
3110戻る（33）{"1", "0", "0", "0", "0", "1"}337

この例題で問われること

問　toDecimal({"1", "0", "0", "0", "0", "1"}) を呼び出したときの戻り値はどれか。

答え　33

  • 戻り値になる value は、0 → 1 → 2 → 4 → 8 → 16 → 32 → 33 と変わります。
  • 10行目で返す時点の値 33 が答えです。

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

答え　32

  • 5行目は全部で6回実行されます。
  • 実行した直後の value は、順に 0 → 2 → 4 → 8 → 16 → 32 です。
  • 6回目の直後なので、答えは 32 です。

問　7行目を2回目に実行した直後の、変数 value の値はどれか。

答え　33

  • 7行目は全部で2回実行されます。
  • 実行した直後の value は、順に 1 → 33 です。
  • 2回目の直後なので、答えは 33 です。

練習問題 標準（10問）

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

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

ほかのアルゴリズム