布置会场(I)

NC14345. 布置会场(I)

描述

今天是Tabris和mengxiang000来到幼儿园的第3天，mengxiang000接到了一个布置会场的任务。
他需要将贵宾观众席的椅子排成一排，一共需要N个。
幼儿园只有两种椅子，所以他也只能使用两种椅子。（A类型和B类型）并且假设每种椅子的数量都是无限的。
而其如果想要摆置一个B类型的椅子，对应就需要必须有连续两个一起布置。换句话说，就是如果出现了B类型的椅子，其必须且只有两个连着B类型的椅子。
mengxiang000突然想知道对应N个椅子排成一列，他能够有多少种布置的方式.

输入描述

本题包含多组输入第一行输入一个整数t，表示测试数据的组数
每组测试数据包含一行，输入一个整数N，表示一共需要摆放的椅子数量
t<=30
1<=N<=30

输出描述

每组测试数据输出包含一行，表示一共有多少种布置的方式。

示例1

输入:

2
2
4

输出:

2
5

说明:

第一个样例，AA，BB两种方案。
第二个样例，AAAA,BBBB,AABB,ABBA,BBAA五种方案对于ABBB 因为有连续3个B类型椅子所以不可行

上次编辑到这里，代码来自缓存点击恢复默认模板

C(clang 3.9) 解法, 执行用时: 2ms, 内存消耗: 308K, 提交时间: 2020-07-26 12:52:54

# include <stdio.h>

int main(){
	int n,m,j[31]={1,1,2},i=3;
	for(;i<31;i++){
 	    j[i]=j[i-2]+j[i-1];
	}
	scanf("%d",&n);
	while(n--){
		scanf("%d",&m);
		printf("%d\n",j[m]);
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 476K, 提交时间: 2019-03-18 16:06:47

#include<cstdio>
int n,f[35],t;
int main(){
	f[0]=1;
	for(int i=1;i<=30;i++)f[i]=f[i-1]+f[i-2];
	for(scanf("%d",&t);t;t--){
		scanf("%d",&n);
		printf("%d\n",f[n]);
	}
}

Python3 解法, 执行用时: 41ms, 内存消耗: 6912K, 提交时间: 2021-12-14 22:17:59

n=int(input())
dp=[0]*31
dp[1],dp[2]=1,2
for i in range(3,31):
    dp[i]=dp[i-1]+dp[i-2]
while n:
    t=int(input())
    print(dp[t])
    n-=1