Pascal Triangle

Pascal Triangle



Screen Shot 2012-02-26 at 13.58.39

The obvious question when you see this, is how you generate the triangle. There are quite a few ways to generate this triangle, here are a few:


1. Generate the triangle using a formula


Apparently, there are a number of ways to do this. The first one is based on a formula and interestingly does not require any arrays as you might initially think.

Here is the formula for calculating the value at column c, row r, knowing the previous value at that row:


Screen Shot 2012-02-26 at 13.59.32

Another thing to notice is that the number of columns in each row is equal to the number of the row, so for example, in row 1 there is 1 column, in row 5 there are 5 columns, in row 8 there are 8 columns and so on.

The method below, takes the number of the rows to generate as a parameter and then outputs the number that make up the pascal triangle (although not in the triangular format).


public void generateTriangle( int maxRows  ) 
{        
        int r, value;
        
        for(int i=0; i<=maxRows; i++) 
        {           
            r = i+1//this is the row            
            value = 1//we start from col=1            
            for(int c=0; c<=i; c++) 
            {
                //special case, cannot divide by 0
                if(c>0
                {
                    value = value * (r - c) / c;                    
                }                
                System.out.print(value + " ");                    
            }
            System.out.println();
        }
}




2. Generate the triangle using a loop


    public void generateTriagle2DArray(int maxRows)
    {
        int triangle[][] = new int[maxRows + 1][(maxRows + 1) * 2];

        int leftOne, rightOne;

        triangle[0][maxRows - 1] = 1;
        leftOne = rightOne = maxRows - 1;

        for (int i = 1; i < maxRows; i++)
        {
            leftOne--;
            rightOne++;
            triangle[i][leftOne] = 1;
            triangle[i][rightOne] = 1;

            for (int c = 1; c <= i; c++)
            {
                int left = triangle[i - 1][leftOne + (* c) - 1];
                int right = triangle[i - 1][leftOne + (* c) + 1];
                triangle[i][leftOne + (* c)] = left + right;
            }
        }

        printTriangle2DArray(triangle);
    }

    public void printTriangle2DArray(int triangle[][])
    {
        for (int i = 0; i < triangle.length; i++)
        {
            for (int c = 0; c < triangle[i].length; c++)
            {
                if (triangle[i][c] == 0)
                {
                    System.out.print(" ");
                else
                {
                    System.out.print(triangle[i][c]);
                }
            }
            System.out.println();
        }
    }


3. Generate the triangle using recursion

The method below, takes the row and the column of the number to generate and uses recursion to calculate what that number should be. Of course this means, there is a great deal of recursion going on, because for example, to calculate the number for row 3, column 3, you need to calculate row 2, col. 2 and row 2, col. 3, and each of these calculations will trigger a whole new series of recursive calculations.

    
public int recrPascal(int row, int col)
    {
        int val1, val2, result = 0;
        if (row == || col == || row == col + 1)
        {
            return 1;
        }

        val1 = recrPascal(row - 1, col - 1);
        val2 = recrPascal(row - 1, col);

        return val1 + val2;
    }


And here is how you call the method above, to print the triangle:
    public void printPascalRecursion(int maxRows)
    {
        for (int i = 0; i <= maxRows; i++)
        {
            for (int j = 0; j < i; j++)
            {
                System.out.print(recrPascal(i, j) + " ");
            }
            System.out.println();
        }
    }


For maxRows=8, here is what methods in (1) and (3) above will print:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1


Method (2) will produce a nicer output since it stores the data in an array which can be later formatted in
printTriangle2DArray. Nevertheless, the output is not completely justified because some numbers in the triangle have more than 1 digit.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1