安科 OJ 1054 排队买票 （递归，排列组合）

概述    时间限制：1 s 空间限制：128 M 题目描述 有M个小孩到公园玩，门票是1元。其中N个小孩带的钱为1元，K个小孩带的钱为2元。售票员没有零钱，问这些小孩共有多少种排队方法，使得售票员总能找得开零钱。注意：两个拿一元零钱的小孩，他们的位置互换，也算是一种新的排法。（M<=10） 输入 输入一行，M,N,K(其中M=N+K,M<=10). 输出 输出一行，总的排队方案。 样例输入 4 2

 

 

时间限制：1 s

空间限制：128 M

题目描述

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

输入

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

输出

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

样例输入

4 2 2

样例输出

8

 

思路：思路挺简单的，先不管每个小孩的不一样，先算出来总共排列有多少种，再乘以 n 和 k 的阶乘就是答案了（乘以 n 和 k 的阶乘就是把 1 和 2 全排列），至于怎么算出来排列的种类，用递归算出来就可以了。

 

代码：

 1 #include <iostream> 2 #include <cstdio> 3  4 using namespace std; 5 int m,n,k,sum; 6  7 int fun(int ye,int nn,int kk)  // ye表示余额，nn表示1元小孩人数，kk表示2元剩余人数  8 { 9     if(ye < 0)  return 0;        //余额小于零，队列无效 10     if(!nn && !kk)  return 1;    //某个量排完，剩余位置只能排剩余的种类，因为这里n >= k 11                                  //保证剩下的排列合法，不会出现如：1 1 2 2 2 2 2 这种不合法的情况 12     if(!ye)  return fun(ye + 1,nn - 1,kk);  //余额为零，所以下一位只能排1元的位置 13     return (fun(ye + 1,kk) + fun(ye - 1,nn,kk - 1));  //每次每个位置能排 1 和 2 两种类型的位置 14 } 15 int main()16 {17     cin >> m >> n >> k;18     if(n < k)  cout << "0";  //1的数量比2少的话不可能出现合法序列 19     else20     {21         sum = fun(1,n - 1,k);  //保证第一位一定排1，不然队列不合法 22         int x1,x2;23         x1 = x2 = 1;24         for(int i = 1; i <= n; i ++ )   x1 *= i;25         26         for(int i = 1; i <= k; i ++ )   x2 *= i;27         28         sum = sum * x1 * x2;29         cout << sum;30     }31     return 0;32 }

 

PS：还有一种更快的算法，卡特兰数，百度出来的，呃，我也不太会，感兴趣的可以看下

总结

以上是内存溢出为你收集整理的安科 OJ 1054 排队买票 （递归，排列组合）全部内容，希望文章能够帮你解决安科 OJ 1054 排队买票 （递归，排列组合）所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。