001package algs11;
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac Binomial.java
005 *  Execution:    java Binomial N k p
006 *  Dependencies: StdOut.java
007 *
008 *  Reads in N, k, and p as command-line arguments and prints out
009 *  (N choose k) p^k (1-p)^N-k.
010 *
011 *  % java Binomial 5 2 .25
012 *  0.263671875
013 *  0.263671875
014 *
015 *  % java Binomial 5 3 .25
016 *  0.087890625
017 *  0.087890625
018 *
019 *  % java Binomial 5 0 .25
020 *  0.2373046875
021 *  0.2373046875
022 *
023 *  % java Binomial 5 5 .25
024 *  9.765625E-4
025 *  9.765625E-4
026 *
027 *************************************************************************/
028
029public class XBinomial {
030
031        // slow
032        public static double binomial1(int N, int k, double p) {
033                if (N == 0 && k == 0) return 1.0;
034                if (N < 0 || k < 0) return 0.0;
035                return (1.0 - p) *binomial1(N-1, k, p) + p*binomial1(N-1, k-1, p);
036        }
037
038        // memoization
039        public static double binomial2(int N, int k, double p) {
040                double[][] b = new double[N+1][k+1];
041
042                // base cases
043                for (int i = 0; i <= N; i++)
044                        b[i][0] = Math.pow(1.0 - p, i);
045                b[0][0] = 1.0;
046
047                // recursive formula
048                for (int i = 1; i <= N; i++) {
049                        for (int j = 1; j <= k; j++) {
050                                b[i][j] = p * b[i-1][j-1] + (1.0 - p) *b[i-1][j];
051                        }
052                }
053                return b[N][k];
054        }
055
056        public static void main(String[] args) {
057                args = new String[] { "5", "2", ".25" };
058                //args = new String[] { "5", "3", ".25" };
059                //args = new String[] { "5", "0", ".25" };
060                //args = new String[] { "5", "5", ".25" };
061
062                int N = Integer.parseInt(args[0]);
063                int k = Integer.parseInt(args[1]);
064                double p = Double.parseDouble(args[2]);
065                StdOut.println(binomial1(N, k, p));
066                StdOut.println(binomial2(N, k, p));
067        }
068
069}