递归求解排队进电影院问题，附带 JAVA 代码 | 珊瑚贝

原题：

1
2
3
4

有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) 表示 4×3=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 代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

/*
 * 排队问题求解
 */
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 的值来计算.