学步园

请写一个程序，求出n中取r个的组合系数C(n,r)

首先，根据C(n,r)的定义求解，不难得出解法如下：

unsigned long cnr(int n, int r)
{
	if (n < 0 || r < 0)
		return 0;
	unsigned long numerator = 1;
	unsigned long denominator = 1;

	for (int i = 0; i < r; i++)
		numerator *= (n - i);
	for (int i = 1; i <= r; i++)
		denominator *= i;

	return numerator / denominator;
}

利用公式C(n,r)=C(n-1,r-1)+C(n-1,r)来化简求解：

#include <iostream>

using namespace std;

#define MAXSIZE 100

unsigned long cnr(int n, int r)
{
	unsigned long c[MAXSIZE];
	int i, j;
	for (i = 0; i <= r; i++)
		c[i] = 1;
	for (i = 1; i <= n - r; i++)
		for (j = 1; j <= r; j++)
			c[j] += c[j - 1];
	return c[r];
}

void main()
{
	int result = cnr(10, 2);
	cout << "result = " << result << endl;
}

快速二项式系数算法：

利用公式 (2^p + 1)^n = C(n,0) + C(n,1)2^p + C(n,2)(2^p)^2 + ... + C(n,n)(2^p)^n，只用于logn成正比的乘法次数求所有C(n,i)，i=0,1,...,n的办法吗？

#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

#define MAXSIZE 100
unsigned long answer[MAXSIZE];

unsigned long long int power(unsigned long base, unsigned long exp)
{
	unsigned long long int result = 1;
	while (exp)
	{
		if (exp & 0x01)
			result *= base;
		base *= base;
		exp >>= 1;
	}

	return result;
}

void cnr(unsigned long n, unsigned long *answer)
{
	unsigned long long int x = (1 << n) + 1;
	unsigned long long int mask = (1 << n) - 1;
	unsigned long long int result;

	result = power(x, n);
	for (unsigned long i = 0; i <= n; i++, result >>= n)
	{
		cout << result << endl;
		answer[i] = result & mask;
		cout << "answer[" << i << "] = " << answer[i] << endl;	
	}
}

void main()
{
	int number = 4;
	cnr(number, answer);
	copy(answer, answer + number, ostream_iterator<int>(cout, " "));
}

采用上面的思想确实很NB，但是该方法存在一个问题，由于result的值很大导致容易溢出。。。