In this post, we will write a program to generate a pascal triangle of given height.
For example, Pascal triangle of height 5 is shown below
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
The idea behind Pascal triangle is that each element in a row is the sum of left and right elements in the previous row. If the previous row does not contain left/right, they are considered as 0. The same idea is used to write simple program like the following.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <vector> | |
| using namespace std; | |
| vector< vector<int> > generate(int numRows) | |
| { | |
| vector< vector<int> > result;//Dynamic two dimensional array | |
| for( int i = 0; i < numRows; i++ ) | |
| { | |
| vector<int> row; | |
| if( i == 0 ) | |
| row.push_back(1); | |
| else | |
| { | |
| for( int j = 0; j <= i; j++ ) | |
| { | |
| //check if prev, and current exists in previous row (i-1); | |
| //If does not exists, cosider them as zeroes | |
| int prev = (j > 0) ? result[i-1][j-1] : 0; | |
| int cur = (j < i) ? result[i-1][j] : 0; | |
| row.push_back( prev + cur ); | |
| } | |
| } | |
| result.push_back(row); | |
| } | |
| return result; | |
| } | |
| void printTriangle(const vector< vector<int> > & tr) | |
| { | |
| for( int i = 0; i < tr.size(); i++) | |
| { | |
| for( int j = 0; j < tr[i].size(); j++ ) | |
| cout << tr[i][j] << " "; | |
| cout << endl; | |
| } | |
| } | |
| int main() | |
| { | |
| vector< vector<int> > res; | |
| res = generate(4); | |
| printTriangle(res); | |
| return 0; | |
| } | |
by