Children’s Queue

Click me~
Problem Description 

PHT学校有许多学生。有一天,猪头饼校长要求所有学生站成一条线。他规定,女孩不能形单影只。换句话说,队列中要么没有女孩，要么有不止一个女孩并排站着。4个孩子排队的情况如下：FFFM,MFFF,FFMM,MFFM MMFF,共有7种情况，这里F代表female,M代表male。现在，要求写一个程序求n个孩子共有多少种排队情况。

 
 

  
  Input 
 
 
 
 

  
  测试用例有多个，每个测试用例只有一个数字n表示孩子的个数，处理到文件结束符表示输入结束。
 
 
 
 

  
  Output 
 
 
 
 

  
  对于每个测试用例，输出满足条件的排队情况总数。
 
 
 
 

  
  Sample Input 
 
 
 
 

  
  1
 
 
 
 

  
  2
 
 
 
 

  
  3
 
 
 
 

  
  Sample Output 
 
 
 
 

  
  1
 
 
 
 

  
  2
 
 
 
 

  
  4
 
 

解释：
 
 

  
  
  
  
设：F(n)表示n个人的合法队列，则：
  
  
 按照最后一个人的性别分析，他要么是男，要么是女，所以可以分两大类讨论：
  
  
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). 
 
 
 
 

  
   
 
 
 
 

  
  结论：
 
 
 
 

  
   所以，通过以上的分析，可以得到递推的通项公式： F(n)=F(n-1)+F(n-2)+F(n-4) ? (n>3)
 
 
 
 

  
  然后就是对n<=3 的一些特殊情况的处理了，显然：F(0)=1 ? (没有人也是合法的，这个可以特殊处理，就像0的阶乘定义为1一样),F(1)=1,F(2)=2,F(3)=4
 
 

可以用C++的大数add()，也可以直接用java的大数类。c++的add见其它博文，这里用一下蹩脚的java.

import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
	public static void main(String []args)
	{
		Scanner cin = new Scanner(System.in);
		Integer N = 1001,i;
		BigInteger[] f = new BigInteger[N];
		f[1] = BigInteger.valueOf(1);
		f[2] = BigInteger.valueOf(2);
		f[3] = BigInteger.valueOf(4);
		f[4] = BigInteger.valueOf(7);
		for ( i = 5; i < N; ++i)
		{
			f[i] = f[i-1].add(f[i-2]).add(f[i-4]);
		}
		while(cin.hasNext())
		{
			i = cin.nextInt();
			System.out.println(f[i]);
		}
	}
}