01串

時間限制：1000 ms  |  內(nèi)存限制：65535 KB

難度：2

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

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

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

樣例輸出35

import java.util.Scanner;

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

}