1
1 1
1 2 1
1 3 3 1
1 4 6 4 1 (圖 1)
如圖 1 所示,一個楊輝三角形的其中一個值等於它左上方與右上方的和;
請寫一個程序,輸入三角形的高度 N,輸出高度為 N 的楊輝三角形。
範例測資
範例輸入 | 範例輸出 |
---|---|
輸入僅有一行,為一個正整數 N (1 <= N <= 20)。 | 輸出高度為 N 的楊輝三角形。 |
5 | 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 |
解題思路
可以使用陣列來存取上一行的資料來做這一行的運算。第一行因為都是一個1所以可以直接在For迴圈外面push_back一個1進去+輸出即可。使用 For迴圈 從第二行跑到第N行,裡面再放一個 For迴圈,第幾行就要輸出幾個數字。在第二個For迴圈裡判斷目前是不是跑到第一個數字或是最後一個數字,如果是的話就是push_back一個1,如果不是的話就將上一行的這個位置的數字加上上一行的這個位置-1的數字push_back,最後再進行輸出+換行即可。
範例程式碼-ZeroJudge K740: 楊輝三角形
#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