題目描述

Time Limit: 1000 ms
Memory Limit: 256 mb

輸入n值，使用遞歸函數，求楊輝三角形中各個位置上的值。

輸入描述:

一個大于等于2的整型數n

輸出描述:

題目可能有多組不同的測試數據，對于每組輸入數據，
按題目的要求輸出相應輸入n的楊輝三角形。

示例

輸入：

6

輸出：

1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

思路：

楊輝三角第一行和第二行的內容很明顯，從第三行開始就很有規律了：每一行的第一個和最后一個元素都是1，從第二個到倒數第二個元素都是上一行的兩個相鄰元素的和。這里可以簡單的分為奇數行和偶數行，只需要用兩個一維數組就可以，保存相鄰的兩行元素，不斷迭代更新它們的內容，并及時輸出。雖然用一個二維數組來保存每一行的數值會簡單許多，但是題目輸入的是一個大于等于2的整數n，當n很大時，如果用一個二維數組來保存每一行的數值會占用較大的空間。

注意：根據題目的示例輸出，這里并不需要輸出楊輝三角第一行的數值1。

源代碼：

#include<iostream>
#include<vector>
using namespace std;//習題8.1 楊輝三角形
int main()
{int n;vector<int> nums1 = { 1 };vector<int> nums2 = { 1,1 };while (cin >> n) {for (int i = 2; i <= n; i++) {if (i % 2 == 1) { //奇數行nums1.resize(1);for (int j = 1; j < i - 1; j++) {nums1.push_back(nums2[j - 1] + nums2[j]);}nums1.push_back(1);for (auto it : nums1) {cout << it << " ";}cout << endl;}else { //偶數行nums2.resize(1);for (int j = 1; j < i - 1; j++) {nums2.push_back(nums1[j - 1] + nums1[j]);}nums2.push_back(1);for (auto it : nums2) {cout << it << " ";}cout << endl;}}}return 0;
}

提交結果：

?