• 中文
    • English
  • 注册
  • 查看作者
  • 如何用C++实现输出杨辉三角

    一.  前言

    杨辉三角大概在初中就接触到了,在学习数据结构的时候再一次遇到,将所学的内容整理如下:

    二.  杨辉三角简介

    杨辉三角形,又称贾宪三角形、帕斯卡三角形、海亚姆三角形、巴斯卡三角形,是二项式系数在的一种写法,形似三角形,在中国首现于南宋杨辉的《详解九章算术》得名,书中杨辉说明是引自贾宪的《释锁算术》,故又名贾宪三角形

    三.  相关知识点

    1.  杨辉三角所有元素均由以正整数构成,数字左右对称,每行由1开始逐渐变大,然后变小,回到1。

    2.  杨辉三角顶层称第 0 层或第 1 行,第n层即第 n+1 行(注意这里和课本上不同,这里的层数相当于课本中的行数,且课本上没有打印第第0层)第 n 层的数字个数为  n + 1 个。第 n 行数字和为2^(n-1)。

    3.  杨辉三角形的第n层正好对应二项式(a + b)^n 展示系数。例如第二层121是幂指数为2 的二项式(a + b)^2 的展开式 1a^2 + 2ab + 1b ^2 的系数

    4.  除每行最左侧与最右侧的数字以外,每个数字等于它的左上方与右上方两个数字之和

    四.  图形解答

    这里以n = 4层,也就是5行为例,第0层(第0行)为 元素为1,第1层(第2行),元素为1,1 ,第2层(第3行),元素为1,2,1

    如何用C++实现输出杨辉三角

    五.  代码实现

    我们可以利用队列的知识,实现杨辉三角

    #include<stdio.h>
    class Queue
    {
    private:
        int *e;//创建一个指针,用于指向数组
        int size;//数组的最大长度
        int front,rear;
    public:
        Queue(int sz = 10)
        {
            e = new int [sz];
            size = sz;
            front = rear = 0;
        }
        ~Queue()
        {
            delete[] e;
        }
        bool enQueue(int x);//入队
        bool deQueue(int &x);//出队
        bool isEmpty()//判断队列是否为满
        {
    
            return front == rear;
        }
        bool isFull()//判断队列是否为空
        {
            return (rear + 1) % size == front;
        }
        bool getTop(int &x);//获取队顶的元素
    };
    
    bool Queue :: getTop(int &x)
    {
        if(isEmpty())
        {
            return false;
        }
        x = e[(front + 1) % size];
        return true;
    }
    
    bool Queue :: enQueue(int x)
    {
        if(isFull())
        {
            //cout << "队列满了"<< endl;
            // assert(!isFull());
            return false;
        }
    
        rear = (rear + 1) % size;
        e[rear] = x;
        return true;
    }
    
    bool Queue :: deQueue(int &x)
    {
        if(isEmpty()) return false;
        front = (front + 1) % size;
        x = e[front];
        return true;
    }
    
    void  pascalTriangle(int n)
    {
        Queue q(n + 2);//n层有n + 1 个元素,又因为是循环队列,则分配n+2个空间(其实n+2在最后还是会发生队满的情况)
        int i = 1,j,s = 0,t;
        q.enQueue(i);
        q.enQueue(i);//存入第1层的两个元素:1,1
        for(int i = 1; i <= n; i++)
        {
            printf("\n");
            q.enQueue(0);//末尾添加0元素,用于计算,这里需要注意0不输出
            for(int k = i; k <= n; k ++)
            {
                printf("  ");
            }
            for(int j = 1; j <= i + 2; j++)
            {
                q.deQueue(t);
                q.enQueue(s + t);
                s = t;
                if(j != i + 2) printf("%4d",s);
            }
        }
    }
    int main()
    {
        int n;
        printf("请输入N的大小:\n" );
        scanf("%d",&n);
        pascalTriangle(n);
        return 0;
    }

     

  • 0
  • 5
  • 0
  • 8.4k
  • 352360404

    请登录之后再进行评论

    登录
  • 0
    324 [s-17]
  • 0
    打赏了5金币。
  • 1
    打赏了666金币。
  • 1
    打赏了18金币。
  • 1
    太棒了
  • 单栏布局 侧栏位置: