ACM训练【排队买票】 （C语言描述 递归 5ms 过 简单易懂）--------C语言——菜鸟级

/*问题 1163: 【排队买票】
时间限制: 1Sec 内存限制: 128MB 提交: 145 解决: 70

题目描述
有M个小孩到公园玩，门票是1元。其中N个小孩带的钱为1元，K个小孩带的钱为2元。
售票员没有零钱，问这些小孩共有多少种排队方法，使得售票员总能找得开零钱。
注意：两个拿一元零钱的小孩，他们的位置互换，也算是一种新的排法。（M<=10）

输入
输入一行，M,N,K(其中M=N+K,M<=10).

输出
输出一行，总的排队方案。

样例输入
4 2 2
样例输出
8

思路： 比较简单 先不管 排不排序 先把 满足条件的 情况通过递归得到数目
再针对 1 元的小朋友 和 2 元的小朋友 分别 进行内部全排 （即求 n! 和 k!)
比如样例 4 2 2
dg() 得到 2（1122 1212） 种情况 再乘以 1的内部全排（2！=2） 2的内部全排（2！=2）
sum=sum* jc(n)jc(k) sum=22*2=8
*/

#include <stdio.h>
long int jc(int m)//求阶乘 
{ long int sum=1,i;
  for(i=2;i<=m;i++)
   sum*=i;
   return sum;
}
long int dg(int lq,int sy1,int sy2)
{    //lq售票员零钱数 sy1 1元小朋友剩余量 sy2 2元小朋友剩余量
  //   if(lq<0||sy1==0&&sy2>lq)return 0;// lq售票员零钱数为零或 
	 //上面这句完全多余     // 1元为零并且票员零钱数小于2元小朋友剩余量 则此排法无效 
	 if(sy2==0||sy1==0) return 1;//如果前面情况未出现 某个剩余量为 零 后面不用考虑 则返回 1 
	 if(lq==0) return dg(lq+1,sy1-1,sy2);//如果售票员没零钱了 只能 一元小朋友排在这一位  
	 return dg(lq+1,sy1-1,sy2)+dg(lq-1,sy1,sy2-1);//两种情况 要么当前排1元的要么排2元 
}
int main()
{int n,m,k;long int sum;
 scanf("%d%d%d",&m,&n,&k);//1元小于 2元 则零 情况 
 if(n<k)printf("0\n");
 else
 {
 sum=dg(1,n-1,k);//首位必须 为 1元 
 sum=sum*jc(n)*jc(k);
 printf("%ld\n",sum);
 }
return 0;
}

  

 

  
 
 

  
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
 

纠错： 其实第10行完全多余了 首先“lq<0 xss=removed xss=removed>lq”
第19行就决定了不会发生这种情况（保证了1元小朋友>=2元小朋友，所所以1元小朋友若先排完 是lq 是不可能小于2元小朋友剩余数的） 综上
第10 行 语句 是我的思维重叠部分 。 不好意意思 误导了误导了 ~~~尴尬 dg() 函数只需这样就行了

文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。

原文链接：fivecc.blog.csdn.net/article/details/80040802