Thursday, January 5, 2012

Print pascal's triangle

Pascal's triangle is based on this formula :
C(n, r) = C(n-1, r-1) + C(n-1, r)
int Pascal(int n, int r) {
if (r == 0) return 1;
if (n == 0) return 0;
return Pascal(n - 1, k - 1) + Pascal(n - 1, r);
}

In cpp, this recursive routine can use both memoization and recursion:
public static long nCr(int n, int r){
     static unsigned long table[256][256] = {0};

     if(r == 0 || n == r) {
         return table[n][r] = 1;
     }

     if(r == 1) {
         return table[n][r]  = n;
     }

     if(r > n / 2) {
         return table[n][r] = ncr(n, n - r);
     }
     return table[n][r] = table[n - 1][r - 1] + table[n - 1][r];
 }


In java, you can use a class and maintain the array outside the function and just use the function similar to above to update that array and return the value in the end.

The last approach is to use memoization only:
public static int[] [] makePascalArray(int max){
  int [][] pascal = new int[max][];

  for (int i=0; i<pascal.length; i++)
  {
   pascal[i] = new int[i+1];
   pascal[i][0] = 1;
   pascal[i][i] = 1;
   for (int j=1; j<i; j++)
   {
    pascal[i][j] = pascal[i-1][j]+pascal[i-1][j-1];
   }
  }
  return pascal;
 }
 
 public static int nCr(int n, int r){
  int[][] pascal = makePascalArray(n);
  return pascal[n][r];
 }

0 comments:

Post a Comment