递归求解排队进电影院问题,附带JAVA代码

原题：

有2n个人排队进电影院，票价是50美分。在这2n个人当中，其中n个人只有50美分，另外n个人有1美元（纸票子）。愚蠢的电影院开始卖票时1分钱也没有。
问： 有多少种排队方法 使得 每当一个拥有1美元买票时，电影院都有50美分找钱
注： 1美元=100美分
拥有1美元的人，拥有的是纸币，没法破成2个50美分

解题方法：

此题可以用递归方式求解，详细求解过程如下：

符合条件的情况必须是拥有1美元的人前方必须要有50美分的人来排队，要不然不可能找零开，即必须满足从头数50美分的人数大于1美元的人数.

我们直接求解符合条件的情况.我们先不考虑持有50美分的人的次序,仅考虑持有1美元的人的次序，最后的结果再乘以n! 就可以了.

可以转化为50美分的人已经排好,由持有1美元的人进行插空排列.

首先1美元的人是不可能插到队头的，所以可以插的空有n个.

定义一个函数f(n.m),这表示有n个1美元的人插m个空的方法数,这m个空是从队尾向前数的m个空的位置.

比如f(4,4)的求解

●1●2●3●4 黑点表示50美分的人,1234表示可以插的空

第一个空可以有0人,可以有1个人.但不可能有2个人及以上

1.当有1人的时候,这个位置4个人四选一,剩下的方式为f(3,3),故为4*f(3,3)

2.当没有的人的时候,则方式为f(4,3)

所以排列方式为f(4,4)=4f(3,3)+f(4,3)=A(4)(0)f(4,3)+A(4)(1)*f(3,3)

注:A(m)(n)在此表示m!/(m-n)! 如A(4)(2)表示4x3=12.A(5)(3)表示5x4x3=60.

再如:f(4,3)的求解

是四个人插后三个空,

● ●1●2●3 黑点表示50美分的人,123表示可以插的空

第一个空可以没人,可以1个人,可以2个人,但不能有3人及以上.

1.当有0人的时候,则只有四个人插后两个空了,即为f(4,2)

2.当有1人的时候,选其中1人,四选一,剩下的3人插2个空,方法数为4*f(3,2)

3.当有2人的时候,选其中的2人，四选二排列,剩下的2人插两个空,方法数为A(4)(2)*f(2,2)

所以排列方式为f(4,3)=f(4,2)+4f(3,2)+A(4)(2)f(2,2)=A(4)(0)f(4,2)+A(4)(1)f(3,2)+A(4,2)*f(2,2)

发现规律了吗?在此我们可以总结出递推式

所以最后的结果就简单了,我们再乘上50美分的人的全排列就是最后的结果了.

最后的答案即为A(n)(n)*f(n,n)

JAVA代码实现如下:

/*
 * 排队问题求解
 */
import java.math.*;
public class Solve {
   public static void main(String[] args) {
	 //n的值
	  int n =7;
	//求得结果
	 System.out.println(getNumber(n,n).multiply(getResult(n,n)));
}
      //即为f(n,m)函数实现
   static BigInteger getNumber(int n,int m){
	  //当m=1返回Ann即n!
        if(m==1) return getResult(n,n);
      //初始化result=0
        BigInteger result =new BigInteger("0");
		for(int i=0;i<=n-m+1;i++){
			//利用递归式子求解
			result=result.add((getResult(n,i)).multiply(getNumber(n-i,m-1)));
		}
		return result;
   }
   static BigInteger getResult(int m,int n){
	   //求Amn
	   BigInteger result =new BigInteger("1");
	   int count=0;
	   //如果n为0,返回Am0即为1
	   if(n==0) return new BigInteger("1");
	   for(int i=m;;i--){
		   result =result.multiply(new BigInteger(""+i));
		   count++;
		   if(count==n) break;
	   }
	   return result;
   }
}

利用了BigInteger求解,防止越界的出现.在main函数里可以修改n的值来计算.