基本情報技術者過去問題 平成29年秋期 午後問9

⇄問題文と設問を画面2分割で開く⇱問題PDF

問9 ソフトウェア開発(C)

次のCプログラムの説明及びプログラムを読んで,設問1〜3に答えよ。

〔プログラムの説明〕
 文字列の中から,回文(palindrome)を探して表示する関数 find_palindrome であ
る。回文とは,先頭から読んだ文字の並びと末尾から読んだ文字の並びが一致する
文字の並びのことである。ただし,ここでは次の条件を満たすものとする。
  • 文字列は英字(A〜Z,a〜z),数字(0〜9),記号(!"#%&'()*+,-./:;<=>?[]^_{|})及び空白文字から成る。
  • 文字の並びを読むとき,英字の大文字と小文字は区別しない。
  • 文字の並びを読むとき,記号及び空白文字は無視する。
  • 回文は英数字で始まり英数字で終わる。ただし,英数字1文字は回文ではない。
 本問のプログラムが表示する回文の例を表1に示す。No.1で示す文字列において,文字の並び bc0cb は回文である。c0c も回文であるが,本問のプログラムでは,文字列の先頭に最も近い文字から始まるものを表示する。また,No.2で示す文字列において,英字の大文字と小文字は区別しないので,文字の並び Bc0Cb は回文である。さらに,No.3で示す文字列において,英字の大文字と小文字を区別せず,かつ,記号及び空白文字を無視するので,文字の並び B!c0Cb は回文である。No.4で示す文字列において,文字列の先頭に最も近い b を先頭文字とする文字の並び bc0cb と bc0cb1bc0cb は,いずれも回文である。しかし,本問のプログラムでは,先頭文字位置が同じ回文が複数あれば,長さが最も短いものを表示する。
  • 関数 find_palindrome の仕様は,次のとおりである。ここで,引数の値に誤りはないものとする。
    機能:
    文字列 text の中から,回文を探して表示する。文字列 text の中に複数の回文がある場合,先頭文字位置が文字列の先頭に最も近いものを表示する。さらに,先頭文字位置が同じ回文が複数あれば,長さが最も短いものを表示する。
    引数:
    text  文字列
     関数 find_palindrome は,関数 is_palindrome 及び関数 find_char を使用する。
  • 関数 is_palindrome の仕様は,次のとおりである。ここで,引数の値に誤りはないものとする。
    機能:
    文字の並び chars が回文かどうかを判定する。
    引数:
    chars 文字の並び
    size  文字の並びcharsの長さ
    返却値:
    回文の場合は1
    回文でない場合は0
  • 関数 find_char の仕様は,次のとおりである。ここで,引数の値に誤りはないものとする。
    機能:
    文字列 str 中で,文字 ch が最初に現れる位置を求める。ただし,英字の大文字と小文字は区別しない。
    引数:
    str  文字列
    ch  文字
    返却値:
    文字 ch が現れる場合は,それが最初に現れる位置へのポインタ
    文字 ch が現れない場合は,空ポインタ
  • プログラム中で使用しているライブラリ関数の概要は,次のとおりである。
    isalnum(ch)
    文字 chが英数字のとき,0以外の値を返し,それ以外のとき,0を返す。
    tolower(ch)
    文字 ch が英大文字のとき,その文字に対応する英小文字を返し,それ以外のとき,文字 ch を返す。
    puotchar(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=
  • b=
  • c=

解説

まず、各関数のプログラムの意味と動作を簡単なものから理解しましょう。

〔関数 find_char(const char* str, char ch)〕
この関数の説明に「文字列 str 中で,文字 ch が最初に現れる位置を求める」とあります。if文でcが真ならば return 文によってその位置が返されるので、cに入る論理式は str[i] と ch が同じ文字である、と言えればいいですが、大文字と小文字を区別せず一致判定をさせる必要があります。
ライブラリ関数 tolower(ch) を使えば大文字を小文字に変換できますが、str[i] も ch もどちらが大文字かわからないので、どちらも tolower(ch) に通す必要があります。

よってcは「ウ」tolower(ch) == tolower(str[i])です。


〔関数 is_palindrome(const char* chars, int size)〕
この関数の説明には「文字の並び chars が回文かどうか判定する」とあります。関数内で宣言されている l と r は for 文内で l は chars の先頭から上がっていき、r は末尾から下がっていきます。その後の while 文で空白・記号でないときに加算または減算しています。
このことから、先頭から l 番目と末尾から r 番目の文字がすべて同じであれば回文と言えます。

if文が偽を返した場合の分岐先では return 文で 0 が返されていますので、論理式には先頭から l 番目と末尾から r 番目の文字が異なる、と言えればいいわけです。この判定も大文字小文字を区別せず判定し、どちらが大文字かわかりません。

よってbは「カ」tolower(chars[l]) != tolower(chars[r])です。


〔関数 find_palindome〕
12-14行目では、text[i] が空白・記号のとき continue でその文字に対する処理をスキップしています。そのあとの記述が重要です。

15行目においてポインタ ith に &text[i] を代入しています。次に16行目では関数 find_char(ith + 1, *ith) の結果を代入しています。関数 find_char の説明に「文字列 str 中で,文字 ch が最初に現れる位置を求める」とありました。

つまり16行目でやっていることは、

「文字 taxt[i] 以降の文字列から最初に出てくる text[i] (同じ文字)を探してポインタ hit にその位置のポインタを渡している」

ということになります。

例では,最初の文字「a」はそれ以降どこにも出てきませんので hit に代入されるのは NULL ポインタであり、直後の while 文は実行されません。その後の文字「b」は 6 文字目にでてくるので、ここのポインタが hit に渡されます。

次に while 文に入るとaがあります。これは回文となる「かもしれない」文字の並びの長さ psize を求めています。
どういうことかというと、19行目で関数 is_palindrome によって回文かどうか判定していますが、重要なのはその引数で、ポインタ ith にある位置から数えて psize 文だけのところで回文かどうか判定するのです。

例でいえば、2 文字目の b から 6 文字目の b までの 5 文字を判定するわけです。2 文字目の b はポインタ ith によって、6 文字目の b はポインタ hit によって位置が格納されていますので、hit - ith + 1 で psize が求まります。例を用いて感覚的に言えば、

 hit - ith + 1 = 6 - 2 + 1 = 5

というわけです。

よってaは「オ」hit - ith + 1です。

その後のプログラムも確認しましょう。19行目で関数 is_palindrome によって回文かどうか判定して、真ならば印字して終了です。重要なのが 27 行目です。

ここは回文かどうかを判定して、回文でないときに実行される処理です。
ここでは、hit (text[i]と同じ文字の位置) を変更してますが、今 hit にある位置以降も、text[i] と同じ文字がある可能性があるので、hit + 1 以降の文字列から *ith = text[i] を探しているんですね。

設問2

関数 find_palindrome が,先頭文字位置が同じ回文が複数ある場合,長さが最も長いものを表示するように,プログラムを変更する。表2中の に入れる正しい答えを,解答群の中から選べ。
  • 関数 find_char を,関数 find_last_char と置き換える。関数 find_last_char の仕様は,次のとおりである。ここで,引数の値に誤りはないものとする。
    機能:
    文字列 str の先頭から文字数 count 以内の範囲で文字 ch が現れる最後の位置を求める。ただし,英字の大文字と小文字は区別しない。
    引数:
    str  文字列
    ch  文字
    count 文字数
    返却値:
    文字 ch が現れる場合は,それが最後に現れる位置へのポインタ
    文字 ch が現れない場合は,空ポインタ
  • 新たに使用するライブラリ関数 strLen(text) は,文字列 text の長さ(ただし,終端ナル文字'\0'は含まない)を返す。
pm09_3.gif/image-size:554×306
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:

解答

  • d=
  • e=

解説

回文が2つ以上ある場合、長さが長いものを表示するようにプログラムを変更します。
  • 関数 find_char(const char* str, char ch) を
  • find_last_char(const char* str, char ch, int count)
に名称変更しています。
この関数で探すのは str 中、先頭から count の範囲で ch と一致する「最後の」文字です。

続いて変更内容表を確認します。

表 3 行目では textlen として回文を探索する文字列の長さを渡します。
表 4 行目は 16 行目を
  • hit = find_char(ith + 1, *ith) から
  • hit = find_last_char(ith + 1, *ith, textlen - i - 1)
としています。探すのは ith 以降の文字列ですので、全体 textlen から ith の位置分 (i + 1) を引いているわけです。(i は 0 スタートなので i + 1 を引きます)

表 5 行目は、行番号 27 を変更します。
ここも find_last_char の引数 count を考えますが、find_last_char が末尾から一致文字を探索していることに注意です。ですので、hit にある位置よりも前で再度一致文字を探索する必要があります。よって行番号 27 の変更結果は、
  • hit = find_last_char(ith + 1, *ith, psize - 2)
psize は回文の候補となった ith から hit までの文字数です。この候補が回文でなかった場合、次にヒットする文字を探す範囲は ith+1 から hit-1 になりますから、探索する文字数は psize-2 となります。

よってdは「オ」psize - 2です。

表 6 行目、関数 find_last_char の変更内容です。
末尾から探索していくのですが、当然配列は 0 から始まるので、count - 1(末尾) から 0(先頭) までで探索します。よってeに入るループ条件式は「エ」i = count - 1; i >= 0です。

設問3

次の記述中の に入れる正しい答えを,解答群の中から選べ。

 設問2で変更した関数 find_palindrome を,次の文字列を引数として実行した。ここで"␣" は空白文字を表す。
pm09_4.gif/image-size:359×29
 関数 find_palindrome が回文の表示を終了するまでに,関数 find_last_char はf回呼び出され,その最後の呼出しにおける引数 count の値はgである。
f に関する解答群
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
g に関する解答群
  • 13
  • 20
  • 31
  • 36
  • 38

解答選択欄

  • f:
  • g:

解答

  • f=
  • g=

解説

実際の回文を探索する際、実行回数を回答する問題です。

「No!_Madam,_I'm_Adam_Graham._This_is_my_gym.」(ここでは空白を_で表示)

プログラムを追いながら呼出し回数を数えていきましょう。
先頭「N」
関数 find_last_char が呼びだされるが返されるのはNULL、やり直し
2文字目「o」
上に同じ。
3-4文字目「!_」
空白・記号なので関数 find_last_char は呼び出されない。
5文字目「M」
関数 find_last_char が呼び出され末尾から 2 文字目「m」(gym の m)へのポインタが返される。
while文に入る
当然回文ではないので変更内容表 5 行目の find_last_char が実行される。
末尾から 7 文字目「m」(my の m)が返され、以下同様。
次に末尾から 18 文字目「m」(Graham の m)が返され、以下同様。←――α
次に末尾から 25 文字目「m」(Adam の m)が返され、回文(MadamImAdam)となり終了。
上記より関数 find_last_char の呼び出し回数は 6 回。よってfは 「オ」6です。

gについては、上記のαの直後、while 文の先頭に戻り、psize が求められますが、ここでの psize を考えればgがわかります。
αの直後で ith は先頭から 5 文字目、hit は先頭から 26 文字目です。なのでこの後に求まる psize は、

 hit - ith + 1 = 26 - 5 + 1 = 22

です。psize が求まったら、回文ではないので再度 hit を求めます。ここでの引数 psize - 2 = 22 - 2 = 20 が最後の呼び出しにおける引数 count の値となります。
よって空欄 g は「イ」20です。

【総評】
例年よりかなり難しいと感じました。(実際私も半分しか取れませんでした)
ポインタをよく理解していないと最初からつまずくので、設問1は c,b,a と逆順で解いた方が点が取れたかもしれません。

※本問の解説は、当サイト掲示板のスレッドNo.[1150]にご投稿いただいたものです。

平成29年秋期 午後問題一覧

問1 問2 問3 問4 問5 問6 問7 問8 問9 問10 問11 問12 問13 採点講評
© 2010-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop