1. 问题提出
一场球赛开始前，售票工作正在紧张的进行中。每张球票为50元，现有30个人排队等待购票，其中有20个人手持50元的钞票，另外10个人手持100元的钞票。假设开始售票时售票处没有零钱，求出这30个人排队购票，使售
票处不至出现找不开钱的局面的不同排队种数。（约定：拿同样面值钞票的人对换位置后为同一种排队。）
2．递归设计要点
我们考虑一般情形：有m+n个人排队等待购票，其中有m 个人手持50元的钞票，另外n个人手持100元的钞票。求出这m+n个人排队购票，使售票处不至出现找不开钱的局面的不同排队种数（这里正整数m，n从键盘输入）。
这是一道典型的组合计数问题，考虑用递推求解。
令f(m,n)表示有m个人手持50元的钞票，n个人手持100元的钞票时共有的方案总数。我们分情况来讨论这个问题。
(1) n=0
n=0意味着排队购票的所有人手中拿的都是50元的钱币，注意到拿同样面值钞票的人对换位置后为同一种排队，那么这m个人的排队总数为1，即f(m,0)=1。
(2）m<n
当m<n时，即排队购票的人中持50元的人数小于持100元的钞票，即使把m张50元的钞票都找出去，仍会出现找不开钱的局面，所以这时排队总数为0，即f(m,n)=0。
(3）其它情况
我们思考m+n个人排队购票，第m+n个人站在第m+n-1个人的后面，则第m+n个人的排队方式可由下列两种情况获得：
1） 第m+n个人手持100元的钞票，则在他之前的m+n-1个人中有m个人手持50元的钞票，有n-1个人手持100元的钞票，此种情况共有f(m,n-1)。
2） 第m+n个人手持50元的钞票，则在他之前的m+n-1个人中有m-1个人手持50元的钞票，有n个人手持100元的钞票，此种情况共有f(m-1,n)。
由加法原理得到f(m,n)的递推关系：
f(m,n)=f(m,n-1)+f(m-1,n)
初始条件：
当m<n时，f(m,n)=0
当n=0时，f(m,n)=1
package basic_practice;
import java.util.Scanner;
public class anlian_bfs {
static long f(int m,int n){
long y ;
if(n==0)y=1;
else if(m<n)y=0; //确定初始条件
else y=f(m-1,n)+f(m,n-1); //实施递归
return y;
}
public static void main(String[] args) {
int m,n;
Scanner in=new Scanner(System.in);
m=in.nextInt();
n=in.nextInt();
System.out.println(f(m,n));
}
}