当先锋百科网

首页 1 2 3 4 5 6 7

实现代码

#include<iostream>
#include<queue>
using namespace std;

void yhTriangle(int n) {
    queue<int> q;
    q.push(1);
    int temp;
    //打印n层
    for(int i = 1; i <= n; i++) {
        q.push(1);
        //打印空格,在每一行首个元素前
        //第i层需要n-i个空格
        for(int k = i; k < n; k++) 
            cout << " ";
        //从第3层起,1.....1,中间元素需要由上一层的两数求和得出
        //所以要对第2层起元素,进行队头两个元素相加的操作
        for(int j = 2; j <= i; j++) {
            temp = q.front();
            q.pop();
            cout << temp << " ";
            //出队元素加队首元素
            q.push(q.front() + temp);
        }
        cout << q.front() << endl;  //每行最后一个结尾1后换行
        q.pop();
        q.push(1);

    }
}

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    yhTriangle(n);
    system("pause");
    return 0;
}

思路

  • 根据杨辉三角的定义,从第3层开始,每层的两端都是1,而中间的元素值等于上一层两个元素之和。
  • 具体过程
    1.先让第一行的1入队。此时队列中只有1,再让每一行左端的1入队,队列中为1 1,弹出每行右端的1(第一行只有一个1),再加入下一行右端的1,队列中1 1
    2.当到第3行左端1进入队列后1 1 1(第3行的左1),需要对第i(i > 2)层的第j(1 < j < i)个元素的值从上层相邻的两个元素求和得到。弹出队首1,此时队列中1(第2行的队尾1) 1(第3行的队首1) 2(弹出元素与队首元素相加得到),循环i-2次。
    3.弹出每一行的结尾1,并加入下一行的结尾1,此时队列1 2 1(第3行的元素)。以此类推。

测试

输入:

5
9

输出:

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1
   1 5 10 10 5 1
  1 6 15 20 15 6 1
 1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1

最后

  • 由于博主水平有限,难免有疏漏之处,欢迎读者批评指正!