擬似言語トレースドリル

文字列の中から並びを探す　問題08

標準 レベル：中級　／　このアルゴリズムの解説を読む

練習モードは行番号つきで順に解く形式、本番形式は公開問題と同じ体裁の1問です。

関数 find は、文字の配列 text の中で、文字の配列 pat と同じ並びが最初に現れる位置（先頭の要素番号）を返す。現れなければ 0 を返す。配列の要素番号は 1 から始まる。

次のプログラムを find({"b", "a", "a", "a", "b", "a"}, {"a", "b"}) で呼び出す。

〔プログラム〕

1○整数型: find(文字型の配列: text, 文字型の配列: pat)
2 整数型: i, j
3 for (i を 1 から textの要素数 － patの要素数 ＋ 1 まで 1 ずつ増やす)
4 j ← 1
5 while (j ≦ patの要素数 and text[i ＋ j － 1] ＝ pat[j])
6 j ← j ＋ 1
7 endwhile
8 if (j > patの要素数)
9 return i
10 endif
11 endfor
12 return 0
ヒント1：トレース表の枠を見る

この列で表を作り、文を1つ実行するたびに1行足していきます。

#行したことtextpatij
ヒント2：最初の6ステップを見る

続きを同じ要領で書いていきます。太字は、その文で値が変わった変数です。

#行したことtextpatij
12宣言{"b", "a", "a", "a", "b", "a"}{"a", "b"}未定義未定義
23繰返しの初期化{"b", "a", "a", "a", "b", "a"}{"a", "b"}1未定義
33条件判定（真）{"b", "a", "a", "a", "b", "a"}{"a", "b"}1未定義
44代入{"b", "a", "a", "a", "b", "a"}{"a", "b"}11
55条件判定（偽）{"b", "a", "a", "a", "b", "a"}{"a", "b"}11
68条件判定（偽）{"b", "a", "a", "a", "b", "a"}{"a", "b"}11

設問1

5行目の条件式が評価される回数はどれか。

解答群

正解：ウ　8

  • 5行目の条件式は8回評価され、真が4回、偽が4回です。

設問2

6行目が実行される回数はどれか。

解答群

正解：ウ　4

  • 6行目が実行されるのは、5行目の条件が真になったときだけです。
  • 5行目の条件は8回評価され、真になるのは4回です。したがって 6行目は4回実行されます。

設問3

find({"b", "a", "a", "a", "b", "a"}, {"a", "b"}) を呼び出したときの戻り値はどれか。

解答群

正解：エ　4

  • 戻り値になる i は、1 → 2 → 3 → 4 と変わります。
  • 9行目で返す時点の値 4 が答えです。

本番形式

問　次の記述中の［　ａ　］と［　ｂ　］に入れる正しい答えの組合せを，解答群の中から選べ。

関数 find は，文字の配列 text の中で，文字の配列 pat と同じ並びが最初に現れる位置（先頭の要素番号）を返す。現れなければ 0 を返す。配列の要素番号は 1 から始まる。

関数 find を find({"b", "a", "a", "a", "b", "a"}, {"a", "b"}) として呼び出すと，プログラム中の α の行の条件式は［　ａ　］回評価され，戻り値は［　ｂ　］となる。

〔プログラム〕

○整数型: find(文字型の配列: text, 文字型の配列: pat)
整数型: i, j
for (i を 1 から textの要素数 － patの要素数 ＋ 1 まで 1 ずつ増やす)
j ← 1
while (j ≦ patの要素数 and text[i ＋ j － 1] ＝ pat[j])　/*** α ***/
j ← j ＋ 1
endwhile
if (j > patの要素数)
return i
endif
endfor
return 0

解答群

ａｂ
71
74
82
84
91
94

正解：エ　ａ 8，ｂ 4

  • 5行目の条件式は8回評価され、真が4回、偽が4回です。
  • 戻り値になる i は、1 → 2 → 3 → 4 と変わります。
  • 9行目で返す時点の値 4 が答えです。

α の行は，下のトレース表（行番号つき）では 5 行目です。

解説

i は text の中の「照合を始める位置」、j は pat の何文字目まで一致したかを表します。 1文字でも違えば while を抜け、i を 1 つ進めて pat の先頭から比べ直します。j が pat の要素数を超えたら、全部一致したということです。戻り値は 4 です。

行番号つきのプログラム

1○整数型: find(文字型の配列: text, 文字型の配列: pat)
2 整数型: i, j
3 for (i を 1 から textの要素数 － patの要素数 ＋ 1 まで 1 ずつ増やす)
4 j ← 1
5 while (j ≦ patの要素数 and text[i ＋ j － 1] ＝ pat[j])
6 j ← j ＋ 1
7 endwhile
8 if (j > patの要素数)
9 return i
10 endif
11 endfor
12 return 0

トレース表（全ステップ）

太字は、その文で値が変わった変数です。設問が指している行は黄色、その回は濃い黄色、変数は青い列で示します。

#行したことtextpatij
12宣言{"b", "a", "a", "a", "b", "a"}{"a", "b"}未定義未定義
23繰返しの初期化{"b", "a", "a", "a", "b", "a"}{"a", "b"}1未定義
33条件判定（真）{"b", "a", "a", "a", "b", "a"}{"a", "b"}1未定義
44代入{"b", "a", "a", "a", "b", "a"}{"a", "b"}11
55条件判定（偽）{"b", "a", "a", "a", "b", "a"}{"a", "b"}11
68条件判定（偽）{"b", "a", "a", "a", "b", "a"}{"a", "b"}11
73繰返しの更新{"b", "a", "a", "a", "b", "a"}{"a", "b"}21
83条件判定（真）{"b", "a", "a", "a", "b", "a"}{"a", "b"}21
94代入{"b", "a", "a", "a", "b", "a"}{"a", "b"}21
105条件判定（真）{"b", "a", "a", "a", "b", "a"}{"a", "b"}21
116代入{"b", "a", "a", "a", "b", "a"}{"a", "b"}22
125条件判定（偽）{"b", "a", "a", "a", "b", "a"}{"a", "b"}22
138条件判定（偽）{"b", "a", "a", "a", "b", "a"}{"a", "b"}22
143繰返しの更新{"b", "a", "a", "a", "b", "a"}{"a", "b"}32
153条件判定（真）{"b", "a", "a", "a", "b", "a"}{"a", "b"}32
164代入{"b", "a", "a", "a", "b", "a"}{"a", "b"}31
175条件判定（真）{"b", "a", "a", "a", "b", "a"}{"a", "b"}31
186代入{"b", "a", "a", "a", "b", "a"}{"a", "b"}32
195条件判定（偽）{"b", "a", "a", "a", "b", "a"}{"a", "b"}32
208条件判定（偽）{"b", "a", "a", "a", "b", "a"}{"a", "b"}32
213繰返しの更新{"b", "a", "a", "a", "b", "a"}{"a", "b"}42
223条件判定（真）{"b", "a", "a", "a", "b", "a"}{"a", "b"}42
234代入{"b", "a", "a", "a", "b", "a"}{"a", "b"}41
245条件判定（真）{"b", "a", "a", "a", "b", "a"}{"a", "b"}41
256代入{"b", "a", "a", "a", "b", "a"}{"a", "b"}42
265条件判定（真）{"b", "a", "a", "a", "b", "a"}{"a", "b"}42
276代入{"b", "a", "a", "a", "b", "a"}{"a", "b"}43
285条件判定（偽）{"b", "a", "a", "a", "b", "a"}{"a", "b"}43
298条件判定（真）{"b", "a", "a", "a", "b", "a"}{"a", "b"}43
309戻る（4）{"b", "a", "a", "a", "b", "a"}{"a", "b"}43