01串

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

難度：2

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

注：01串的長(zhǎng)度為2時(shí),有3種：00，01，10。

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

樣例輸出35

import java.util.Scanner;

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

}