基本情報技術者 2017年 秋期 午後 問09
次のCプログラムの説明及びプログラムを読んで、設問1～3に答えよ。
〔プログラムの説明〕
文字列の中から、回文(palindrome)を探して表示する関数find_palindromeである。回文とは、先頭から読んだ文字の並びと末尾から読んだ文字の並びが一致する文字の並びのことである。ただし、ここでは次の条件を満たすものとする。
・文字列は英字（A～Z, a～z）、数字（0～9）、記号(!"#%&'()*+,-./:;<=>?[]^_{|})及び空白文字から成る。
・文字の並びを読むとき、英字の大文字と小文字は区別しない。
・文字の並びを読むとき、記号及び空白文字は無視する。
・回文は英数字で始まり英数字で終わる。ただし、英数字1文字は回文ではない。
本問のプログラムが表示する回文の例を表1に示す。No.1で示す文字列において、文字の並びbc0cbは回文である。c0cも回文であるが、本問のプログラムでは、文字列の先頭に最も近い文字から始まるものを表示する。また、No.2で示す文字列において、英字の大文字と小文字は区別しないので、文字の並びBc0Cbは回文である。さらに、No.3で示す文字列において、英字の大文字と小文字を区別せず、かつ、記号及び空白文字を無視するので、文字の並びB!c0 Cbは回文である。No.4で示す文字列において、文字列の先頭に最も近いbを先頭文字とする文字の並びbc0cbとbc0cb1bc0cbは、いずれも回文である。しかし、本問のプログラムでは、先頭文字位置が同じ回文が複数あれば、長さが最も短いものを表示する。
(1) 関数find_palindromeの仕様は、次のとおりである。ここで、引数の値に誤りはないものとする。
機能：文字列textの中から、回文を探して表示する。文字列textの中に複数の回文がある場合、先頭文字位置が文字列の先頭に最も近いものを表示する。さらに、先頭文字位置が同じ回文が複数あれば、長さが最も短いものを表示する。
引数：text 文字列
関数find_palindromeは、関数is_palindrome及び関数find_charを使用する。
(2) 関数is_palindromeの仕様は、次のとおりである。ここで、引数の値に誤りはないものとする。
機能：文字の並びcharsが回文かどうかを判定する。
引数：chars 文字の並び
size 文字の並びcharsの長さ
返却値：回文の場合は1、回文でない場合は0
(3) 関数find_charの仕様は、次のとおりである。ここで、引数の値に誤りはないものとする。
機能：文字列str中で、文字chが最初に現れる位置を求める。ただし、英字の大文字と小文字は区別しない。
引数：str 文字列
ch 文字
返却値：文字chが現れる場合は、それが最初に現れる位置へのポインタ、文字chが現れない場合は、空ポインタ
(4) プログラム中で使用しているライブラリ関数の概要は、次のとおりである。
isalnum(ch)：文字chが英数字のとき、0以外の値を返し、それ以外のとき、0を返す。
tolower(ch)：文字chが英大文字のとき、その文字に対応する英小文字を返し、それ以外のとき、文字chを返す。
putchar(ch)：文字chを表示する。
設問1：
問題文を見る プログラム中のに入れる正しい答えを、解答群の中から選べ。
aに関する解答群
ア：i
イ：ith - &text[0]
ウ：ith - &text[0] + 1
エ：hit - ith
オ：hit - ith + 1
bに関する解答群
ア：l == r
イ：l != r
ウ：chars[l] == chars[r]
エ：chars[l] != chars[r]
オ：tolower(chars[l]) == tolower(chars[r])
カ：tolower(chars[l]) != tolower(chars[r])
cに関する解答群
ア：ch == str[i]
イ：ch != str[i]
ウ：tolower(ch) == tolower(str[i])
エ：tolower(ch) != tolower(str[i])
オ：(ch == tolower(str[i])) || (tolower(ch) == str[i])
カ：(ch == tolower(str[i])) && (tolower(ch) == str[i])
模範解答
a：オ、b：カ、c：ウ
解説
解答の導き方
この問題では、空欄ごとに「回文として調べる範囲の長さ」「回文の判定方法」「文字の探し方」を考えます。
a：回文として調べる範囲の長さ
16行目では、ith が指す文字と同じ文字を、ith より後ろから探して hit に格納します。つまり、ith から hit までの範囲を、19行目で回文かどうか調べます。
ポインタ（文字列内の位置を指す値）同士の差は、その位置の間にある文字数です。表1のNo.1の文字列 abc0cbe では、先頭文字位置が2番目の b で、末尾の b までの差は4です。ただし、調べる範囲には先頭の b も含めるので、長さは5文字です。
したがって、範囲の長さは「hit と ith の差に1を加えた値」です。これに当たるのは、オです。
b：左右の文字が一致するか
34行目から40行目では、左端と右端から内側へ進みます。その途中で英数字ではない文字を読み飛ばしています。これは、記号と空白文字を回文判定で無視するためです。
問題文には「英字の大文字と小文字は区別しない」とあります。そのため、左右の文字をそのまま比較するのではなく、tolower で小文字にそろえてから比べます。
41行目では、左右の文字が異なる場合に回文ではないと判定する必要があります。したがって条件は「小文字にそろえた左右の文字が異なる場合」で、カです。
c：大文字と小文字を区別せずに文字を探す
find_char は、文字列 str の中で文字 ch が最初に現れる位置を探します。仕様には「英字の大文字と小文字は区別しない」とあります。
そこで、探す文字と文字列中の文字を、それぞれ tolower で小文字にそろえて比較します。一致した場合にその位置を返すので、条件は tolower(ch) == tolower(str[i]) です。これに当たるのは、ウです。
この処理では、文字列の先頭に近い開始位置から調べます。また、同じ開始位置から候補を探すときは、find_char が後ろにある一致文字を順番に探します。そのため、回文が見つかれば、長さが最も短いものから見つかります。表示するときは元の文字列を出力するので、記号や空白文字も含まれます。
誤りやすいポイント
- aでポインタの差に1を加え忘れる
ポインタの差は、両端の文字を両方含めた長さではありません。ith と hit の両方を含めるため、差に1を加えます。 - bで文字をそのまま比較する
大文字と小文字は区別しないため、左右の文字をそのまま比べるだけでは不十分です。tolower で小文字にそろえてから比べます。 - 記号や空白文字も回文判定に含めてしまう
is_palindrome は、英数字以外の文字を読み飛ばします。一方、表示処理では元の文字列を出力するため、記号や空白文字は表示に含まれます。 - cで変換する側を取り違える
探す文字と調べる文字の両方を小文字にして比べます。片方だけを変換して比較するのではありません。
FAQ
Q: find_char は、同じ開始位置から候補を探すとき、なぜ短い回文を先に見つけられるのですか？
A: find_char は文字列の前から順に探し、最初に一致した位置を返します。そのため、開始位置に近い末尾候補から調べられ、回文であれば短いものが先に見つかります。
A: find_char は文字列の前から順に探し、最初に一致した位置を返します。そのため、開始位置に近い末尾候補から調べられ、回文であれば短いものが先に見つかります。
Q: 回文判定では記号を無視するのに、表示には記号が含まれるのはなぜですか？
A: 回文かどうかを判定するときは記号を読み飛ばしますが、表示するときは元の文字列を出力します。そのため、記号や空白文字も表示されます。
A: 回文かどうかを判定するときは記号を読み飛ばしますが、表示するときは元の文字列を出力します。そのため、記号や空白文字も表示されます。
Q: tolower は数字や記号にも影響しますか？
A: 問題文の説明では、英大文字の場合だけ対応する小文字を返し、それ以外の文字はそのまま返します。そのため、数字や記号は変化しません。
A: 問題文の説明では、英大文字の場合だけ対応する小文字を返し、それ以外の文字はそのまま返します。そのため、数字や記号は変化しません。
関連キーワード: ポインタ、ポインタ演算、文字列走査、英字の大小文字変換、回文判定
設問2：
問題文を見る 関数find_palindromeが、先頭文字位置が同じ回文が複数ある場合、長さが最も長いものを表示するように、プログラムを変更する。表2中のに入れる正しい答えを、解答群の中から選べ。
(1) 関数find_charを、関数find_last_charと置き換える。関数find_last_charの仕様は、次のとおりである。ここで、引数の値に誤りはないものとする。
機能：文字列strの先頭から文字数count以内の範囲で文字chが現れる最後の位置を求める。ただし、英字の大文字と小文字は区別しない。
引数：str 文字列
ch 文字
count 文字数
返却値：文字chが現れる場合は、それが最後に現れる位置へのポインタ、文字chが現れない場合は、空ポインタ
(2) 新たに使用するライブラリ関数strlen(text)は、文字列textの長さ（ただし、終端ナル文字'\0'は含まない）を返す。
dに関する解答群
ア：textlen - psize
イ：textlen - i - psize
ウ：textlen - i + psize
エ：psize + 2
オ：psize - 2
eに関する解答群
ア：i = count; i > 0
イ：i = count; i >= 0
ウ：i = count - 1; i > 0
エ：i = count - 1; i >= 0
模範解答
d：オ、e：エ
解説
解答の導き方
変更後は、同じ先頭文字位置から始まる回文のうち、最も長いものを探します。そのためには、先頭文字と同じ文字が現れる位置を、遠い方から調べる必要があります。
1. 先頭位置は、これまでどおり左から調べます
find_palindromeのfor文は、文字列の先頭から順に位置iを進めます。また、「回文は英数字で始まり英数字で終わる」ので、英数字でない位置は飛ばします。
このため、見つかった回文の先頭位置は、文字列の先頭に最も近いものになります。今回変更するのは、同じ先頭位置から始まる候補の調べ方です。
2. 候補の末尾は、右端から探します
表2では、行番号１６でfind_charをfind_last_charに置き換えています。find_last_charは、指定した範囲の中で、文字chが最後に現れる位置を返します。
最初の呼出しでは、ithの次の文字から文字列の末尾までを調べます。その範囲の文字数は、textlenからiと1を引いた値です。つまり、候補の末尾を最も遠い位置にして、最長の候補から判定を始めます。
候補の長さpsizeは、先頭のithから末尾のhitまでを含む長さです。候補が回文でなければ、次はそれより手前にある、先頭文字と同じ文字を末尾とする候補を調べます。
3. 次の候補を探す範囲は、psize - 2文字です
行番号２７の呼出しでは、検索の開始位置はith + 1です。現在の末尾hitは、その検索開始位置から数えると、位置psize - 2にあります。
次の候補では、現在のhitを末尾に含めてはいけません。そこを含めると、同じ候補をもう一度調べることになります。そのため、検索対象にするのは位置0から位置psize - 3までです。対象となる文字数はpsize - 2なので、dにはオが入ります。
例えば、psizeが7なら、現在のhitはith + 1から数えて位置5です。次に調べる範囲は、その手前の5文字です。現在のhitを範囲に含めず、次に近い候補を探せます。
4. count個の文字を末尾から先頭まで調べます
find_last_charの仕様では、strの先頭からcount文字が検索範囲です。文字列の添字は0から始まるので、count文字の添字は0からcount - 1です。
最後の文字から調べるには、iをcount - 1から始め、0まで含めて減らします。したがって、eにはエが入ります。countが0の場合は、最初のiが-1となり、ループの条件を満たさないため、範囲外を調べずに終了できます。
このように、まず右端の候補から判定し、回文でなければ末尾を少しずつ手前に移していきます。最初に見つかった回文が、その先頭位置から始まる最長の回文です。表1のNo.4のように「bc0cb」と「bc0cb1bc0cb」が同じ位置から始まる場合、長い方から調べることで「bc0cb1bc0cb」を先に判定できます。
誤りやすいポイント
- find_last_charのループをi = countから始めると、count個の範囲には含まれない位置を先に調べてしまいます。最後の有効な位置はcount - 1です。
- ループ条件をi > 0にすると、添字0の文字を調べられません。i >= 0として、先頭まで確認します。
- 行番号２７の検索範囲に現在のhitを含めると、回文でなかった同じ候補を再び取得する可能性があります。psize - 2文字に範囲を絞り、現在のhitより手前を調べます。
- 英字の大文字と小文字は区別しません。候補の末尾を探す処理でも、find_last_charの仕様どおりに扱います。
FAQ
Q: 最初のfind_last_charの呼出しでは、なぜ文字列の末尾まで調べるのですか？
A: 同じ先頭位置から始まる最長の候補を最初に調べるためです。回文でなければ、検索範囲を狭めて次の候補を調べます。
A: 同じ先頭位置から始まる最長の候補を最初に調べるためです。回文でなければ、検索範囲を狭めて次の候補を調べます。
Q: psize - 2ではなく、psize - 1文字を検索するとどうなりますか？
A: 検索範囲に現在のhitが含まれます。そのため、回文でなかった候補と同じhitが再び見つかる可能性があります。
A: 検索範囲に現在のhitが含まれます。そのため、回文でなかった候補と同じhitが再び見つかる可能性があります。
Q: 記号や空白文字もpsizeに含まれますか？
A: 含まれます。psizeは、ithからhitまでの文字列上の長さです。一方、回文かどうかの判定では、記号と空白文字は読み飛ばします。
A: 含まれます。psizeは、ithからhitまでの文字列上の長さです。一方、回文かどうかの判定では、記号と空白文字は読み飛ばします。
関連キーワード: 回文判定、ポインタ、文字列走査、線形探索、境界条件
設問3：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
設問2で変更した関数find_palindromeを、次の文字列を引数として実行した。ここで“␣”は空白文字を表す。
No!␣Madam,␣I'm␣Adam␣Graham.␣This␣is␣my␣gym.
関数find_palindromeが回文の表示を終了するまでに、関数find_last_charはf回呼び出され、その最後の呼出しにおける引数countの値はgである。
fに関する解答群
ア：2
イ：3
ウ：4
エ：5
オ：6
カ：7
gに関する解答群
ア：13
イ：20
ウ：31
エ：36
オ：38
模範解答
f：オ、g：イ
解説
解答の導き方
設問2では、同じ位置から始まる回文のうち、最も長いものを表示するように変更しています。変更後は、文字列の後ろ側にある同じ文字から順に調べます。したがって、始まりの位置が同じなら、長い候補から短い候補へ確認していきます。
まず、関数find_last_charの呼出し回数を数えるには、どの文字位置を調べるかを追います。文字列の位置は、C言語の配列と同じく先頭を0として数えます。この文字列の長さは43なので、末尾の「.」の位置は42です。
関数find_palindromeは、英数字以外の文字では関数find_last_charを呼び出しません。最初に調べる英数字は位置0のNです。Nは後ろにないため、この呼出しで該当文字は見つかりません。次に調べる位置1のoも、後ろにないため見つかりません。この2回も呼出し回数に含まれます。
その次は位置4のMです。英字の大文字と小文字は区別しないので、後ろにあるmも一致します。文字列中のmの位置は8、13、18、25、36、41です。関数find_last_charは、指定範囲の中で最後に現れる位置を返すので、最初は位置41を返します。
同じ位置4から始まる候補を、返された位置ごとに調べると次のようになります。ここで「正規化した文字列」は、回文かどうかを確かめるために、記号と空白文字を取り除き、英字を小文字にしたものです。
位置41の候補が回文でなければ、関数find_last_charは位置41より前の範囲を調べ、位置36を返します。同様に、位置36の候補の次は位置25、位置25の候補の次は位置18が返されます。位置18までの候補は回文なので、そこで関数find_palindromeは表示して終了します。
次に、最後の呼出しにおける引数countを求めます。countは、検索範囲に含める文字数です。表2の変更では、現在の候補より前の文字を検索するために、次の候補を探すときのcountをpsize − 2とします。
位置4から位置25までの候補では、両端を含めた長さが
です。したがって、次の検索範囲は
文字です。この検索で位置18のmが見つかり、回文と判定されます。そのため、最後の呼出しにおけるcountは20です。
呼出しを整理すると、位置0のN、位置1のo、位置4のMに対する最初の検索、そして位置41、36、25の候補を調べた後の検索です。合計で6回呼び出されます。最後に見つかった回文は、元の文字の大小や記号、空白を保ったまま表示されるため、「Madam, I'm Adam」です。
誤りやすいポイント
- 回文判定では記号と空白文字を無視しますが、表示するときは元の文字列からそのまま文字を出力します。そのため、表示結果から記号や空白文字が消えるわけではありません。
- 関数find_last_charは、範囲内で最初に見つかる文字ではなく、最後に現れる文字を返します。始まりの位置を固定したとき、後ろにある文字ほど候補が長くなります。
- countは位置番号ではなく、検索する文字数です。候補の長さpsizeから2を引くのは、現在の候補の先頭と末尾を検索範囲に含めないためです。
- 回文と判定された時点で関数find_palindromeは終了します。そのため、位置18のmが見つかった後に、さらに短い候補を調べる呼出しはありません。
FAQ
Q: 「Madam」だけでなく「Madam, I'm Adam」まで表示されるのはなぜですか？
A: 変更後は、同じ位置から始まる候補を長いものから調べます。「Madam, I'm Adam」は、記号と空白文字を無視して英字を小文字にするとmadamimadamとなり、回文です。そのため、これより長い候補が回文でないと確認された後、この文字列が表示されます。
A: 変更後は、同じ位置から始まる候補を長いものから調べます。「Madam, I'm Adam」は、記号と空白文字を無視して英字を小文字にするとmadamimadamとなり、回文です。そのため、これより長い候補が回文でないと確認された後、この文字列が表示されます。
Q: 位置41の候補を調べた後、なぜ位置36の候補に移るのですか？
A: 現在の候補の末尾にある位置41を検索範囲から外し、その前にある同じ文字を探すためです。これにより、候補を長いものから短いものへ順に調べられます。
A: 現在の候補の末尾にある位置41を検索範囲から外し、その前にある同じ文字を探すためです。これにより、候補を長いものから短いものへ順に調べられます。
Q: 表示される回文も、英字が小文字に変わりますか？
A: 変わりません。小文字への変換は回文かどうかの比較に使うだけです。表示では、元の文字列にある大文字・小文字や記号、空白文字が保たれます。
A: 変わりません。小文字への変換は回文かどうかの比較に使うだけです。表示では、元の文字列にある大文字・小文字や記号、空白文字が保たれます。
関連キーワード: 回文判定、文字列処理、ポインタ、文字列長、線形探索
