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