擬似言語トレースドリル

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

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

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

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

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

〔プログラム〕

1○整数型: find(文字型の配列: text, 文字型の配列: pat)
2 整数型: i, j
3 for (i を 1 から textの要素数 － patの要素数 ＋ 1 まで 1 ずつ増やす)
4 j ← 1
5 while (j ≦ patの要素数 and text[［　ａ　］] ＝ 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宣言{"a", "a", "b", "b", "a"}{"b", "a"}未定義未定義
23繰返しの初期化{"a", "a", "b", "b", "a"}{"b", "a"}1未定義
33条件判定（真）{"a", "a", "b", "b", "a"}{"b", "a"}1未定義
44代入{"a", "a", "b", "b", "a"}{"b", "a"}11
55条件判定（偽）{"a", "a", "b", "b", "a"}{"b", "a"}11
68条件判定（偽）{"a", "a", "b", "b", "a"}{"b", "a"}11

設問1

find({"a", "a", "b", "b", "a"}, {"b", "a"}) を呼び出すと戻り値は 4 になる。プログラム中の ［　ａ　］ に入れる正しい答えはどれか。

解答群

正解：ウ　i ＋ j － 1

  • それぞれの選択肢を空欄に入れて、実際に動かした結果は次のとおりです。
  • 「i ＋ j」→ 戻り値は 3
  • 「i ＋ j ＋ 1」→ 戻り値は 2
  • 「i ＋ j － 1」→ 戻り値は 4（正解）
  • 「i」→ 戻り値は 0

設問2

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

解答群

正解：ウ　7

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

設問3

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

解答群

正解：イ　3

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

本番形式

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

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

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

〔プログラム〕

○整数型: 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

解答群

ａｂ
62
73
74
82
83
84

正解：ウ　ａ 7，ｂ 4

  • 5行目の条件式は7回評価され、真が3回、偽が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宣言{"a", "a", "b", "b", "a"}{"b", "a"}未定義未定義
23繰返しの初期化{"a", "a", "b", "b", "a"}{"b", "a"}1未定義
33条件判定（真）{"a", "a", "b", "b", "a"}{"b", "a"}1未定義
44代入{"a", "a", "b", "b", "a"}{"b", "a"}11
55条件判定（偽）{"a", "a", "b", "b", "a"}{"b", "a"}11
68条件判定（偽）{"a", "a", "b", "b", "a"}{"b", "a"}11
73繰返しの更新{"a", "a", "b", "b", "a"}{"b", "a"}21
83条件判定（真）{"a", "a", "b", "b", "a"}{"b", "a"}21
94代入{"a", "a", "b", "b", "a"}{"b", "a"}21
105条件判定（偽）{"a", "a", "b", "b", "a"}{"b", "a"}21
118条件判定（偽）{"a", "a", "b", "b", "a"}{"b", "a"}21
123繰返しの更新{"a", "a", "b", "b", "a"}{"b", "a"}31
133条件判定（真）{"a", "a", "b", "b", "a"}{"b", "a"}31
144代入{"a", "a", "b", "b", "a"}{"b", "a"}31
155条件判定（真）{"a", "a", "b", "b", "a"}{"b", "a"}31
166代入{"a", "a", "b", "b", "a"}{"b", "a"}32
175条件判定（偽）{"a", "a", "b", "b", "a"}{"b", "a"}32
188条件判定（偽）{"a", "a", "b", "b", "a"}{"b", "a"}32
193繰返しの更新{"a", "a", "b", "b", "a"}{"b", "a"}42
203条件判定（真）{"a", "a", "b", "b", "a"}{"b", "a"}42
214代入{"a", "a", "b", "b", "a"}{"b", "a"}41
225条件判定（真）{"a", "a", "b", "b", "a"}{"b", "a"}41
236代入{"a", "a", "b", "b", "a"}{"b", "a"}42
245条件判定（真）{"a", "a", "b", "b", "a"}{"b", "a"}42
256代入{"a", "a", "b", "b", "a"}{"b", "a"}43
265条件判定（偽）{"a", "a", "b", "b", "a"}{"b", "a"}43
278条件判定（真）{"a", "a", "b", "b", "a"}{"b", "a"}43
289戻る（4）{"a", "a", "b", "b", "a"}{"b", "a"}43