用最朴素的方法打出前三十组数据，发现是fibonacci数列，直接水过。
此外还可以用排列组合的方法。n=3时，由插空法得C(4,0)+C(3,1)+C(2,2); n=k时则是sigma C(k-i+1,i) (i=0..(k+1)/2)
Problem
Given a positive integer n, determine the number of different chanting patterns of this length, i.e., determine the number of n-bit sequences that contain no adjacent 1's. For example, for n = 3 the answer is 5 (sequences 000, 001, 010, 100, 101 are acceptable
while 011, 110, 111 are not).
Input
The first line contains the number of scenarios.
For each scenario, you are given a single positive integer less than 45 on a line by itself.
For each scenario, you are given a single positive integer less than 45 on a line by itself.
Output
The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the number of n-bit sequences which have no adjacent 1's. Terminate
the output for the scenario with a blank line.
the output for the scenario with a blank line.
Sample Input
2 3 1
Sample Output
Scenario #1: 5 Scenario #2: 2
#include <stdio.h>
int sum;
int a[50];
__int64 f[50];
int fun(int n,int k){
if (k>n) {
sum++;
return sum;
}
else{
a[k]=0;
fun(n,k+1);
if (a[k-1]==0){
a[k]=1;
fun(n,k+1);
}
return sum;
}
}
int main(){
int i;
f[1]=2;f[2]=3;
for (i=3;i<=49;i++){
f[i]=f[i-1]+f[i-2];
}
/* for (int i=1;i<=30;i++){
sum=0;
printf("n=%d sum =%d\n",i,fun(i,1));
printf("n=%d fibo=%d\n",i,f[i]);
}*/
int n,x;
scanf("%d",&n);
for (i=1;i<=n;i++){
scanf("%d",&x);
printf("Scenario #%d:\n",i);
printf("%lld\n\n",f[x]);
}
return 0;
}