java算法-01串(斐波那契数列)

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()]);  } }

}