UVa 369 Combinations

解題策略

組合公式: C(n,r) = n! / (n-r)!r!
直接使用組合公式來計算結果就可以了。

必須注意的就是階乘的成長速度極快，14! 的值就已經超出long的範圍，更別說第一個範例測資 C(100,6)，100!保證爆掉。所以不能分開計算分子分母最後再相除，要在迴圈中邊乘邊除，壓低計算過程中的數字。

注意

要用浮點數，因為除法會產生小數點。ZeroJudge的測資更嚴苛些，想通過最好把變數精確度提高到long double。而long double與printf溝通的代號是%Lf

碎碎念

偷懶寫的遞迴解法，果然製造 Time Limit Exceeded。自己測了一下，C(34,20)要跑個十來秒，數量級成長很恐怖呀。(汗)

	/**
	* UVa 369 Conbinations
	* Author: chchwy
	* Last Modified: 2008/09/17
	*/
	//C(n,r)= n! / (n-r)!r!
	#include<cstdio>
	long double C(int n, int r)
	{
	if (n - r < r) r = n - r; // C(5,3)==C(5,2)
	long double product = 1;
	for (int i = 1; i <= r; i++)
	{
	product = product * (n - r + i) / i;
	}
	return product;
	}
	int main()
	{
	int n, r;
	while (scanf("%d %d", &n, &r) == 2)
	{
	if (n == 0 && r == 0) break;
	printf("%d things taken %d at a time is %.0Lf exactly.\n", n, r, C(n, r));
	}
	return 0;
	}

view raw 369.cpp hosted with ❤ by GitHub