応用情報技術者平成29年秋期 午前問2

まきさん  
(No.1)
ア  123
    123→<R1><R2><R0>
  イ  124
    124→<R1><R2><R1>
  ウ 127
    127→<R1><R2><R1>
  エ 128
    128→<R1><R2><R2>

という解説は分かりましたがこの問題を早解きをするにはどうすればどうすればよろしいでしょうか。解説お願いいたします。
2024.02.22 20:47
jjon-comさん 
AP プラチナマイスター
(No.2)
このサイトの検索欄で「BNF」をキーワード検索したところ
次の書き込みがヒットしました。
https://www.ap-siken.com/bbs/1929.html
https://www.ap-siken.com/bbs/4347.html
2024.02.22 21:31
まきさん 
(No.3)
>jjon-comさん
解説ありがとうございました。参考にします
2024.02.23 09:09
boyonboyonさん 
AP シルバーマイスター
(No.4)
この問題興味を持ったので考えてみました。

○考えた結果
<R*><R*><R*>から<A><B><C>を使った表記に戻していったらできました。
例えば、
エ   128→<R1><R2><R2>
を戻していきます。
<R1>  <R2><R2>
↓  <R1>になるのは、<B>なので
<B>  <R2><R2>

<B><R2>  <R2>
↓  <B><R2>があるのは、<A>なので置き換えて
<A>  <R2>
↓  <A><R2>があるのは、<C>なので置き換えて
<C>

同様に、
ア・・・<A><R0>→<A>
イ・・・<A><R1>→<B>
ウ・・・<A><R1>→<B>
答えは、アになります。
アから始めれば、早解きできると思います。

余談・・・
ついでに、<R*><R*><R*>全部調べてみました。
<R0><R0><R0>→<A>
<R0><R1><R2>→<A>
<R0><R2><R1>→<A>
<R1><R0><R2>→<A>
<R1><R1><R1>→<A>
<R1><R2><R0>→<A>
<R2><R0><R1>→<A>
<R2><R1><R0>→<A>
<R2><R2><R2>→<A>
3つ同じか、3つとも違う<R*>。
<R0><R0><R1>→<B>
<R0><R1><R0>→<B>
<R0><R2><R2>→<B>
<R1><R0><R0>→<B>
<R1><R1><R2>→<B>
<R1><R2><R1>→<B>
<R2><R0><R2>→<B>
<R2><R1><R1>→<B>
<R2><R2><R0>→<B>
2つが同じ<R*>
<R0><R0><R2>→<C>
<R0><R1><R1>→<C>
<R0><R2><R0>→<C>
<R1><R0><R1>→<C>
<R1><R1><R0>→<C>
<R1><R2><R2>→<C>
<R2><R0><R0>→<C>
<R2><R1><R2>→<C>
<R2><R2><R1>→<C>
2つが同じ<R*>
という結果でした。ちょっと規則っぽいものがあっておもしろかったです。
2024.02.23 16:38
まきさん 
(No.5)
>boyonboyonさん
いつも解説ありがとうございます
あまりBNFを知らずいたので参考になりました
2024.02.23 18:33
jjon-comさん 
AP プラチナマイスター
(No.6)
応用情報 平成29年 秋期 午前 問2
https://www.ap-siken.com/kakomon/29_aki/q2.html

No.4は、問題文の定義を(当然のものとして?)明示していないので、異なる形で出題されたならそれを理解していない初心者は引っかかるんじゃないかな、と思いました。

この問題における、ある文字列の定義は次のようであり、
<A> ::= <R0>|<A> <R0>|<B> <R2>|<C> <R1>
<B> ::= <R1>|<A> <R1>|<B> <R0>|<C> <R2>
<C> ::= <R2>|<A> <R2>|<B> <R1>|<C> <R0>
「非終端定義の右側に終端記号を置いたもの」を新たな非終端定義としている。
これを優先順位を表すカッコ付けで表記するならばこうなります。
(((<R?>) <R?>) <R?>)

それに対して、もしも問題の定義が次のようなものであったなら、
<A> ::= <R0>|<R0> <A>|<R2> <B>|<R1> <C>
<B> ::= <R1>|<R1> <A>|<R0> <B>|<R2> <C>
<C> ::= <R2>|<R2> <A>|<R1> <B>|<R0> <C>
「非終端定義の左側に終端記号を置いたもの」を新たな非終端定義としている。
これを優先順位を表すカッコ付けで表記するならばこうなります。
(<R?> (<R?> (<R?>)))

ですから、No.4の「○考えた結果」の
> エ   128→<R1><R2><R2>
を、私なら
> エ   128→ (((<R1>) <R2>) <R2>)
とカッコ付けの表記にするでしょう。その後の作業はboyonboyonさんと同じです。
2024.02.24 00:22
boyonboyonさん 
AP シルバーマイスター
(No.7)
>jjon-comさん
こんにちは、いつもお世話になっています。

>No.4は、問題文の定義を(当然のものとして?)明示していないので、
おっしゃるとおりです。定義は前提条件のつもりで省略しました。掲示板だけ見たら誤解を与えるかもしれません。ご指摘ありがとうございます。
2024.02.24 09:07

返信投稿用フォーム

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

その他のスレッド


Pagetop