数据结构--队列Queue--打印杨辉三角

Michael阿明

发布于 2021-02-20 10:28:21

1.1K00

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

杨辉三角大家很熟悉，不做介绍了，第n行的首末两元素均为1，中间n-2个元素由n-1行相邻两元素相加得到。

将第1行数据入队（1） -------队列表示（队头，… 队尾）-------

第2行数据1入队（1,1）--------打印第n行数据并出队，同时入队第n+1行数据-------- { 打印第1行前0个数据，准备第2行中间数据，第2行中间没有数据 } 打印1行结尾1，出队（1） //打印 1 第2行结尾1入队（1,1）

第3行数据1入队（1,1,1） { 打印第2行前1个数据，1 打印出队（1,1），出队的1+队首的1=2，入队（1,1,2） } //打印 1 打印2行结尾1，出队（1,2） //打印 1 第3行结尾1入队（1,2,1）

第4行数据1入队（1,2,1,1） { 打印第3行前2个数据，1 打印出队（2,1,1），出队的1+队首的2=3，入队（2,1,1,3）；2 打印出队（1,1,3）,出队的2+队首的1=3入队（1,1,3,3） } //打印 1 2 打印3行结尾1，出队（1,3,3） //打印 1 第4行结尾1入队（1,3,3,1）

第5行数据1入队（1,3,3,1,1） { 打印第4行前3个数据，1 打印出队（3,3,1,1），出队的1+队首的3=4，入队（3,3,1,1,4）；3 打印出队（3,1,1,4）,出队的3+队首的3=6入队（3,1,1,4,6）,3 打印出队（1,1,4,6）,出队的3+队首的1=4，入队（1,1,4,6,4）} //打印 1 3 3 打印4行结尾1，出队（1,4,6,4） //打印 1 第5行结尾1入队（1,4,6,4,1）

以上列举了打印4行杨辉三角 1 1 1 1 2 1 1 3 3 1

代码实现如下：

/**
 * @description: 用队列打印杨辉三角
 * @author: michael ming
 * @date: 2019/4/4 20:30
 * @modified by: 
 */
#include <iostream>
#include <queue>
#include <iomanip>
using  namespace std;
void yanghuitriangle(size_t n)
{
    queue<int> line;
    line.push(1);    //第一行元素
    int temp, space = n;
    for(int i = 2; i <= n+1; ++i)   //打印第n行元素，产生第n+1行队列
    {
        line.push(1);        //第n+1行的第1个元素
        cout << setw(space--);  //设置开始打印前的空格个数
        for(int j = 1; j <= i - 2; ++j) //产生第n+1行的中间n-1个元素
        {
            temp = line.front();
            cout << temp << " ";    //打印第n行的n-1个元素，并出队
            line.pop();
            temp = temp + line.front(); //相邻两数相加，并入队（n+1行的）
            line.push(temp);
        }
        cout << line.front() << endl;   //打印第n行最后1个元素，并出队
        line.pop();
        line.push(1);    //n+1行最后1个元素
    }
}

int main()
{
    size_t N;
    cout << "请输入杨辉三角的行数：";
    cin >> N;
    yanghuitriangle(N);
    return 0;
}

运行结果