队列实现杨辉三角

杨辉三角解题公式(二)杨辉三角解题公式什么是杨辉三角？杨辉三角是中国古代数学家杨辉发现的一种特殊数列排列方式。

它的特点是，每一行的端点和每一行的中间数都是1，其他位置上的数是上一行两个相邻数的和。

杨辉三角解题公式第n行第k个数的计算公式第n行第k个数的计算公式可以表示为：C(n,k)=n!k!(n−k)!其中，n!表示n的阶乘，即n!=n×(n−1)×(n−2)×...×2×1。

例子我们来计算一下杨辉三角的第5行：第1个数：C(5,1)=5!1!(5−1)!=5!1!×4!=5×4×3×2×11×4×3×2×1=5第2个数：C(5,2)=5!2!(5−2)!=5!2!×3!=5×4×3×2×12×1×3×2×1=10第3个数：C(5,3)=5!3!(5−3)!=5!3!×2!=5×4×3×2×13×2×1×2×1=10第4个数：C(5,4)=5!4!(5−4)!=5!4!×1!=5×4×3×2×14×3×2×1×1=5第5个数：C(5,5)=5!5!(5−5)!=5!5!×0!=5×4×3×2×15×4×3×2×1×1=1所以，第5行的数列为：1, 5, 10, 10, 5, 1。

这就是杨辉三角的特性：每一行的数都可以通过计算上一行的两个相邻数得到，并且每一行的端点和中间数都是1。

python实现杨辉三⾓的⼏种⽅法代码实例⽅法⼀：迭代def triangle_1(x):""":param x: 需要⽣成的杨辉三⾓⾏数:return:"""triangle = [[1], [1, 1]] # 初始化杨辉三⾓n = 3 # 从第三⾏开始计数,逐⾏添加while n <= x:for i in range(0, n-1):if i == 0:# 添加初始列表[1,1],杨辉三⾓每⾏的⾸位和末位必为1triangle.append([1, 1])else:# 逐位计算，并插⼊初始列表中triangle[n-1].insert(i, triangle[n - 2][i] + triangle[n - 2][i - 1])n += 1return trianglex = 11triangle = triangle_1(x)# 遍历结果，逐⾏打印for i in range(x):print(' '.join(str(triangle[i])).center(100)) # 转为str,居中显⽰⽅法⼆：⽣成器def triangle_2(n):""":param n: 需要⽣成的杨辉三⾓⾏数:return:"""triangle = [1] # 初始化杨辉三⾓for i in range(n):yield triangletriangle.append(0) # 在最后⼀位加个0，⽤于计算下⼀⾏triangle = [triangle[i] + triangle[i - 1] for i in range(len(triangle))]# 从⽣成器取值for i in triangle_5(10):print(''.join(str(i)).center(100)) # 格式化输出⽅法三：递归杨辉三⾓特性：【1，1】=【0，1】+【1，0】【1，2，1】=【0，1，1】+【1，1，0】【1，3，3，1】=【0，1，2，1】+【1，2，1，0】【1，4，6，4，1】=【0，1，3，3，1】+【1，3，3，1，0】第n⾏等于第n-1⾏分别⾸尾补0，然后按位相加def triangle_4(n):""":param n:需要⽣成的杨辉三⾓⾏数:return:"""triangle = [1] # 初始化杨辉三⾓if n == 0:return trianglereturn [x+y for x, y in zip([0] + triangle_4(n - 1), triangle_4(n - 1) + [0])]for i in range(10):print(''.join(str(triangle_4(i))).center(100))到此这篇关于python实现杨辉三⾓的⼏种⽅法代码实例的⽂章就介绍到这了,更多相关python实现杨辉三⾓内容请搜索以前的⽂章或继续浏览下⾯的相关⽂章希望⼤家以后多多⽀持！。

杨辉三角(一)需求分析1.逐行打印二项展开式(a + b)i 的系数2.要求：输入杨辉三角的阶数n，在屏幕上显示数杨辉三角形。

3.输入的值n以小于12为宜（图形漂亮）。

(二)概要设计1. 首先初始化一个队列，元素为1，然后根据这个队列迭代生成任意行的二项式系数。

2. 判断用户输入的行数，然后决定循环次数。

这些循环中，程序根据杨辉三角的实际构造函数模拟构造过程。

每次形成一个新的二项式系数序列，并将这个序列保持在一个新的队列中。

本次循环结束后，这个心构造的序列将作为下次循环来构造另一个二项式序列的参照序列。

(三)详细设计1.定义队列结点typedef struct QNode{int data;struct QNode *next;}QNode ,*QueuePtr;typedef struct {QueuePtr front;QueuePtr rear;}LinkQueue;2.基本操作函数原型●队列初始化void InitQueue(LinkQueue *Q){Q->front =Q->rear = (QueuePtr)malloc(sizeof(QNode));if(!Q->front) printf("OVERFLOW");Q->front->next= NULL;}●插入元素e为新的队尾元素void EnQueue(LinkQueue *Q,int e){QNode *p;p = (QueuePtr)malloc(sizeof(QNode));if(!p) printf("OVERFLOW");p->data = e;p->next = NULL;Q->rear->next = p;Q->rear = p;}●void DeQueue(LinkQueue *Q){ QNode *p;if(Q->front == Q->rear) printf("ERROR");Q->front->next = Q->front->next->next;}●美化形状for(i = 1;i <= n; i++){printf("\n");c=i;for(b=1;b<=n-c;c++){printf(" ");}}●根据上行系数求下行系数for (j=1;j<=i+2;j++){t = q->front->next->data;DeQueue (q);EnQueue (q,s+t);s = t;if (j!=i+2) printf("%3d ",s);}(四)调试分析1.美化形状时，第一次的输出空格的个数和位置考虑的有瑕疵，导致图像歪歪曲曲的。

利⽤队列实现逐⾏打印杨辉三⾓形的前n⾏
分别打印⼆项式(a+b)^n展开项的系数，在程序中利⽤了⼀个队列，在输出上⼀⾏系数时，将下⼀⾏的系数预先放⼊队列中。

在各⾏系数间插⼊0。

void YANGVI(int n){
Queue q(n+2); //建⽴队列对象q并初始化。

int i=1,j,s=0,t,u;
q.EnQueue(1);q.EnQueue(1); //插⼊第⼀⾏元素
for(i=1; i<=n; i++){
cout<<endl; //换⾏
q.EnQueue(0); //每⾏刚开始打印的时候，先在队列尾部插⼊⼀个0
for(j=1; j<=i+2; j++){ //第i⾏有i+1个系数和1个0
q.DeQueue(t); //第i⾏第j个系数t出队列
u=s+t; //s为第i⾏第j-1个系数,j==1时s必为0
q.EnQueue(u); //计算第i+1⾏第j个系数u=s+t并进队列
s=t;
if(j!=i+2) cout<<s<<''; //打印移除的系数，第i+2个是0
}
}
}
最后第n⾏的n+2次循环执⾏完后，队列⾥是第n+1⾏的n+2个数，0还没来得及⼊队列（因为换⾏后才会把0⼊队列）。

/*用队列方法输出杨辉三角。

*/#include<iostream.h>#include<iomanip.h>#include<stdlib.h>#define ElemType int/*-----LNode的结点类型定义-----*/struct LNode{ElemType data; //值域LNode* next; //链接指针域};/*-----队列的链接存储结构的定义-----*/struct LinkQueue{LNode* front; //队首指针LNode* rear; //队尾指针};/*------1.初始化链队-----*/void InitQueue(LinkQueue& HQ){HQ.front=HQ.rear=NULL; //把队首和队尾指针置为空}/*-----2.向链队中插入一个元素------*/void EnQueue(LinkQueue& HQ, ElemType item){LNode* newptr=new LNode; //得到一个新的结点newptr->data=item; //把item 的值赋给新结点的值域newptr->next=NULL; //把新结点的指针域置为空if(HQ.rear==NULL) //若链队为空，则新结点既是队首又是队尾{HQ.front=HQ.rear=newptr;}else //若链队非空，则新结点被链接到队尾并修改队尾指针{HQ.rear=HQ.rear->next=newptr;}}/*-------3.从队列中删除一个元素-------*/ElemType OutQueue(LinkQueue& HQ){if(HQ.front==NULL) //若链队为空则终止运行{cerr<<"链队为空，无法删除！"<<endl;exit(1);}ElemType temp=HQ.front->data; //暂存队首元素以便返回LNode* p=HQ.front; //暂存队首指针以便收回队首指针HQ.front=p->next; //使队首指针指向下一个结点if(HQ.front==NULL) //若删除后链队为空，则使队尾指针为空{HQ.rear=NULL;}delete p; //回收原队首结点return temp; //返回被删除的队首元素}void YanyHuiTriangular(LinkQueue& HQ, int n){int i,j; //i，j 都是循环变量int first,second; //first,second 分别记录上一行的两个累加数EnQueue(HQ,1);for(i=1; i<n+1; i++){ //第 0 至 n-1 行元素分别入列，并输出；最后第 n 行入列first=0; second=0;//控制每行前头空格的输出for(j=0; j<n-i+1; j++){cout<<setw(3)<<' ';}for(j=0; j<i; j++){second=OutQueue(HQ);cout<<setw(3)<<second<<setw(3)<<' ';EnQueue(HQ,first+second);first=second;}cout<<endl; //输完一行，回车EnQueue(HQ,second);}//最后输出最后一行元素（即第 n 行出列）for(j=0; j<n+1; j++){cout<<setw(3)<<OutQueue(HQ)<<setw(3)<<' '; }cout<<endl;}void main(){LinkQueue LQ;InitQueue(LQ);cout<<"用队列输出杨辉三角!"<<endl<<endl; int n;cout<<"请输入要输出多少行杨辉三角："; cin>>n;YanyHuiTriangular(LQ,n);}。

数据结构实验报告实验一杨辉三角形(Pascal’s triangle)一、需求分析1.输入的形式和输入值的范围本程序中，需输入的杨辉三角级数level为正整数，由键盘输入，以回车结束2.输出的形式通过屏幕输出杨辉三角3.程序所能达到的功能用户从键盘输入需要的杨辉三角级数，从屏幕输出杨辉三角4.测试数据输入：5输出： 1 11 2 11 3 3 11 4 6 4 11 5 10 10 5 1二、概要设计以链队列结构实现该实验1.抽象数据类型定义ADT Queue {数据对象：D = { ai | ai∈ElemSet , i = 1,2,…,n,n≥0 }数据关系：R1={<ai-1,ai> | ai-1 , ai∈D, i=2,…,n}约定其中ai端为队列头，an端为队列尾基本操作：InitQueue ( &Q )操作结果：构造一个空队列QDestroyQueue ( &Q )初始条件：队列Q已存在操作结果：队列Q被销毁，不再存在ClearQueue ( &Q )初始条件：队列Q已存在操作结果：将Q清为空队列QueueEmpty ( Q )初始条件：队列Q已存在操作结果：若Q为空队列，则返回TRUE，否则FALSEQueueLength ( Q )初始条件：队列Q已存在操作结果：返回Q的元素个数，即队列长度GetHead ( Q , &e )初始条件：Q为非空队列操作结果：用e返回Q的队头元素EnQueue ( &Q , e )初始条件：队列Q已存在操作结果：插入元素e为Q的新队尾元素DeQueue ( &Q , &e )初始条件：Q为非空队列操作结果：删除Q的队头元素，并用e返回其值QueueTraverse ( Q , visit( ) )初始条件：Q已存在且非空操作结果：从队头到队尾，依次对Q的每个数据元素调用函数visit( )。

实验4 杨辉三角1 实验要求打印二项展开式（a+b）^i的系数，将其系数构成杨辉三角形。

2 简单的需求分析1，该程序的描述是：建立一个循环队列，以及一个利用队列实现逐行打印杨辉三角形的前n行的算法，最后在主函数中输入所要打印的杨辉三角形的行数，调用函数输出结果。

2，程序运行后,首先会出现"请输入二项式为几次幂"，用户根据自己的选择输入后，系统便会输出打印的情况。

3 概要设计1、所用的抽象数据类型：（1）//循环队列的类定义template<class T>class SeqQueue{public:SeqQueue(int sz=10); //构造函数~SeqQueue(){delete[] elements;} //析构函数bool EnQueue(const T& x); //若队列不满，则将x进队，否则队溢出处理bool DeQueue(T& x); //若队列不空，则退出队头元素x并由函数返回true，否则队空，返回falseprotected:int rear,front; //队尾与队头指针T* elements; //存放队列元素的数组int maxSize; //队列最大可容纳元素个数};（2） //链式栈的类定义void YANGVI(int n){//分行打印二项式(a+b)^n展开式的系数，在程序中利用一个队列，在输出上一行系数时，将其//下一行的系数预先放入队列中，在各行系数之间插入一个0int k;SeqQueue<int> q(n+2); //建立队列对象并初始化int i=1,j,s=k=0,t,u,m; //计算下一行系数时用到的工作单元q.EnQueue(i);q.EnQueue(i); //预先放入第一行的两个系数for(i=1;i<=n;i++) //逐行处理{cout<<endl; //换一行q.EnQueue(k); //各行间插入一个0for(j=1;j<=i+2;j++) //处理第i行的i+2个系数（包括一个0）{q.DeQueue(t); //读取一个系数u=s+t; q.EnQueue(u); //计算下一行系数，并进队列s=t;if(j!=i+2) cout<<s<<' '; //打印一个系数，第i+2个是0 }}}2、函数调用关系：在main（）函数中，先输入所要打印的杨辉三角形的行数，然后调用YANGVI(int n)函数4 详细设计部分#include<iostream.h>#include<assert.h>#include<stdio.h>//循环队列的类定义template<class T>class SeqQueue{public:SeqQueue(int sz=10); //构造函数~SeqQueue(){delete[] elements;} //析构函数bool EnQueue(const T& x); //若队列不满，则将x进队，否则队溢出处理bool DeQueue(T& x); //若队列不空，则退出队头元素x并由函数返回true，否则队空，返回falseprotected:int rear,front; //队尾与队头指针T* elements; //存放队列元素的数组int maxSize; //队列最大可容纳元素个数};//循环队列的构造函数template<class T>SeqQueue<T>::SeqQueue(int sz):front(0),rear(0),maxSize(sz){//建立一个最大具有maxSize个元素的空队列elements=new T[maxSize];//创建队列空间assert(elements!=NULL);//断言：动态存储分配成功与否}//循环队列的进队template<class T>bool SeqQueue<T>::EnQueue(const T& x){if((rear+1)%maxSize==front) {return false;} //队列满则插入失败，返回else{elements[rear]=x; //按照队尾指针指示位置插入rear=(rear+1)%maxSize; //队尾指针加1return true; //插入成功，返回}}//循环队列的出队template<class T>bool SeqQueue<T>::DeQueue(T& x){if(front==rear) {return false;} //若队列空则删除失败，返回else{x=elements[front];front=(front+1)%maxSize; //队头指针加1return true;//删除成功，返回}}//打印杨辉三角形的前n行函数定义void Y ANGVI(int n){//分行打印二项式(a+b)^n展开式的系数，在程序中利用一个队列，在输出上一行系数时，将其//下一行的系数预先放入队列中，在各行系数之间插入一个0int k;SeqQueue<int> q(n+2); //建立队列对象并初始化int i=1,j,s=k=0,t,u,m; //计算下一行系数时用到的工作单元q.EnQueue(i);q.EnQueue(i); //预先放入第一行的两个系数for(i=1;i<=n;i++) //逐行处理{cout<<endl; //换一行q.EnQueue(k); //各行间插入一个0for(j=1;j<=i+2;j++) //处理第i行的i+2个系数（包括一个0）{q.DeQueue(t); //读取一个系数u=s+t; q.EnQueue(u); //计算下一行系数，并进队列s=t;if(j!=i+2) cout<<s<<' '; //打印一个系数，第i+2个是0}}}//主函数void main(){int m;cout<<"请输入二项式为几次幂"<<endl;cin>>m;Y ANGVI(m);cout<<endl;}/5 调试与测试1.输入所要打印的杨辉三角形的行数2，显示结果。

循环队列实现杨辉三⾓形的打印知识温习循环队列：即将顺序队列的数组看成是⼀个环状的空间，规定最后⼀个单元的后继为第⼀个单元。

运⽤循环队列可以有效的解决链队列的“假溢出”现象。

假溢出其实是指在链队列中，当rear==MAXSIZE时就认为队满。

然⽽由于元素的出队，使得数组前⾯出现⼀些空单元，⽽元素⼜只能在队尾⼊队，如果此时已经到数组的尾部，就认为队列已满，但其实还存在上述那些空单元未使⽤，队列并未真正满。

这种现象即为“假溢出”现象。

真正的队满条件应该是rear-front==MAXSIZE。

在循环队列中，我们通过数学中的求模运算来改变头指针和尾指针的位置。

进队操作时，队尾指针的变化是：rear=（rear+1）mod MAXSIZE；⽽出队操作时，队头指针的变化是：front=（front+1）mod MAXSIE。

杨辉三⾓形11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1从上图中可以看出，杨辉三⾓形的特点：每⾏的第⼀个元素和最后⼀个元素都为1，其他位置上的元素总是等于上⼀⾏与之相邻的两个元素之和。

故第i⾏的元素要由第i-1⾏的元素来⽣成。

可以利⽤循环队列实现杨辉三⾓形的打印过程：在循环队列中依次存放第i-1⾏上的元素，然后逐个出队并打印，同时⽣成第i⾏元素并⼊队。

下⾯⽤第6⾏元素⽣成第7⾏元素为例⼦来说明打印过程：①第7⾏的第⼀个元素1⼊队。

element[Q->rear] = 1;Q->rear = (Q->rear + 1)% MAXSIZE;②循环做以下操作，⽣成第7⾏的中间5个元素并⼊队。

element[Q->rear] = element[Q->front] + element[(Q->front+1)%MAXSIZE];Q->rear = (Q->rear + 1)%MAXSIZE;Q->front = (Q->front + 1)%MAXSIZE;③第6⾏的最后⼀个元素1⼊队。

队列实现杨辉三角的算法原理
杨辉三角是一种数学模式，每个位置上的数字等于它上方两个数字之和。

队列可以用来实现杨辉三角的算法，其原理如下：
1. 首先，创建一个空的队列。

2. 将1入队列，作为第一行的元素。

3. 进行循环，从第二行开始到第n行：
- 将当前队列中的元素依次出队，并将它们存储在一个临时数组temp中。

- 在temp数组末尾添加一个0，作为哨兵元素。

- 再将temp数组中的元素依次相加，并将结果入队列。

4. 打印队列中的元素，即可得到杨辉三角的结果。

这个算法的基本思路是利用队列先进先出的特性，每次处理一行的数据。

在处理每一行时，将队列中的元素依次出队，并计算它们的和，然后将和再次入队，作为下一行的元素。

通过不断重复这个过程，最终得到的队列中的元素就是杨辉三角的结果。

杨辉三⾓队列实现杨辉三⾓显⽰问题描述：编写程序，根据输⼊的⾏数，屏幕显⽰杨辉三⾓。

基本要求：(1)⾏数不⼤于20⾏。

(2)基于队列的操作来实现杨辉三⾓的不断⽣成过程。

（注：不要⽤其它的公式计算的⽅法或者⼆维数组来实现）（3）基于数组实现队列的物理数据结构需求分析：1、输⼊形式：输⼊⼀个整数n ，0<=n<=202、输出形式：打印出来前(n+1)⾏的杨辉三⾓数列3、功能实现：输出前20层的杨辉三⾓序列4、样例输⼊输出：（数据加强版）输⼊：10输出：1 n=11 1 n=21 2 1 n=31 3 3 1 n=41 4 6 4 1 n=51 5 10 10 5 1 n=61 6 15 20 15 6 1 n=71 7 21 35 35 21 7 1 n=81 8 28 56 70 56 28 8 1 n=91 9 36 84 126 126 84 36 9 1 n=105、效率分析：O(n)抽象数据类型（ ADT）:抽象数据结构描述：Typedef struct {Int q[MaxSize];//存放队列中的元素Int front,rear;//front和rear分别是指向队头和队尾的指针}Queue;队列的基本操作：V oid InitQueue(Queue Q) function:构造⼀个空队列V oid EnQueue(Queue Q,int x) :function:将元素x⼊队V oid DeQueue(Queue Q,int x):function:删除队头元素，并⽤x返回其值Bool QueueEmpty(Queue Q) function:判断队列是否为空概要设计：既然要⽤到队列来打印杨辉三⾓，那么肯定会利⽤到队列FILO的性质（First In Lase Out），由于是要打印⼀个数列，那么肯定要利⽤已经进队的元素在其出队之前完成杨辉三⾓的递归性----即利⽤要出队的元素来不断地构造新的进队的元素，即在第N⾏出队的同时，我们来构造杨辉三⾓的第N+1⾏，从⽽实现打印杨辉三⾓的⽬的。

for(i=1;i<=N;++i){for(j=0;j<30-3*i;++j)//打印每行前面的空格printf(" ");do{DeQueue();GetHead();if(e!=0) printf("%6d",e);EnQueue();}while(e!=0);UpQueue();puts("");//每行后回车换行}以n=4举例结果为：1 11 2 11 3 3 11 4 6 4 1解析：queue_size=n+2;//队列的最大容量queue_size=6（数组空间大小）for(i=0;i<n-2;++i) queue[i]=0;//初始化queue[i]=1,queue[i+1]=1,queue[i+2]=0;front=i-1,rear=n+1;初始化后的队列(queue数组)：front0 0 1 1 0rear打印第一行（即for（）循环中i=1）DeQueue(); 删除队首元素，并将0赋值s 实际只将front向下移一位，front=2，即指向queue[2] GetHead(); 取队首元素，e= queue[front]= queue[2]=1if(e!=0) printf("%6d",e); e！=0 打印e 即1继续执行do……while语句因为e不为0DeQueue(); 删除队首元素，并将queue[2]赋值s front=3GetHead(); 取队首元素，e= queue[front]=queue[3]=1if(e!=0) printf("%6d",e); e！=0 打印e 即1EnQueue(); 在队尾添加元素s+e 此时queue[rear]=queue[0]=2 rear=1继续执行do……while语句因为e不为0DeQueue(); 删除队首元素，并将queue[3]赋值s front=4GetHead(); 取队首元素，e= queue[front]=queue[4]=0if(e!=0) printf("%6d",e); e==0 不执行printf（）语句EnQueue(); 在队尾添加元素s+e 此时queue[rear]=queue[1]=1 rear=2此时e==0跳出do……while语句即打印第一行完毕输出： 1 1UpQueue(); 在队尾添加元素0 即queue[rear]=queue[2]=0 rear=3队列为：2 1 0 1 0 1puts("");//每行后回车换行rearfront打印第二行DeQueue(); s=0 front=5GetHead(); e=1if(e!=0) printf("%6d",e); e！=0 打印e 即1EnQueue(); 在队尾添加元素s+e 此时queue[rear]=queue[3]=1 rear=4继续……DeQueue(); s=1 front=6 对queue_size取模即指向queue[0] front=0GetHead(); e=2if(e!=0) printf("%6d",e); e！=0 打印e 即2EnQueue(); 在队尾添加元素s+e 此时queue[rear]=queue[4]=3 rear=5继续……DeQueue(); s=2 front=1GetHead(); e=1if(e!=0) printf("%6d",e); e！=0 打印e 即1EnQueue(); 在队尾添加元素s+e 此时queue[rear]=queue[5]=3 rear=6对queue_size取模即指向queue[0] rear=0继续……DeQueue(); s=1 front=2GetHead(); e=0if(e!=0) printf("%6d",e); e==0 不打印EnQueue(); 在队尾添加元素s+e 此时queue[rear]=queue[0]=1 rear=1此时e==0跳出do……while语句即打印第二行完毕输出： 1 2 1UpQueue(); 在队尾添加元素0 即queue[rear]=queue[1]=0 rear=2队列为：……剩下依此类推……。

使⽤队列实现杨辉三⾓使⽤队列实现杨辉三⾓杨辉三⾓的特点：除了第⼀⾏，其他⾏两端都为1；从第三⾏开始可以看出，除了两端，其中每个数都是元素本⾝上⾯对着的两个数的和；奇数⾏有奇数个数，偶数⾏有偶数个数，都是n个数每⾏数从左端开始看到中间都是升序，都是正序。

想要⽤代码来实现杨辉三⾓最简单的⽅法就是使⽤两个数组来实现，互相承载结果，并将数组打印出来。

但结合杨辉三⾓的特点，正序可以想到⽤队列的问题来解决。

解决⽅案：可以想到，作为开端的1可以看成是0和1的和，因此开始可以将队列设成这样（此处是以3⾏为例⼦）设定变量a和b来作为队列第⼀个元素和第⼆个元素的载体。

在a获取了第⼀个元素后将第⼀个元素移出队列，然后让b获取新的第⼀个元素，然后将a和b加起来，并将结果移进队列中，并将结果打印出来然后重复上述步骤，可以得到：要能够获取第⼆⾏的值，我在第⼀⾏中进⾏两次和运算即可，第⼀轮到此也就可以停⽌了。

然后，让⼀个0⼊列，再次重复上⾯的步骤，具体流程⼤概是这样：遇到的问题：最初的原代码：package ch15;import java.util.Scanner;/*** Created by Funny_One on 2017/10/13.*/public class YangHuiTriangle {public static void main(String[] args) {CircularArrayQueue<Integer> queue = new CircularArrayQueue();Scanner sca = new Scanner(System.in);System.out.println("需要显⽰的⾏数：");int n = sca.nextInt();queue.enqueue(0);queue.enqueue(1);System.out.println(1);for(int times =0;times<n;times++){queue.enqueue(0);for(int i=1;i<queue.size()-1;i++){int a,b=0,c;if(queue.size()==1){a = b;b = queue.first();c = a + b;queue.enqueue(c);System.out.print(c);}else {a=queue.first();queue.dequeue();b = queue.first();queue.dequeue();c = a+b;queue.enqueue(c);System.out.print(c+" ");}}System.out.println();}}}运⾏的结果是：可以见到，其中出现的问题有：问题1：每⼀⾏只有⼀个元素；问题2：每个元素都是1；问题3: 不只有三⾏；在我进⾏调试之后，发现这些问题的原因是：问题1的原因：在我的代码中，当a和b将数据获取之后，⼀个1⼊列，1被打印出来，同时两个数被移出队列。

数据结构之杨辉三⾓（队列实现）（C++版）#include <iostream>#include <stdlib.h>#include <windows.h>#include <string>#define MAXLISTSIZE 100 //预设的存储空间最⼤容量#define TRUE 1#define FALSE 0using namespace std;typedef int ElemType;typedef struct{ElemType *elem; //存储空间基址 int rear; //队尾指针 int front; //队头指针int queuesize; //允许的最⼤存储空间，以元素为单位 }Queue;void InitQueue(Queue &Q, int maxsize){//构造⼀个最⼤存储空间为 maxsize 的空队列 Q if (maxsize == 0)maxsize = MAXLISTSIZE;Q.elem = new ElemType[maxsize]; //为循环队列分配存储空间 if (!Q.elem) exit(1); //存储分配失败Q.queuesize = maxsize;Q.front = Q.rear = 0;} //InitQueuebool EnQueue(Queue &Q, ElemType e){// 若当前队列不满，这在当前队列的尾元素之后，插⼊元素 e 为新的队列尾元素,并返回TRUE,否则返回FALSEif((Q.rear + 1) % Q.queuesize == Q.front)return FALSE;Q.elem[Q.rear] = e;Q.rear = (Q.rear+1) % Q.queuesize;return TRUE;}bool DeQueue(Queue &Q, ElemType &e){//若队列不空，则删除当前队列Q中的头元素，⽤ e 返回其值，并返回TRUE，否则返回 FALSE　if (Q.front == Q.rear)return FALSE;e = Q.elem[Q.front];Q.front = (Q.front+1) % Q.queuesize;return TRUE;}bool GetHead(Queue Q, ElemType &e){//若队列不空，则⽤ e 返回队⾸元素，并返回TRUE，否则返回 FALSEif (Q.front == Q.rear)return FALSE;e = Q.elem[Q.front];return TRUE;}int QueueLength(Queue Q){//返回队列Q中元素个数，即队列的长度return((Q.rear-Q.front+Q.queuesize) % Q.queuesize);}bool QueueEmpty(Queue Q){if(Q.front == Q.rear)return TRUE;elsereturn FALSE;}int main(void){//打印输出杨辉三⾓的前n(n>0)⾏int n, i, k;Queue Q;ElemType s, e;cout << "请输⼊杨辉三⾓的⾏数：";cin >> n;/* for(i = 1; i <= n; i++)cout << ' ';cout<< '1' << endl; // 在中⼼位置输出杨辉三⾓最顶端的"1"*/ InitQueue(Q, n+3); // 设置最⼤容量为 n+3 的空队列EnQueue(Q, 0); // 添加⾏界值EnQueue(Q, 1);EnQueue(Q, 1); // 第⼀⾏的值⼊队列k = 1;while(k < n){ // 通过循环队列输出前 n-1 ⾏的值for(i = 1; i <= n - k; i++)cout<< ' '; // 输出n-k个空格以保持三⾓型EnQueue(Q, 0); // ⾏界值"0"⼊队列do { // 输出第 k ⾏，计算第 k+1 ⾏DeQueue(Q, s);GetHead(Q, e);if(e) cout<< e << ' '; //若e为⾮⾏界值0，则打印输出 e 的值并加⼀空格else cout << endl; //否则回车换⾏，为下⼀⾏输出做准备EnQueue(Q, s+e);}while(e!=0);k++;}//whileDeQueue(Q, e); //⾏界值"0"出队列while (!QueueEmpty(Q)){ //单独处理第 n ⾏的值的输出DeQueue (Q, e);cout << e << ' ';}//whilecout << endl;}//yanghui。

杨辉三角垛列递推公式求法杨辉三角，这玩意儿在数学世界里可算是个有趣的存在。

咱今天就来聊聊怎么通过递推公式来求解杨辉三角垛列。

记得我当年读书的时候，第一次接触杨辉三角，那感觉就像是走进了一个神秘的数字迷宫。

老师在黑板上写下那一排排整齐的数字，我当时就被它的规律给吸引住了。

咱先来说说杨辉三角到底是啥。

它就是一个由数字排列成的三角形，每行的数字都是通过特定的规律生成的。

这个规律简单来说，就是每行的开头和结尾都是 1，而中间的数字则是上一行相邻两个数字的和。

那杨辉三角垛列又是什么呢？其实就是把杨辉三角的每行数字相加得到的新数列。

比如说第一行是 1，第二行是 1 + 1 = 2，第三行是 1 +2 + 1 = 4，以此类推。

接下来，咱们就进入正题，研究研究怎么通过递推公式来求这个杨辉三角垛列。

假设第 n 行的数字之和为 S(n)，那么我们来观察一下它的规律。

当 n = 1 时，S(1) = 1 ，这很明显。

当 n = 2 时，S(2) = 2 。

当 n = 3 时，S(3) = 4 。

这时候，聪明的你有没有发现点啥？没错，S(n)似乎和 2 的幂次有关系。

经过一番琢磨，我们可以得出递推公式：S(n) = 2^(n - 1) 。

这个公式是怎么来的呢？我们来仔细分析一下。

从杨辉三角的构造来看，每一行的数字之和都是上一行数字之和的2 倍。

为啥呢？因为每一行新增的数字都是由上一行相邻数字相加得到的，这就相当于把上一行的和翻了一倍。

比如说，第一行的和是 1，第二行是在第一行的基础上，左右两边各加了 1，所以和变成了 2 。

第三行呢，在第二行的基础上，又多了一些相加的部分，和就变成了 4 。

就拿我教过的一个学生来说吧，他一开始对这个递推公式怎么都理解不了。

我就给他画了好几遍杨辉三角，一个数字一个数字地给他解释相加的过程。

最后他恍然大悟，那种开心的表情，我到现在都还记得。

咱们再回到这个递推公式，有了它，要求杨辉三角垛列的任意一项，那就简单多啦。

题目：编写程序，根据输入的行数，屏幕显示杨辉三角形(Pascal’s triangle)班级：自动化05 姓名:刘丽丽学号：10054107 完成日期：2011.12.20 一．需求分析1、本演示程序中，利用顺序队列打印杨辉三角。

杨辉三角的特点是两个腰上的数字都为1，其它位置上的数字是其上一行中与之相邻的两个整数之和，故在打印过程中，第i行上的元素要由第i-1行中的元素来生成。

这是一个基于队列的操作来实现杨辉三角不断生成的过程。

2、此次输出的杨辉三角不需要只有一个1的第一行，但只需对输出实际杨辉三角的程序稍作修改即可；3、在计算机终端上显示"提示信息"之后，由用户在键盘上输入演示程序中需要输入的数据，以“回车符”为结束标志。

相应的输入数据和运算结果显示在其后。

4、程序执行的命令包括：1）构造顺序队列；2）分析第 i 行元素与第 i+1行元素的关系目的是从前一行的数据可以计算下一行的数据 从第i 行数据计算并存放第i+1行数据5、 测试数据输入行数 n=3； 输出结果为：1 11 2 1 1 3 3 1二． 概要设计链队列的抽象数据类型定义为： ADT Queue{ 数据对象 ：D={ai| ai ∈Elemset ，i=1,2,3，···n ，n ＞=0}11i = 1 1 2 121 3 3 13 14 6 4 141510 10 5 15 1 6152015 6 16数据关系：R={＜ai-1 ,ai＞| ai-1 ,ai∈D,i=1,2,···n} （约定其中ai端为队列头，an端为队列尾）基本操作：InitQueue（&Q）操作结果：构造一个空队列DestroyQueue（&Q）初始条件：队列已存在操作结果：队列被销毁ClearQueue（&Q）初始条件：队列已存在操作结果：将Q清空QueueEmpty（Q）若队为空，则返回为TRUE，否则返回为FALSE。

杨辉三角显示问题描述：编写程序，根据输入的行数，屏幕显示杨辉三角。

一、需求分析：1、行数不大于20行。

2、基于队列的操作来实现杨辉三角的不断生成过程。

（注：不要用其它的公式计算的方法或者二维数组来实现）3、基于数组实现队列的物理数据结构。

输入形式：输入一个整数n (行数不大于20)输出形式：打印出来前(n+1)行的杨辉三角数列功能实现：输出前20层的杨辉三角序列样例输入输出形式：输入：6输出：1 n=01 1 n=11 2 1 n=21 3 3 1 n=31 4 6 4 1 n=41 5 10 10 5 1 n=51 6 15 20 15 6 1 n=65、效率分析：O(n)二、概要设计：抽象数据类型void Queue::EnQueue(int item) //将元素item入列{QueueValue[++iLast]=item; } //入列int Queue::OutQueue() //第一个元素出列返回此元素{ return QueueValue[++iFront];}算法的基本思想：下面为主要实现生成杨辉三角的算法：Q.EnQueue(1); //第一行和第二行的生成Q.EnQueue(1);Q.EnQueue(1);cout<<Q.OutQueue()<<" n=0\n";for(i=3;i<=n+1;i++) //n行杨辉三角数的生成与输出 {Q.EnQueue(1);t1=Q.OutQueue();for(j=2;j<i;j++) //利用第n-1行的杨辉三角生成第n行的中间杨辉三角数{ t 2=t1;t1=Q.OutQueue(); //第n-1行第j个元素出列 Q.EnQueue(t1+t2); //第n行的第j个元素入列 cout<<t2<<" "; }Q.EnQueue(1); //第n行最后一个元素为1 cout<<t1<<" n="<<i-2<<endl; } //输出第n-1行最后1个元素Q.EnQueue(0); //以防队列为空while(--i) //输出最后一行cout<<Q.OutQueue()<<" ";cout<<" n="<<n<<endl;}程序的流程程序由三个模块组成：输入模块：输入一个整数n计算模块：栈和杨辉三角的算法输出模块：在屏幕上打印出来前(n+1)行的杨辉三角数列三、详细设计算法的具体步骤：算法思想已经在概要设计中提到了，现在通过基于队列基本操作的函数以及程序的模块化思想来实现杨辉三角的打印输出问题。

循环队列和杨辉三角（Cyclic queue and Yang Hui triangle）circulatequeue。

H：类circulatequeue{私人：int数据；/ /数组在前、后；/ /队头队尾指针，下标int长度；/ /队列长度const int ini_mem_length；/ /动态数组初始大小const int增量；/ /数组扩展增量/ / / /内存利用率const双率；国际current_mem_length；/ /当前数组内存单元大小公共：circulatequeue（int = 100，int = 10）；//构造~ circulatequeue() /析构{删除[ ]数据；}输出（void）；/ /输出，调试用无效enterqueue（int值）；/ /入队列int DeleteQueue（int值）；/ /出队列国际getqueuelength（void）/获取当前队列的长度{返回的长度；}int GetTop（int值）/取队头元素{如果（0 =长度）返回- 1；int i =（前+ 1）% current_mem_length；值=数据[ i ]；返回1；}}；CirculateQueue.cpp：#包括“circulatequeue。

”#包含iostream > <使用名称空间；circulatequeue：：CirculateQueue（int，int newsize，newincrement）：ini_mem_length（newsize）、增量（newincrement）{数据=新国际[ ini_mem_length ]；长度= 0；前面=后面= 0；current_mem_length = ini_mem_length；}无效circulatequeue：：输出（void）{如果（0 =长度）{cout <<“当前队列为空！“<<”不当前队列动态数组长度为：“<< current_mem_length << endl；}其他的{cout <<“当前队列长度为：“<<长<<“不当前队列动态数组长度为：“<< current_mem_length << end l；cout <<“当前队列内容为：”；int pos =（前+ 1）% current_mem_length；对于（int = i 1；i =长度；i + +）{cout <<数据【词性】<<“T”；POS =（POS + 1）% current_mem_length；cout << endl；}}无效circulatequeue：：enterqueue（int值）{如果（长度= =（current_mem_length-1））/ /{/ /int *温度=新国际[ current_mem_length +增量]；int pos =（前+ 1）% current_mem_length；对于（int = i 1，j = 1；i =长度；i +，+ +）/ i，j {温度=数据[ POS ]；POS =（POS + 1）% current_mem_length；}删除[ ]数据；数据=温度；前0；后=长度；current_mem_length = current_mem_length +增量；}后=（后+ 1）% current_mem_length；数据[后面] =值；长度+；}国际circulatequeue：：DeleteQueue（int值）{如果（0 =长度）/返回- 1；前=（前+ 1）% current_mem_length；值=数据[前]；长度-；返回0；}main.cpp：#包含iostream > <使用名称空间；#包括“circulatequeue。

#include<stdio.h>#include<malloc.h>#define Max 30typedef struct{int *base;int front;int rear;}SqQueue;int InitQueue(SqQueue &Q);//队列的初始化int EnQueue(SqQueue &Q,int e);//数据进队（从队尾传值）int DeQueue(SqQueue &Q,int &e);//数据出队（返回队头）void YHPrint(SqQueue &Q,int n);//打印杨辉int InitQueue(SqQueue &Q){Q.base=(int *)malloc(Max*sizeof(int));if(!Q.base)return 0;//储存分配失败Q.front=Q.rear=0;return 1;}int EnQueue(SqQueue &Q,int e){if((Q.rear+1)%Max==Q.front) return 0;//判断队满Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%Max; return 1;}int DeQueue(SqQueue &Q,int &e) {if(Q.front==Q.rear)//判断队空return 0;e=Q.base[Q.front];Q.front=(Q.front+1)%Max; return e;}void YHPrint(SqQueue &Q,int n) {int i,j,k,e,s1;for(i=1;i<=n;i++){for(k=0;k<n-i;k++)printf(" ");for(j=1,s1=0;j<i;j++){int s2;s2=DeQueue(Q,e);printf("%d",s1+s2);printf(" ");EnQueue(Q,s1+s2);s1=s2;}printf("1");EnQueue(Q,1);printf("\n");}}//主函数main(){int n,t;SqQueue Q;printf("杨辉三角：\n执行请输入：1，退出请输入：2！\n");scanf("%d",&t);do{switch(t){case 1:{InitQueue(Q);printf("请输入杨辉三角的层数：\n");scanf("%d",&n);YHPrint(Q,n);};break;case 2:printf("欢迎再次使用!");break; default:printf("输入错误：");break;}if(t==1){printf("请继续输入:1,退出请输入：2!\n");scanf("%d",&t);}}while(t==1);return 0;}【下载本文档，可以自由复制内容或自由编辑修改内容，更多精彩文章，期待你的好评和关注，我将一如既往为您服务】。

//----- 循环队列的顺序存储结构#define MAXQSIZE 100 //最大队列长度QElemType *base;int front;int rear;}SqQueue//-----循环队列的基本操作的函数原型说明-----Status InitQueue(ListQueue &Q) 构造一个空队列Status EnQueue(ListQueue &Q,e) 素e入队列QStatus DeQueue(ListQueue &S,&e) 出队列到元素e//-----循环队列的基本操作的算法描述-----Status InitQueue(SqQueue &Q){//构造一个空队列Q. base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));if (!Q.base) exit (OVERFLOW);Q.front = Q.rear = 0; //初始空队列return OK;}Status EnQueue(SqQueue &Q,QElemType e){//插入元素e为Q的新队尾元素if ((Q.rear+1)%MAXQSIZE == Q.front) return ERROR;Q.base[Q.rear] = e;Q.rear = (Q.rear+1)%MAXQSIZE;return OK;}Status DeQueue(SqQueue &Q,QElemType &e){//若队列不为空，删除队头元素用e返回，并返回OK//否则返回ERRORif (Q.front == Q.rear) return ERROR;e = Q.base[Q.front];Q.front = (Q.front +1)%MAXQSIZE;return OK;}void YANGVI ( int n ) {InitQueue(Q); //队列初始化EnQueue (Q,1); EnQueue (Q,1); //预放入第一行的两个系数for ( int i=1; i<=n; i++ ) { //逐行处理EnQueue (0); //两行之间增加一个标志0s=0;for ( int j=1; j<=i+2; j++ ) { //处理第i行的i+2个系数DeQueue (Q,e); //读取系数1EnQueue ( s+e ); //计算下一行系数，并进队列s = e;if ( j != i+2 ) printf(s); //打印一个系数，第i+2个为0 else printf(“\n”); //换行}}}//YANGVI。