This is the syntax highlighted version of Binomial.java.
/*************************************************************************
* Compilation: javac Binomial.java
* Execution: java Binomial 56 3
*
* Reads in two command line inputs n and k and print the corresponding
* binomial coefficient n choose k. Note: not perfectly accurate since
* roundoff from double to long.
*
* % java Binomial 10 2
* 45
*
* % java Binomial 100 3
* 161700
*
* % java Binomial 100 0
* 1
*
*************************************************************************/
public class Binomial {
// return integer nearest to x
static long nint(double x) {
if (x < 0.0) return (long) Math.ceil(x - 0.5);
return (long) Math.floor(x + 0.5);
}
// return log n!
static double logFactorial(int n) {
double ans = 0.0;
for (int i = 1; i <= n; i++)
ans += Math.log(i);
return ans;
}
// return the binomial coefficient n choose k.
static long binomial(int n, int k) {
return nint(Math.exp(logFactorial(n) - logFactorial(k) - logFactorial(n-k)));
}
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
int k = Integer.parseInt(args[1]);
if (n <= 0 || k > n || k < 0)
System.out.println("Illegal input.");
else
System.out.println(binomial(n, k));
}
}
Last updated: Wed Feb 11 18:13:20 EST 2004
.
Copyright © 2004, Robert Sedgewick and Kevin Wayne.