INTRODUCTION TO COMPUTER SCIENCE
Robert Sedgewick and Kevin Wayne


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.