新生晚会
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 14344 Accepted Submission(s): 4932
每组数据包含两个整数N（来报名的人数,1<=N<=30），M（节目需要的人数0<=M<=30）
5 3 2 5 3 4 4 3 6 8 0
3 10 1 0 1
问题链接：HDU2519 新生晚会。
题意简述：参见上文。
问题分析：这是一个经典的组合计算问题，是计算n中取m的组合数问题。
组合计算公式：C(n,m)=[n*(n-1)*.(n-m+1)]/m!=[n*(n-1)*.(n-m+1)]*(n-m)!/m!*(n-m)!=n!/[(n-m)!*m!]
其中C(n,m)=n!/(n-m)!*m!是众所周知的数学公式，然而用于程序计算并不十分有效。
原始的公式C(n,m)=[n*(n-1)*.(n-m+1)]/m!，用于程序计算是十分有效的。
即使使用long long数据类型，算阶乘时也会有溢出的时候。以下是阶乘的值（计算程序附后）：
0! 1
1! 1
2! 2
3! 6
4! 24
5! 120
6! 720
7! 5040
8! 40320
9! 362880
10! 3628800
11! 39916800
12! 479001600
13! 6227020800
14! 87178291200
15! 1307674368000
16! 20922789888000
17! 355687428096000
18! 6402373705728000
19! 121645100408832000
20! 2432902008176640000
21! -4249290049419214848
上述结果中，21！为负数，说明已经溢出。
程序说明：
一边做乘法，一边做除法，是一个不错的主意，可以避免结果增大的过快而产生溢出，用同类型变量可以算更大的n和m。
乘法是先乘以大的数，除法是先除以小的数，仔细观察推导可以发现，除法总是能够整除的。这是因为，2个连续的整数必有一个是偶数即必有一个数是2的倍数，3个连续的整数必有一个数是3的倍数，等等。考虑m个连续的整数，用m做模除，其中一个的余数必然是0（鸽巢原理），即必有1个整数能被m整除。
编写的函数c()可以用于n和m比较小的情况，该函数具有通用性，计算速度也比较快。
程序不够优化，重新改写了C++语言程序。改写了函数c()，循环的每一步做了简化速度会更快一些。函数中，乘法改为从小到大做乘法，这样做可以计算的n和m范围有可能更大一些。
同时添加了C语言的版本。
题记：
程序员需要面对现实世界、数学世界和机器世界，每日游离于这三个世界之中。
用计算解决问题有两种方法可以选择，一是直接编写程序，二是先进行数学推导再编写程序。
数学的优美与程序的优美是不同的。这个时代人们更多地追求程序的优美。
AC的C++语言程序（正解）如下：
/* HDU2519 新生晚会 */
#include <iostream>
#include <stdio.h>
using namespace std;
// 计算组合函数：n中取m
long long c(int n, int m)
{
long long c;
if(n < m)
c=0;
else if (n == m || m == 0)
c=1;
else {
c = 1;
n = n - m + 1;
for (int i=1; i<=m; i++) {
c *= n++;
c /= i;
}
}
return c;
}
int main()
{
int t, n, m;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
printf("%lld
", c(n, m));
}
return 0;
}AC的C语言程序如下：
/* HDU2519 新生晚会 */
#include <stdio.h>
// 计算组合函数：n中取m
long long c(int n, int m)
{
long long c;
if(n < m)
c=0;
else if (n == m || m == 0)
c=1;
else {
c = 1;
n = n - m + 1;
for (int i=1; i<=m; i++) {
c *= n++;
c /= i;
}
}
return c;
}
int main(void)
{
int t, n, m;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
printf("%lld
", c(n, m));
}
return 0;
}AC的C++语言程序如下：
/* HDU2519 新生晚会 */
#include <iostream>
#include <stdio.h>
using namespace std;
// 计算组合函数：n中取m
long long c(int n, int m)
{
long long c;
if(n < m)
c=0;
else if (n == m || m == 0)
c=1;
else {
c = 1;
for (int i=0; i<m; i++) {
c *= n - i;
c /= i + 1;
}
}
return c;
}
int main()
{
int t, n, m;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
printf("%lld
", c(n, m));
}
return 0;
}计算阶乘的程序：
#include<iostream>
#include<cstring>
using namespace std;
long long factorial(int n)
{
long long f;
if(n) {
f = 1;
for(int i=1; i<=n; i++)
f *= i;
} else
f = 1;
return f;
}
int main()
{
for(int i=0; i<=21; i++)
printf("%d! %lld
", i, factorial(i));
}