CS 100: Programming Assignment P3

Solution

// This class contains methods that can be used to answer various
// combinatoric questions that involve binomial coefficients.  
public class MyMath
{
   
   // The class constants:1 point correctness and 1 point style.
   // -1 style if no comments

   public static final int KMAX = 100;                   // Iteration maximum for square root
   public static final double TOL = .0000000000000001;   // Square root tolerance
   public static final double PI = 3.14159265358979;       
   public static final double E  = 2.71828182845905;

   // The square root method = 2 points correctness + 1 point style
   // -1 style if NO comments to assist in understanding the loop.
   // -1 style if specification inadequate.
   // While loop condition 2 points. -1 if "or" instead of 'and"
   // One point for the right loop body.

   // Yields the square root of x. 
   // The value of  x must be  nonnegative.
   public static double sqrt(double x)
      int k;     // Counts the number of square root improvements
      double y;  // The kth improvement.
      k=0;
      y=x;
      while(k&ltKMAX && abs(x-y*y)/x > TOL)
      {
         y = (y+x/y)/2.0;
         k++;
      }
      return y;
   }
   

   // Absolute value method: 1 point correctness and 1 point style
   // -1 if specification inadequate

   // Yields the absolute value of x.
   public static double abs(double x)
   {
      if (x>=0)
         {return x;}
      else
         {return -x;}
   }
   
   // The binCoeff Method = 3 points correctness + 1 point style
   // 1 point for loop range, 1 point for loop body, 1 point for k = n-k idea
   // -1 style if correct but change output or input  type to double
   // -1 style inadequate specification
   // -1 style if NO comments to help follow what the loop is doing.

   // Yields the binomial coefficient n-choose-k.
   // Assumes that 0<=k<=n.
   public static long binCoeff(int n, int k)
   {
      long y = 1;  
      if (k>n/2)
         // It pays to compute n-choose-(n-k) so reset k.
         {k=n-k;}         
      for(int j=0;j&ltk;j++)
         {y = (y*(n-j))/(j+1);}   // y is n-choose-j
      return y;
   }
   
   // The pow Method = 2 points correctness + 1 point style
   // 1 point for loop range, 1 point for loop body
   // -1 style if correct but change output or input  type to double
   // -1 style inadequate specification (must say n nonnegative)
   // -1 style if NO comments to help follow what the loop is doing.

   // Yields x raised to the nth power.
   // Assumes that n is nonnegative.
   public static double pow(double x,int n)
   {
       double y = 1;
       for(int k=1;k<=n;k++)
          {y = y*x;}          // y is x-to-the-k
       return y;
   }
   
   // The stirling method = 1 point correctness + 1 point style
   // -1 style if inadequate specification (should say n nonnegative but ok not to)

   // Yields Stirling's approximation to n!
   // Assumes n is nonnegative.
   public static double stirling(int n)
   {
      if (n==0)
         {return 1.0;}
      else
         {return sqrt(2*PI*n)*pow(n/E,n);}
   }
   
   // The binCoeffAppx method = 1 point correctness + 1 point style
   // -1 style if inadequate specification (must say 0<=k<=n))

   // Yields an approximation to the binomial coefficient n-choose-k.
   // Assumes that 0<=k<=n.
   public static double binCoeffApprx(int n, int k)
   {
      return stirling(n)/(stirling(k)*stirling(n-k));
   }
}

P3A.java Output:

The square root of one million = 1000.000000000000000

The absolute value of -10 is 10.0

The absolute value of 10 is 10.0

The number of possible 5-card poker hands = 2598960

The binomial coefficient 52-choose-47     = 2598960

The 50th power of two = 1125899906842624

The Stirling approximation to 5! = 118.01916795758895

The approximate number of 5-card poker hands = 2643031

An approximation to 100-choose-30 = 2.9464561071296764E25

P3B

// P3B = 1 points correctness + 1 point style 
 // -1 style if output table really bad. 
 // -1 correctness if the binCoeff implementation done in a way that results in
 // integer arithmetic overflow.
 // Warning but no points off if 4-choose-2 not out of loop

// P3B: The probability of having exactly one pair in an n-card poker hand.	

import java.io.*;

public class P3B
{
    public static void main(String args[])
    {
       TokenReader in = new TokenReader(System.in);
       System.out.println("P is the probability of having exactly one pair in");
       System.out.println("an n-card hand.\n");
       System.out.println("  n           P");
       System.out.println("----------------------");
    
       double factor = 13.0*MyMath.binCoeff(4,2);   // A common factor in the probabilities.
       double prob;                                 // The probability pn.
       for(int n=2;n<=14;n++)
       {
          prob = factor*MyMath.binCoeff(12,n-2)*MyMath.pow(4,n-2)/(double) MyMath.binCoeff(52,n);
          Format.print(System.out,"%3d   ",n);
          Format.println(System.out,"  %10.4f",prob);
       }   
       in.waitUntilEnter();
	}
}

P3B Output:

P is the probability of having exactly one pair in
an n-card hand.

  n           P
----------------------
  2         0.0588
  3         0.1694
  4         0.3042
  5         0.4226
  6         0.4855
  7         0.4728
  8         0.3923
  9         0.2751
 10         0.1599
 11         0.0745
 12         0.0262
 13         0.0062
 14         0.0007