找出沒有相鄰的1的二進制數的個數---2013年2月17日

   問題描述:用G(n)表示在有n位的二進制數中沒有相鄰的兩個1的二進制數個數。比如，當n=3時，000，001，010，011，100，101，110，111這8個數中隻有000,001,010,100,101這5個是沒有相鄰為1的，故G(3)=5。請寫一個程式，輸出G(n)的值。

      錯誤的思路(考慮的不周全):采用"分治"的方法，比如n=3，每次都将處理原問題規模的二分之一，直到n=1時，就很容易可以知道有兩種情況。前面是"分"，然後是"合"。比如把規模為n的問題分成了p1和p2部分，而且p1和p2問題都已經解決，個數已經知道。那麼，把p1和p2合起來的時候就隻需要注意p1的最右邊和p2的最左邊的數不能同時為1，即:合起來的總的個數是:1*(p2-1)+(p1-1)*p2。"遞歸"和"分治"不分家，是以很容易寫出下面的程式。

      以下是錯誤的代碼。

錯誤的代碼

       正确的思路:算法的核心思想不變，依然是"分治"。"分"的部分很好處理，"合"的時候就容易出錯了。我之前就是在合并的時候沒有考慮周全。依然是把規模為n的問題分成p1和p2部分,令div=n/2，那麼p1中有div個元素，p2中有n-div個元素。合并的時候，已經保證p1,p2部分分别都沒有相鄰的兩個1了，這時需要注意的就隻是p1的最右邊一個數和p2的最左邊的一個數了。分兩種情況(要用到排列組合的基礎知識):

       将p1中最右邊的數記為A，p2中最左邊的數記為B，友善下面的文字描述。

       1.A不為1。這種情況比下一種情況簡單一些。在p1中，A不為1，那麼A就是0了。這種情況下,G(div)=G(div-1)。再來考慮p2。既然A為0，那麼B即使為1也沒關系了。是以，這種情況下的結果就是G(div-1)*G(n-div)。

       2.A為1。因為A為1，那麼A左邊的第一個數必然為0(因為p1中沒有兩個相鄰的1)，是以在這種情況下G(div)=G(div-2)。再來考慮p2。既然A為1，那麼B肯定得為0了，那麼B右邊的數也就沒有限制了，即G(n-div-1)。是以，這種情況下的結果就是G(div-2)*G(n-div-1)。

       代碼如下:

       通過程式，可以得到G(1)=2,G(2)=3,G(3)=5,G(4)=8,G(5)=13,G(6)=21......可以看出這是一個斐波拉契數列。

本文轉自NeilHappy 51CTO部落格，原文連結：http://blog.51cto.com/neilhappy/1134394，如需轉載請自行聯系原作者