UVA 10375 Choose and divide(组合数学)

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

题意：给定p,q,r,s。求c(p,q) / c(r, s)。

思路：由于c(n,m)分子和分母数是相等的，所以可以进行一除一乘。就不会超过范围

代码：

#include   
  
int p, q, r, s, i;  
double ans;  
int main () {  
    while (~scanf("%d%d%d%d", &p, &q, &r, &s)) {  
        ans = 1.0;  
        if (p - q < q)  
            q = p - q;  
        if (r - s < s)  
            s = r - s;  
        for (i = 1; i <= q || i <= s; i ++) {  
            if (i <= q) {  
                ans = ans * (p - q + i) / i;  
            }  
            if (i <= s) {  
                ans = ans / (r - s + i) * i;  
            }  
        }  
        printf("%.5lf\n", ans);  
    }  
    return 0;  
}