ZeroJudge K740: 楊輝三角形

        1
      1   1
    1   2   1
  1   3   3   1
1   4   6   4   1   (圖 1)

如圖 1 所示,一個楊輝三角形的其中一個值等於它左上方與右上方的和;

請寫一個程序,輸入三角形的高度 N,輸出高度為 N 的楊輝三角形。

範例測資

範例輸入範例輸出
輸入僅有一行,為一個正整數 N (1 <= N <= 20)。輸出高度為 N 的楊輝三角形。
51
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

發佈留言