FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次のプログラムを実行したとき、戻り値はどれか。文字番号は1か…
問題
次のプログラムを実行したとき、戻り値はどれか。文字番号は1から始まる。
文字列: s ← "abxcdba"
整数型: left ← 1, right ← sの文字数, miss ← 0
while (left ＜ right)
if (s[left] = s[right])
left ← left ＋ 1
right ← right － 1
else
miss ← miss ＋ 1
left ← left ＋ 1
endif
endwhile
return miss- ア 1
- イ 2（正解）
- ウ 3
- エ 4
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：2
一致したときは左右両方を動かしますが、不一致のときはleftだけを動かします。通常の回文判定と動きが違います。
1文字目と7文字目はa同士で一致、2文字目と6文字目はb同士で一致します。次にxとdが不一致でmiss=1，rightは5のままです。さらにcとdが不一致でmiss=2になります。
Hardでの確認点：leftとrightが常に同時に動くとは限りません。不一致時に片方だけ動く処理では、同じ文字や要素が次の比較にも残るため、通常の回文判定や単純な両端走査と混同しないことが重要です。
計算量と停止性：このループはどちらの分岐でも必ずleftが1ずつ増えるため、leftがrightに追いつくまでにかかる繰り返しは高々文字数nに比例し、計算量はO(n)です。rightは一致時しか減らないので、不一致が続くと同じrightの文字が次の比較にも残る点が、左右が必ず同時に縮む通常の回文判定との違いになります。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。