UVa 10375 Choose and divide （组合数相除）

UVa 10375 Choose and divide （组合数相除）2014-07-2410375 - Choose and divide

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=1316

The binomial coefficient C（m,n） is defined as

m！

C（m,n） = --------

n！（m-n）！

Given four natural numbers p, q, r, and s, compute the the result of dividing C（p,q） by C（r,s）.

The Input

Input consists of a sequence of lines. Each line contains four non-negative integer numbers giving values for p, q, r, and s, respectively, separated by a single space. All the numbers will be smaller than 10,000 with p>=q and r>=s.

The Output

For each line of input, print a single line containing a real number with 5 digits of precision in the fraction, giving the number as described above. You may assume the result is not greater than 100,000,000.

Sample Input

10 5 14 9

93 45 84 59

145 95 143 92

995 487 996 488

2000 1000 1999 999

9998 4999 9996 4998

Output for Sample Input

0.12587

505606.46055

1.28223

0.48996

2.00000

3.99960

思路：不要被题目那个公式误导了~自己算一算几个组合数，比如C（100,4），发现分子分母都是4个乘数，那就好办了，写一个for循环每次一除一乘就是。

完整代码：

/*0.022s*/#include<cstdio>#include<algorithm>using namespace std;int main（）{int p, q, r, s,maxn,i;double ans;while （~scanf（"%d%d%d%d", &p, &q, &r, &s））{q = max（q, p - q）, s = max（s, r - s）;maxn = max（q, s）;ans = 1.0;for （i = 1; i <= maxn; ++i）{if （i <= q） ans = ans / i * （p - q + i）;if （i <= s） ans = ans / （r - s + i） * i;}printf（"%.5f
", ans）;}return 0;}

作者署名：csdn博客 synapse7