解题思路:
N+K 个人排队买票,N个持有1元,M个人持有2元,那么每一个持有2元的人必有一个持有1元的人与之配对。
那这个问题就是个配对问题,配对问题正好用卡特兰数。
参考:
https://zh.wikipedia.org/wiki/卡塔兰数
http://www.cnblogs.com/wuyuegb2312/p/3016878.html#suggestion
https://blog.csdn.net/doc_sgl/article/details/8880468
注意事项:
卡特兰数本身是组合计数,本题有个特殊要求是要排序,因此乘以 N 与 K 的全排列数,即阶乘的个数。
参考代码:
#include <stdio.h>
#define N 10
long fIter(int n)
{
long result = 1;
while(n > 1)
{
result *= n;
n--;
}
return result;
}
long catalan(int n, int m)
{
long count;
long mid;
mid = fIter(n+m);
count = (mid/(fIter(n)*fIter(m)) - mid/(fIter(n+1)*fIter(m-1)))*(fIter(n)*(fIter(m)));
return count;
}
int main()
{
int n,m,k;
long count;
while((scanf("%d%d%d",&m,&n,&k))==3)
{
count = catalan(n,k);
printf("%d\n",count);
}
return 0;
}
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:1054 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:732 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:523 |
C语言程序设计教程(第三版)课后习题9.4 (Java代码)浏览:1424 |
ASCII帮了大忙浏览:758 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:643 |
C语言程序设计教程(第三版)课后习题7.1 (C语言代码)浏览:523 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:577 |
WU-输出九九乘法表 (C++代码)浏览:1688 |
WU-拆分位数 (C++代码)浏览:791 |