Children’s Queue

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 5687 Accepted Submission(s): 1764

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?

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 

【大数的输出花费了好久时间。】

/* 题目大意：n个孩子站成一排，要求至少两个女孩站在一起。（男孩、女孩足够多），求有多少种站法。 假设n-1个孩子已经站好了，现在第n个孩子过去。 如果第n个孩子是男孩：则有f(n-1)种站法 如果第n个孩子是女孩，那么第n-1个也必须是女孩： 如果前n-2个孩子是合法的，那么就有f(n-2)种站法 如果前n-2个孩子是不合法的，但是加上最后两个女孩就是合法的了，那么有f(n-4)种站法。 n    f 0    1 1    1 2    2 3    4 4    7 ----- n可能为1000哦~所以要用大数。 */ #include 
     
       #include 
      
        #define N 100 #define M 100000 long a[1001][N]; void Add(long *a,long *b,long *c)//c = a + b {
   int i; long carry; carry = 0L; for (i=N-1;i>=0;i--) {
   c[i]=a[i]+b[i]+carry; carry = 0L; if (c[i]>=M) {
   c[i]-=M; carry=1L; } } } void output(long *a) {
   int i=0; while(a[i] == 0L) i++; printf("%ld",a[i++]);//注意大数的输出格式。     while (i!=N) {
   //注意a[i]小于M-1的位数的情况         printf("%05ld",a[i++]); } printf("\n"); } int main() {
   int n,i; long temp[N]; memset(a,0L,sizeof(a)); a[0][N-1]=1; a[1][N-1]=1; a[2][N-1]=2; a[3][N-1]=4; for (i=4;i<=1000;i++) {
   if (i==50) {
   i=50; } memset(temp,0L,sizeof(temp)); Add(a[i-1],a[i-2],temp); Add(temp,a[i-4],a[i]); } while (scanf("%d",&n)!=EOF) {
   output(a[n]); } return 0; }

本文转自ZH奶酪博客园博客，原文链接：http://www.cnblogs.com/CheeseZH/archive/2012/04/05/2433422.html，如需转载请自行联系原作者