平成29年秋期午後問8の設問4について

新人さん  
(No.1)
設問4について、解説には
表の第1行目は第5行目から数えて5番目(奇数番目)なので、~(中略)元の文字と同じ文字である必要があります
とありますが
行が偶数番目だった場合は同じ文字でなくても誤りがないと判定される場合があるのでしょうか?
なんとなく横軸縦軸で検査されたら誤検出はなさそうだなってイメージで「カ」を選んで正解でしたが、きちんとトレースして考えるべきなのかが気になりました。

https://www.fe-siken.com/kakomon/29_aki/pm08.html
2021.02.16 14:02
いいね正解大卒さん 
FE ブロンズマイスター
(No.2)
自分もちょっと自信がないんですが、私が計算した結果を述べさせていただきます。

☆まず前提の確認から
検証文字付文字列の検証において奇数番目の文字に割り当てた数値はそのまま足し合わされ、偶数番目の文字に割り当てた数値は2倍して30で割った商と余りを足し合わされます。
解説通り、異なる文字に割り当てられた数字同士に衝突がないため、奇数番目の文字に関しては同じ文字でなければなりません。ここまではご承知かと思います。

☆証明っぽいもの
では、偶数番目の場合を考えます。2つの数をnとmとしておきます(ただしn,mは0以上29以下の整数であり、n < m)。
n * 2 / 30 = a 余り b
m * 2 / 30 = c 余り d
とします(n,mの変域より、a,cは0か1。ただし、n < m より a ≦ c。また、両式ともに割られる数・割る数が偶数であるので、b,dは0以上28以下の偶数)。
ここで、nとmが検証の際に衝突してしまうとき、
a + b = c + d  ……【式X】
が成立するはずですので、この式が成立すると『仮定して』話を進めます。
前述の通りa,cは0か1となりますが、a = cとなる場合、b = d となり、n = m となってしまい定義である n < m に反しますので不適となります。
つまり a = 0, c = 1 の場合のみ考えればよいことになります。
このとき、【式X】より
b = 1 + d
となります……ん?

先ほどb,dはともに偶数であると確認したはずですが、これでは必ずどっちかは奇数になってしまいますね。ということは、仮定に問題があったことになります。つまり【式X】が成り立つと仮定したことが間違いだったってことです(所謂「背理法」)。つまり検証付文字列の偶数番目を検証する際、衝突が生じないことになります。なので新人さんの直感通り、おそらくは文字列に誤りがあれば偶数番目・奇数番目問わず検出されます!多分!
(冒頭に述べさせていただいた通り、自信はかなーりないです。どこかに穴があるかもしれないし、結論が合っているにしてももっとスマートな証明方法がありそうな気がする……)

☆実際に問題を解く際の方針
……と、言うわけで、試験中こんなこと確認してる暇はもちろんないので、ここまで厳密に調べなくていいでしょう。しかしまあ、設問2を正解できていれば、確認すべきは表4のケースのうち2と4だけですし、大した計算量でもないので、計算すべきかなとは思います。ただ、時間がなければ新人さんのように直感で解くというのも一つの手段とは思います。本番だったらそれでよいでしょう(ただし、練習の際には時間を使って解く訓練もしたほうがいいようにも思います。最悪トレースでゴリ押せば絶対解けるぜ!という自信があると本番時のメンタルが安定しやすいですし、解法は何種類持っていても邪魔になることはないので)。
2021.02.18 13:14
いいね正解大卒さん 
FE ブロンズマイスター
(No.3)
☆補足
上記はあくまで問題文中図1のような文字列の中の誤りが1文字のみであることを前提にお話しさせていただいています。2文字以上の誤りがあった場合は検出できないこともあると思います。
2021.02.18 13:19
新人さん  
(No.4)
証明までしていただいてありがとうございます・・・!
証明すべて理解できたとは言えませんが解く際の方針は決められました。
ありがとうございます!
2021.02.18 13:45

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。

その他のスレッド


Pagetop