递推加大数
Problem Description
There are many students in PHT School. One day, the headmaster whose name is PigHeader wanted all students stand in a line. He prescribed that girl can not be in single. In other words, either no girl in the queue or more than one
girl stands side by side. The case n=4 (n is the number of children) is like
FFFF, FFFM, MFFF, FFMM, MFFM, MMFF, MMMM
Here F stands for a girl and M stands for a boy. The total number of queue satisfied the headmaster’s needs is 7. Can you make a program to find the total number of queue with n children?
girl stands side by side. The case n=4 (n is the number of children) is like
FFFF, FFFM, MFFF, FFMM, MFFM, MMFF, MMMM
Here F stands for a girl and M stands for a boy. The total number of queue satisfied the headmaster’s needs is 7. Can you make a program to find the total number of queue with n children?
Input
There are multiple cases in this problem and ended by the EOF. In each case, there is only one integer n means the number of children (1<=n<=1000)
Output
For each test case, there is only one integer means the number of queue satisfied the headmaster’s needs.
Sample Input
1 2 3
Sample Output
1
2
4
分析如下：
按照最后一个人的性别分析，他要么是男，要么是女，所以可以分两大类讨论：
1、如果n个人的合法队列的最后一个人是男，则对前面n-1个人的队列没有任何限制，他只要站在最后即可，所以，这种情况一共有F(n-1);
2、如果n个人的合法队列的最后一个人是女，则要求队列的第n-1个人务必也是女生，这就是说，限定了最后两个人必须都是女生，这又可以分两种情况：
2.1、如果队列的前n-2个人是合法的队列，则显然后面再加两个女生，也一定是合法的，这种情况有F(n-2);
2.2、但是，难点在于，即使前面n-2个人不是合法的队列，加上两个女生也有可能是合法的，当然，这种长度为n-2的不合法队列，不合法的地方必须是尾巴，就是说，这里说的长度是n-2的不合法串的形式必须是“F(n-4)+男+女”，这种情况一共有F(n-4).
再则就是大数处理，代码如下：
#include<iostream>
#include<cstdio>
using namespace std;
char a[1001][401];
int int1[401],int2[401],int3[401];
int sum[401];
void ds(int w)
{
int x=strlen(a[w-1]),y=strlen(a[w-2]),z=strlen(a[w-4]),i,j,k,m,maxx;
for(i=0;i<=400;i++)
{
sum[i]=0;
int1[i]=0;
int2[i]=0;
int3[i]=0;
}
m=0;
for(i=x-1;i>=0;i--)
{
int1[m++]=a[w-1][i]-'0';
}
m=0;
for(i=y-1;i>=0;i--)
{
int2[m++]=a[w-2][i]-'0';
}
m=0;
for(i=z-1;i>=0;i--)
{
int3[m++]=a[w-4][i]-'0';
}
maxx=x+y+z;
for(i=0;i<=maxx+1;i++)
{
sum[i]+=(int1[i]+int2[i]+int3[i]);
if(sum[i]>=10)
//注意这里处理的时候因为是三个数相加，所以不是sum[i]-=10,sum[i]的结果大于0小于27
{
int p=sum[i]/10;
sum[i]%=10;
sum[i+1]+=p;
}
}
int u;
for(j=400;j>=0;j--)
{
if(sum[j]!=0)
{
u=j;break;
}
}
m=0;
for(k=u;k>=0;k--)
{
a[w][m++]=sum[k]+'0';
}
return;
}
int main()
{
int n,w;
a[0][0]='1';a[1][0]='1';a[2][0]='2';a[3][0]='4';
for(w=4;w<=1001;w++)
{
ds(w);
}
while(scanf("%d",&n)!=EOF)
{
printf("%s\n",a[n]);
}
return 0;
}