FE SUBJECT B
基本情報技術者 科目Bの問題解説：文字列 s="ABBCCCDDA" に対して、次の手続 lo…
問題
文字列 s="ABBCCCDDA" に対して、次の手続 longestRun(s) を実行したときの戻り値はどれか。
○整数型: longestRun(文字列型: s)
整数型: i, len ← 1, max ← 1
for (i を 2 から sの文字数 まで 1 ずつ増やす)
if (sのi文字目 = sの(i-1)文字目)
len ← len ＋ 1
else
len ← 1
endif
if (len ＞ max)
max ← len
endif
endfor
return max- ア 2
- イ 3（正解）
- ウ 4
- エ 9
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：3
この手続は文字の種類数ではなく、同じ文字が連続した最長の長さを求めています。文字が前と同じなら len を増やし、違えば連続が切れるので len を1に戻します。
ABBCCCDDAでは、BBが長さ2、CCCが長さ3、DDが長さ2です。最大値 max はCCCを読んだところで3になり、その後は更新されません。文字列全体の長さ9や、Cの位置を答えにしないようにしましょう。
| 区間 | 長さ | maxへの影響 |
|---|---|---|
| A | 1 | 初期値1 |
| BB | 2 | max=2 |
| CCC | 3 | max=3 |
| DD | 2 | 更新なし |
| A | 1 | 更新なし |
計算量と着目点：これは文字列を先頭から一度なぞるだけで最長連続区間を求める、計算量O(n)・追加領域ほぼ不要の処理です。鍵は不一致のとき len を0ではなく1に戻す点で、今読んでいる文字自身が長さ1の新しい連続の始まりだからです。0に戻すとCCCを2と数え違えてしまいます。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。