HOME»基本情報技術者試験掲示板»平成29年秋期試験午前問題  午後問9

基本情報技術者試験掲示板

掲示板検索:

平成29年秋期試験午前問題  午後問9[2162]

ITビギナーさん(No.1)

 教えて下さい。
設問2 解答 d ですが、設問3の例文をトレースして考えてみました。初めはdの答えとしてpsize-1と思ったのですが、プログラム行番号19でif文が偽になる、つまり例文の29文字目"y"が4文字目の"a"と回文にならない分さらに1引く結果psize-2になるという考え方で合ってますでしょうか。
宜しくお願いします。

2020.02.13 14:20
ITビギナーさん(No.2)

訂正です。
「平成29年秋期試験  午後問9」です。
失礼しました。

2020.02.13 14:24
納豆さん(No.3)

この投稿は投稿者により削除されました。(2020.02.14 14:24)

2020.02.14 14:24
納豆さん(No.4)

No!_Madam,_I'm_Adam_Graham._This_is_my_gym.
をtextとしてトレースすると


16行目  hit = find_last_char(ith + 1, *ith, textlen - i - 1);

今(記号含めて)5文字目の"M(m)"が探索対象(ith)だとすると
ithの1文字後ろの"a"  〜  文末  (ith+1からtextlen-i-1文字)  の範囲で
"m"を後ろから探索します。
後ろから2文字目が"m"なのでそこがhitになります。
==============================
adam,_I'm_Adam_Graham._This_is_my_gym.
(find_last_charでこのtextlen-i-1文字を後ろから探索)
==============================


18行目  psize = hit - ith + 1;
19行目  if (is_palindrome(ith, psize)) {

ith  〜  hit  まで  (ithからpsize文字)  が回文か調べます。
==============================
Madam,_I'm_Adam_Graham._This_is_my_gym
(is_palindromeでこのpsize文字の文が回文か調べる)
==============================


27行目  hit = find_last_char(ith + 1, *ith, [ d ]);

(↑の文が回文でなかった場合)
今hitの位置にある"m"とは別の"m"を見つけたいので
ithの1文字後ろの"a"  〜  hitの1文字前  (ith+1  〜  hit-1)  の範囲を
16行目と同じように探します。
ith  〜  hit  がpsize文字なので  ith+1  〜  hit-1  はpsize-2文字です
==============================
adam,_I'm_Adam_Graham._This_is_my_gy
(find_last_charでこのpsize-2文字を後ろから探索)
==============================


後は回文が見つかるまで18、19行目と27行目の処理を
可能な限り(ithの文字と一致する文字がith+1以降で見つかる限り)
繰り返します。


なんかくどい説明ですいません。

2020.02.14 14:25
ITビギナーさん(No.5)

納豆さん、丁寧な説明ありがとうございます。
納得できました。
ちなみに、回文が見つかりfind_palindromeが終了するまでの間、11行目のfor文iの値はi=4のままで合ってますか。

2020.02.14 18:51
納豆さん(No.6)

>ちなみに、回文が見つかりfind_palindromeが終了するまでの間、11行目のfor文iの値はi=4のままで合ってますか。

質問の意図を正しく汲めているかわかりませんが・・・
"M"を探索対象として回文を探している間はi=4のままであってます。
"M"の1文字後まで探しても回文が見つからなかったら
17行目〜28行目のwhileループを抜けて11行目〜29行目のforループが回りきりますので
i=5となって探索対象は"a"となりまた同じように回文を探します。

2020.02.14 20:51
ITビギナーさん(No.7)

納豆さん、ありがとうございます。
もう一度じっくりトレースしてみます。

2020.02.14 21:16
ITビギナーさん(No.8)

トレースしていて思ったのですが、プログラム行番号27の解答d psize-2 をis_palindrome関数で途中まで合致した文字数分引いたほうが効率が良さそうに感じました。
  例文として、「MabdwxwBaMbbAm」末尾からmAbまでは合致してるけど回文ではありません。is_palindrome()を改変してfind_last_char()に渡す際、psize-(l+1)なんて感じで。末尾から5番目「M」がすぐにhitすると思うのです。
 

2020.02.16 14:49
はまじさん(No.9)

合致した部分に探索する文字が含まれている可能性があるので
その方法だとうまくいかない場合があります。
単純な例ですが aaabaaaa 
aaabaaa が正しい出力ですが、上記の方法だと出力されるのは aaa です。

2020.02.16 23:48
ITビギナーさん(No.10)

はまじさん、丁寧な説明ありがとうございます。
  自分の考え方が浅はかでした。

2020.02.17 05:16

【返信投稿用フォーム】

お名前(10文字以内)

顔アイコン


本文(2,000文字以内)

記事削除用パスワード(20文字以内)

プレビュー

※宣伝や迷惑行為を防止するため当サイトとIPAサイト以外のURLを含む記事の投稿は禁止されています。

投稿記事削除用フォーム

投稿No. パスワード 
© 2010-2020 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop