KOEI的旅行

使用BNF(Backus Naur Form)文法，產生二進位數字，其值為3的倍數。第一次看到這題是95年高考程式語言的題目，答案如下:

<N3> ::=   <N3>0 | <N1>1 | 0 
<N1> ::= <N2>0 | <N3>1 | 1 
<N2> ::= <N1>0 | <N2>1 

解了好久，最後求助Google大神，才能有系統解出。

以3為基準來表示數字，會有三種數字 3n、3n+1、3n+2，也就是3的倍數、3的倍數+1、3的倍數+2，共3種。

以<3n>、<3n+1>、<3n+2>表示這三種數字的集合。

<3n>  (3的倍數)  如果為1位數時  <3n>::=0。

<3n>不只1位數時，假設<3n>::=  <A>0  |  <B>1，<A>、 <B>為<3n>、<3n+1>、<3n+2>其中之1。

求<A>*2+0 、<B>*2+1 為三的倍數時，<A>、 <B>的值?

得<3n>*2、<3n+1>*2+1 為三的倍數，即<3n>::= <3n>0  |  <3n+1>1。

綜合兩項得<3n>::= <3n>0  |  <3n+1>1 | 0

再來求<3n+1>  (3的倍數+1)

<3n+1>如果為1位數時 <3n+1>::=1。

<3n+1>不只1位數時，假設<3n+1>::=  <C>0  |  <D>1，

求<C>*2+0 、<D>*2+1為3的倍數+1時，<C>、 <D>的值?

得<3n+2>*2+0 、 <3n>*2+1為3的倍數+1，即<3n+1>::= <3n+2>0  |  <3n>1。

綜合兩項得<3n+1>::= <3n+2>0  |  <3n>1 | 1

最後求<3n+2>   (3的倍數+2)

<3n+2>為1位數時無解，故假設<3n+2>::=  <E>0  |  <F>1，

求<E>*2+0、<F>*2+1 為3的倍數+2時，<E>、 <F>的值?

得<3n+1>*2、 <3n+2>*2+1 為3的倍數+2，即<3n+2>::= <3n+1>0  |  <3n+2>1

令<N3>= <3n>、<N1>=<3n+1>、<N2>=<3n+2>，即可求得答案。