1
1 1
1 2 1
1 3 3 1
1 4 6 4 1 (Figure 1)
As shown in Figure 1, one of the values of Pascal's triangle is the sum of its upper left and upper right values.
Please write a program that inputs the height N of the triangle and outputs Pascal's triangle with height N.
Sample Inputs/Outputs
Sample Input(s) | Sample Output(s) |
---|---|
The input consists of only one line containing a positive integer N (1 <= N <= 20). | Output the Pascal's triangle of height N. |
5 | 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 |
Thought Process
You can use an array to access the data from the previous row to perform calculations for the current row. Since the first row consists of all 1s, you can simply push_back a 1 outside the for loop and then output it. Use a for loop to iterate from the second row to the Nth row, and inside it, add another for loop to output the numbers corresponding to each row. Within the inner loop, check if the current position is the first or last number of the row. If it is, push_back a 1; otherwise, push_back the sum of the number at the current position and the number at the position one index to the left from the previous row. Finally, output the numbers followed by a newline character.
Sample Code-ZeroJudge K740: Pascal's Triangle
#include <iostream>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
vector<int>num;
num.push_back(1);
cout << 1 << endl;
for (int i = 2; i<=N; i++)
{
vector<int>newNum;
int output;
for (int j = 0; j<i; j++)
{
if (j == 0 || j == i-1)
{
newNum.push_back(1);
output = 1;
}
else
{
output = num[j-1]+num[j];
newNum.push_back(output);
}
cout << output << " ";
}
cout << "\n";
num.clear();
num.assign(newNum.begin(), newNum.end());
}
}
//ZeroJudge K740
//Dr. SeanXD