題目如下：
如果一個二進制數包含連續的兩個1，我們就稱這個二進制數是非法的。
找出在所有 n 位二進制數（一共有2^n個）中，非法二進制數有多少個。
例如對于 n = 3,有 011, 110, 111 三個非法二進制數。
由于結果可能很大，你只需要輸出模10^9+7的余數。
輸入 一個整數 n (1 ≤ n ≤ 100)。
輸出 n 位非法二進制數的數目模10^9+7的余數。
樣例輸入：3
樣例輸出：3
解題思路： 這一題很容易讓人不知所措。。。讓我們來合理分析，抽象一下問題。問題結果抽象為S（n），即在n位內，存在多少非法二進制數。由于二進制位只有1，0兩種結果，并目前數據規模假設為n，那么內部問題結果抽象為B（n，1）與B（n，0），即在第n位為1或0時n位內，存在多少非法二進制數。從而理性得出，S（n）=B（n，1）+B（n，0）。
繼續分析，B（n，1）如何得出？試想一下，第n位為1時，如何保證其為非法二進制呢？很簡單，n-1位為1時，肯定保證了兩位連續的1存在。因此所有n-1位為1的數在這情況下都是非法二進制，我們抽象結果為A（n-1），意為在n-1位內第n-1位為1的所有二進制數個數。那么n-1位為0時呢？這不難得出相等于B（n-1，0）的結果吧。因此得出等式B（n，1）=B（n-1，0）+A（n-1）。
然而，相比于B（n，1），B（n，0）顯得容易許多，稍微推導即得B（n，0）=B（n-1，1）+B（n-1，0）。
最后，A（n）又如何得出呢？我們來總結一下規律，假設n=2，A（2）即從10到11的個數，因此為（2^0 + 2^1）-2^1+1=2。n=3時，A（3）為100到111的個數，即（2^2+2^1+2^0）-2^2+1=4。n=4時，A（4）為1000到1111的個數，即（2^3+2^2+2^1+2^0）-2^3+1=8。好了，從以上式子得出A（n）=A（n-1）+2^(n-1)。
綜合上述，我們得出了以下一系列方程： S（n）=B（n，1）+B（n，0） B（n，1）=B（n-1，0）+A（n-1） B（n，0）=B（n-1，1）+B（n-1，0） A（n）=A（n-1）+2^(n-1)
從方程可以看出，n規模數據結果是由n-1規模數據得出，因此從低到n規模遞推數據結果即可解決。
思路代碼實現如下：
int Method(int n){ int **matrix=new int *[n]; for(int i=0;i<n;++i) matrix[i]=new int[3], ZeroMemory(matrix[i],12); matrix[0][2]=1; for(int i=1;i<n;++i) { matrix[i][0]=matrix[i-1][1]+matrix[i-1][2]; matrix[i][1]=matrix[i-1][0]+matrix[i-1][1]; matrix[i][2]=pow(2,i-1)+matrix[i-1][2]; } int res=matrix[n-1][0]+matrix[n-1][1]; for(int i=0;i<n;++i) delete[] matrix[i]; delete[] matrix; return res%1000000007;}新聞熱點
疑難解答
