使用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>,即可求得答案。

 

 

 

 

 

arrow
arrow
    文章標籤
    BNF 3的倍數
    全站熱搜

    KOEI 發表在 痞客邦 留言(1) 人氣()