平成29年(H29)秋期 基本情報技術者試験 C言語問題 解き方解説

平成29年度秋期午後のC言語問題である問9の私の解き方・考え方について解説していきます。

問題

IPAの公式サイトで公開されています。このページでは問9についての解説を行います。

https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2017h29_2/2017h29a_fe_pm_qs.pdf

問題の概要

回文に関する問題ですね。回文というのは例えば「新聞紙」「竹やぶ焼けた」などのように前から読んでも後ろから読んでも同じ言葉になるものです。ただし、この問題では前から読んでも後ろから読んでも同じ、という条件の他に下記の条件もあります。

回文の条件1
  • 文字列は英字、数字、記号及び空白文字から成る。
  • 文字の並びを読むとき、英字の大文字と小文字は区別しない。
  • 文字の並びを読むとき、記号及び空白文字は無視する。
  • 回文は英数字で始まり英数字で終わる。ただし、英数字1文字は回文ではない。

また、設問1で扱うプログラムでは回文が複数あっても表示する回文は1つです。複数回文があるときには、下記の条件でどの回文を表示するかが選ばれます。

回文の条件2
  • 文字列の先頭に最も近い文字から始まるものを表示する
  • 先頭文字位置が同じ回文が複数あれば、長さが最も短いものを表示する

この条件が問題を解く上でのポイントの1つになるので内容は頭に入れておいた方が良いです。実例を表1で示し、文章で解説してくれているのでよく読んでおくと設問に回答しやすくやると思います。

スポンサーリンク

設問1

それでは設問を解いていきましょう。設問1はプログラムの穴埋め問題です。まずfind_palindrome関数のfor文のなかでどのような処理を行っているかを確認し、[   a   ]の回答を導きましょう。find_palindrome関数のfor文の中を6つに分割してみました。

まず①から⑥で大まかにどのような処理を行なっているかを解説します。

①はtext[i]が英数字でない場合に②から⑥の処理をスキップする処理を行います。

②はtext[i]の文字がtext[i+1]以降の文字列の中に存在するかどうかを確認する処理を行っています。回文であれば先頭の文字は文字列の中に必ずもう一つ以上存在するはずです。

③はtext[i]を先頭文字とした回文が見つかるまでループするためのwhile文です。

④は穴埋め部分ですので一旦飛ばします。

⑤はアドレスithからpsize文字数分の文字列が回文である場合にその回文を表示して関数を終了する処理を行っています。

⑥は、⑤で回文でないと判断された場合に、hit+1を先頭アドレスとする文字列の中に*ith(つまりtext[i]の文字)があるかどうかを確認し、もしあれば③のループに戻ります。

大まかな処理の流れはこの通りです。

次はtext配列として実際に下記が与えられたとし、それぞれでどのような動きをするのかをi=の状態から具体的に見ていきます。

まず①で、isalnum関数によりtext[0]が英数字であるかどうかの確認をし、英数字でない場合にcontinueにより以降の処理をスキップします。ですが、i=0の時は文字が”A”なのでスキップせずに処理が継続されます。

次に②で、ithポインタにtext[0]のアドレスを格納し、find_char関数にith+1のアドレス(つまりtext[1]のアドレス)が指す文字列”Bc0CbE”とithの指すアドレスに格納されている文字”A”を渡します。

find_char関数は第一引数で渡された文字列に第二引数の文字が含まれている場合は文字列内のその文字のアドレスを返却し、含まれない場合はNULLを返却しますので、この場合はNULLが返却され、③以降の処理は行われず、i=1の時の処理に移ります。

i=1の時、text[1]は”B”ですので先ほどと同様に①ではcontinueされません。続いて②でithにはtext[1]のアドレスがセットされfind_char関数にith+1(つまりtext[2])のアドレスと文字”B”が渡され実行されます。

find_char関数は大文字小文字は区別しません。ですので、find_char関数はith+1を先頭アドレスとする文字列には文字”b”が存在するため”b”が格納されているアドレスを返却します。そしてそのアドレスがポインタhitに格納されます。

hitがNULL以外のアドレスが格納されているので今度は③以降の処理が実行されます。

③は回文が見つかるまでループするためのwhile文です。

④は穴埋め部分ですので一旦飛ばし、先に⑤の説明をします。⑤はis_palindrome関数で与えられた文字数の文字列が回文であるかどうかをまず調べています。ここで④で代入されるpsizeがis_palindrome関数の第二引数(つまり文字数)として使用されています。②よりithとhitの指すアドレスの文字が一致することが分かっており、ithからhitの間の文字列が回文である可能性があります。ですのでpsizeはithからhitの間の文字列の文字数であると分かります。

ithからhitの文字数は、「hit – ith + 1」となりますので、psizeに代入される[   a   ]は選択肢オの「hit – ith + 1」となります。

[   b   ]は回文かどうかを判断するis_palindrome関数の穴埋めです。35行目から40行目は英数字以外をスキップしています。41行目の条件文が成立すれば、42行目で直ちにreturn文で関数を終了すること、さらに、return値が回文でないことを示す0であることから、41行目の条件文である[   b   ]は「文字が一致しない場合」を示すものとなることが分かります。なので、選択肢としてはエかカに絞れます。さらに、is_palindrome関数は大文字と小文字を区別せずに回文であるかどうかを判断する仕様となっていますので、エだと大文字と小文字を区別して判断されてしまうため正解ではないです。カだと大文字であってもtolower関数で小文字に変換してから判断できますので、大文字と小文字を区別なしに回文かどうかを判断できます。したがって、[   b   ]は選択肢カの「tolower(chars[l]) != tolower(chars[r])」となります。

設問1の最後は[   c   ]です。[   c   ]はfind_char関数の穴埋めになります。find_char関数は、strに大文字小文字区別なしにchと同じ文字があれば、strのその文字のアドレスを返却する関数ですので、[   c   ]はstr[i]とchが大文字小文字区別なしに同じ文字であるかどうかを判断する条件文となります。したがって、[   c   ]は選択肢ウの「tolower(ch) == tolower(str[i])」となります。オとカは引っ掛けの選択肢ですね。chもstr[i]も両方大文字の時に違う文字と判断されてしまうので正解ではないです。

設問2

続いて設問2に移ります。設問2も穴埋め問題ですね。設問2では表示する回文の条件2が変わります。

回文の条件2
  • 文字列の先頭に最も近い文字から始まるものを表示する
  • 先頭文字位置が同じ回文が複数あれば、長さが最も長いものを表示する

そのため、find_char関数がfind_last_char関数に置き換わっています。find_last_char関数ではfind_char関数から入力文字列から指定された文字を検索する文字数を指定できるようになり、後ろから文字chに一致するstr[i]を探すように変わっています。find_palindrome関数の最初で入力文字列の文字数を格納するtextLen変数が追加されています。

例えば下図のように、”ABf0CbE”が入力された時はtextLenが7になります。実際にi=1の時にどのようにプログラムが動けば回文の条件2を満たした回文を表示できるかを考えてみましょう。

i=1の時のfind_last_char関数の動きから考えてみましょう。i=1の時は16行目のfind_last_char関数には第一引数にith+1を先頭アドレスとした文字列”Bf0CbE”が、第二引数にithが指すアドレスに格納されている文字”B”が、第三引数にはtextLen-i-1の結果である”5″が渡されます。

find_last_char関数では第一引数に指定された文字列の中に第二引数に指定された文字が複数存在する場合はより後ろ側にある文字の位置を返却する仕様になっています。ですので、文字列の最後から前に向かって順に1文字ずつ一致するかどうかを確認していき、一致した時点で文字の位置(アドレス)を返却してやれば仕様を満たせます。

ですので、[   e   ]は文字列の最後から順に前方向に向かってループするようなループ文とする必要があります。

find_last_char関数の第三引数のcountは入力された文字列strの文字数ですので、まず最初に最後の文字がchと一致するかどうかを調べるためにはiをcount-1で初期化する必要があります。さらにそこから文字列の前の方に向かって1文字ずつchと一致するかどうかを調べ、最終的にstr[0]の文字まで調べる必要があります。したがって、find_last_char関数の仕様を満たすためには、for文の初期化部分は「i = count-1」、続行条件は「i >= 0」とするのが正しいです。したがって[   e   ]は選択肢エとなります。

続いて[   d   ]を解くためにプログラムの動きをさらに追っていきましょう。i=1時の16行目のfind_last_char関数を実行すると、hitに”b”が格納されいる位置のアドレスが格納されます。

そして設問1の時同様にis_parindrom関数が実行されます。

ただし、今回は文字列を変えていますので、is_parindrome関数は0を返します。この直後に実行されるのが27行目のfind_last_char関数(表2)になります。[   d   ]には第1引数で指定する文字列の中から第二引数の文字があるかどうかを調べる文字数が入ります。すでにhit以降(hitを含む)では回文は存在しないことは直前で実行したis_palindrome関数で判明していますので、hitよりも前の部分から*ithに一致する文字を探すので良さそうです。第一引数で指定する文字列はith+1ですので、ithも検索対象外です。ですので、psizeからith部分とhit部分を引いたpsize-2文字数だけ検索するので良いことになります。したがって[   d   ]は選択肢オの「psize-2」となります。

設問3

設問3は与えられた文字列をfind_palindrome関数に入力した時の動作を問われている問題です。具体的にはfind_last_char関数の実行回数と最後に実行した時の第三引数の値を問われています。実際に動きを追ってみましょう。

i=0

text[0]は”N”ですのでfind_last_char関数が実行されます。*ithは”N”であり、第三引数のcountは42となります。ith+1から42文字の間に”N”はありませんので、find_last_char関数はNULLを返却し、i=0の時の処理を終えます。

i=1

text[1]は”o”ですので2回目のfind_last_char関数が実行されます。*ithは”o”であり、第三引数のcountは41となります。ith+1から41文字の間に”o”はありませんので、find_last_char関数はNULLを返却し、i=1の時の処理を終えます。

i=2

text[2]は”!”ですのでfind_last_char関数が実行されずにすぐにi=2の時の処理を終えます。

i=3

text[3]は” “ですのでfind_last_char関数が実行されずにすぐにi=3の時の処理を終えます。

i=4

text[4]は”M”ですので3回目のfind_last_char関数が実行されます。*ithは”M”であり、第三引数のcountは38となります。ith+1から38文字の間に”m”が存在しますので、そのアドレスがhitに格納されます。ただし、ithからhitの文字列は回文ではないのでさらにfind_last_char関数が実行されます。

4回目のfind_last_char関数の実行では第三引数countは36となります。ith+1から36文字の間に”m”が存在しますので、そのアドレスがhitに格納されます。ただし、ithからhitの文字列は回文ではないのでさらにfind_last_char関数が実行されます。

5回目のfind_last_char関数の実行では第三引数countは31となります。ith+1から31文字の間に”m”が存在しますので、そのアドレスがhitに格納されます。ただし、ithからhitの文字列は回文ではないのでさらにfind_last_char関数が実行されます。

6回目のfind_last_char関数の実行では第三引数countは20となります。ith+1から20文字の間に”m”が存在しますので、そのアドレスがhitに格納されます。さらにithからhitの文字列は回文の条件に当てはまりますので、回文が表示されてfind_palindrome関数は終了します。

したがって、find_last_char関数は6回実行され、最後に実行時のcountの値は20となります。つまり、[   f   ]は選択肢オの6となり、[   g   ]は選択肢イの20となります。

スポンサーリンク

解いてみた感想

問題自体が難しいですね。そこでさらにポインタや文字列操作についての知識が必要ですので難易度高めだと思いました。解説書くのも難しかったです・・・。もともと文字列関連はケアレスミスが多かったので、図を書いて整理しながらなんとか解いたという感じです。文字列の問題は基本情報技術者試験でも多く扱われていますので過去問解いて慣れておくことをオススメします。

本ページの図・プログラム・問題文について

図やプログラム、問題文はIPA公開の過去問題から引用しています。また図やプログラムに関しては説明に必要な部分に関してのみ加工して使用させていただいております。

出典:平成29年度 秋期 基本情報技術者試験(FE)試験区分 午後 問8

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です