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串共有多少个，占一行。 样例输入

2 2 3样例输出

3 5

看这个题目难度不高，也就没多想。手动推出了，m=4，和m=5 的数据，感觉可能是类似于斐波那契数列的求法，也就是当m大于2时，他的数量就是前两个之和。没想到还真的AC了。

#include<iostream>

using namespace std;

int a[50];

int main()

{

a[0]=0;

a[1]=2;

a[2]=3;

for(int i = 3; i <= 42; i ++)

a[i]=a[i-1]+a[i-2];

int t;

cin>>t;

while(t--)

{

int n;

cin>>n;

cout<<a[n]<<endl;

}

return 0;

}

打了个表。。。。

相关知识

斐波那契数列
斐波那契数列的各种求法（终于找全了！）
【数学文化】数学之美：花朵中的斐波那契数列
数列之花处处盛开——植物与数学
Fibonacci数列是这样定义的： F[0] = 0 F[1] = 1 for each i ≥ 2: F[i] = F[i
植物惊人的“数学天赋”
“美貌”与“美味”并存的植物——向日葵
美丽是可以表述的——描述花卉形态的数理方程
美丽是可以表述的——描述花卉形态的数理方程 | 《物理》50年精选文章
GuoSmallGuo23

原文链接: 01串（类似于斐波那契数列） https://www.huajiangbk.com/newsview353312.html

上一篇: 繁殖策略34.ppt

下一篇: 版纳君的相册