01串

時間限制：1000 ms  |  內存限制：65535 KB

難度：2

描述 ACM的zyc在研究01串，他知道某一01串的長度，但他想知道不含有“11”子串的這種長度的01串共有多少個，他希望你能幫幫他。

注：01串的長度為2時,有3種：00，01，10。

輸入第一行有一個整數n（0<n<=100）,表示有n組測試數據;隨后有n行，每行有一個整數m(2<=m<=40)，表示01串的長度;輸出輸出不含有“11”子串的這種長度的01串共有多少個，占一行。樣例輸入223

樣例輸出35

import java.util.Scanner;

/* * 01串 * 思路：看到此題想到可以利用遞歸嘗試每種可能, 排除11連用的情況。 * 稍微思考想到字串長度為8的一定和4的有關系，只要處理好2個字串為4的相連接的可能就可以了。即二分算法。 * 思考：其實還可以采用遞增的方法如果原來字串是0結尾，則新添加的可以使1或0，否則為0 * 給予這樣的思路得出數據如下 * 長度 種類  0結尾個數    公式 *  1  2    1    2+1=3 *  2  3    2    3+2=4   *  3  5  5-2=3(種類數)  *  解釋：長度為2時有2個0所以長度為3這里必有2個1 *  有長度為為3時種類數等于長度為2時的種類數加上0結尾的個數 和長度為3是推出的0結尾個數推出 *  長度為n的種類=長度為n-1的種類+長度為n-2的種類 *  此時大家看到這其實是一個斐波那契數列 *  針對此題我們看到數據大小m為2<=m<=40可以采用先算法放到數組中的方法節約時間 */public class Main {

 public static void main(String[] args) {  Scanner sc = new Scanner(System.in);  int n;  int ary[] = new int[41];  ary[2] = 3;  ary[3] = 5;  for (int i = 4; i < ary.length; i++) {   ary[i]=ary[i-1]+ary[i-2];  }  n=sc.nextInt();  while(n-->0){   System.out.PRintln(ary[sc.nextInt()]);  } }

}