Pages

Monday, June 29, 2015

Pascal Triangles

Pascal’s triangle is a set of numbers arranged in the form of a triangle. Each number in a row is the sum of the left number and right number on the above row. If a number is missing in the above row, it is assumed to be 0. The first row starts with number 1.

Ex: The following example is a pascal with 7 rows

              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

How it work?
Each row begins and ends with the number one. The remaining numbers are obtained by summing the two numbers that lie directly above that number on the previous row and the number that follows it. So, in order to find the numbers in the nth row of the triangle, we need the values of the (n-1) the row. Let's say that we have computed the fourth row - 1 3 3 1. Now, the fifth row has five elements. The first and the last element would be one. The remaining elements would be (1+3), (3+3), (3+1) = 4, 6, 4. So, the complete fifth row would be 1 4 6 4 1.



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Pascal
{ 
    public static void main(String[] args)
    { 
        int ROW = 7;
        int max=0;
        int[][] pascal  = new int[ROW +1][];

        pascal[1] = new int[1 + 2];
        pascal[1][1] = 1;

        for (int i = 2; i <= ROW; i++)
        {
            pascal[i] = new int[i + 2];
            for (int j = 1; j < pascal[i].length - 1; j++)
            {
                pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j];
                String str = Integer.toString(pascal[i][j]);
                int len = str.length();
                if (len > max)
                    max = len;
            }
        }
        
        // Display
        for (int i = 1; i <= ROW; i++)
        {                
            for (int k = ROW; k > i; k--)
                System.out.format("%-" + max + "s", " ");
            for (int j = 1; j < pascal[i].length-1; j++)                      
                System.out.format("%-" + (max + max) + "s",  pascal[i][j]);
            System.out.println();
        }
        
    }
}

No comments:

Post a Comment