问题描述：
售票工作正在进行，每张票为50元，现在有m+n人排队等待购票，其中有m人手持50元，n人手持100元，假设售票处不设找零，那么若想使售票处不会出现找不开零钱的局面，请你帮忙设计不同的排队方案。特别说明的是，拿同样面值的人对换位置为同一种方案。
算法分析：
一：n=0; 那么说明买票的人都是手持50元，所以不会出现找不开零钱的局面，所以这是一种排队方案；
二：m=0; 那么说明买票的人都是手持100元，所以一定会找不开零钱，所以没有排队方案；
三：m<n; 那么说明买票的人中，手持50元的人数少于手持100元的人数，所以肯定会出现找不开零钱的局面，所以同样没有排队方案；
四：m>n; 此时，买票的人中，手持50元的人数多于手持100元的人数，所以可以有排队方案，我们这里来分析一下第m+n人的位置：
（1）：第（m+n）人手持100元站在第（m+n-1）人的后面，那么他之前的人有(m)人手持50元，有(n-1)人手持100元，此种情况共有f(m,n-1)种排队方式；
（1）：第（m+n）人手持50元站在第（m+n-1）人的后面，那么他之前的人有(m-1)人手持50元，有(n)人手持100元，此种情况共有f(m-1,n)种排队方式；
所以通过第（m+n）人就可以分析出递归关系为：f(m,n)=f(m-1,n)+f(m,n-1)
刚刚分析的边界条件： 当m<n时，f(m,n)=0; 当n=0时，f(m,n)=1; 当 m=0时，f(m,n)=0;
代码如下：
递归方法：
#include<iostream> using namespace std; long f(int i,int j){ long s; if(j==0){ s=1; } else if(i<j){ s=0; } else{ s=f(i-1,j)+f(i,j-1); } return (s); } int main(){ int m,n; cout<<"请输入m,n:"; cin>>m>>n; cout<<f(m,n); }
递推方法：
#include<iostream> using namespace std; int main(){ int i,j,m,n; long f[100][100]; cout<<"请输入m,n:"; cin>>m>>n; for(i=1;i<=m;i++){ f[i][0]=1; } for(i=0;i<=m;i++){ for(j=i+1;j<=n;j++){ f[i][j]=0; } } for(j=1;j<=n;j++){ for(i=j;i<=m;i++){ f[i][j]=f[i-1][j]+f[i][j-1]; } } cout<<f[m][n]<<endl; }
