用循环队列获得杨辉三角
中国古代数学史曾经有代写论文自己光辉灿烂的篇章，而杨辉三角的发现就是十分精彩的一页。杨辉三角是中国古代数学家贾宪在公元11世纪发现，并被南宋数学家杨辉在他的书中所引述，才使我们今天得以了解贾宪在数学上的重大贡献。杨辉三角是一个由数字排列成的三角形数表.一般形式如下:
1
1 1
1 2 1
1 3 3 1
....
..
杨辉三角，我相信大家都知道。其实在高中数列中应该就用详细介绍了。在高中数学中如果用A(m,n)表示杨辉三角中的第m行第n列的元素，那么表示杨辉三角的表达式如文件1.png
那么在这里我想用我们学过的队列来实现这个获得过程

其基本算法如下：
假设n行
当n=1时将1入队
当n>=2时当生成第n行第j个时
如果j=1时，将1入队
如果j=n时，将1入队，并将队列第一个出对
当1<j<n时，将队列第一个出对记录其值并和此时队列第一个元素的和入队
其图示如文件2.png
首先得实现MyQuen类，自己定义的队列MyQuen.h

#pragma once//这是visual studio 2010中只编译一次的语句            //相当于visual C++ 6.0中 #ifndef ...              //                       #define ...            //                       #endif#include<iostream>using namespace std;const int Maxsize = 30;template<class Elem>class MyQuen{public:MyQuen();//构造空队列~MyQuen();void AddElem(Elem e);//元素e入队列void DeleElem(Elem &e);//队首元素出队，并用e保存bool IsEmpty();//是否为空队，是则返回true,否则返回falsebool IsFull();//是否为满队，是则返回true,否则返回falseElem GetFrontVal();//返回队首元素的值private:Elem Array[Maxsize];//存储队列元素，采用数组int front;//队首int rear;//队尾};template<class Elem>MyQuen<Elem>::MyQuen(){front = 0;rear = 0;}template<class Elem>MyQuen<Elem>::~MyQuen(){}template<class Elem>void MyQuen<Elem>::AddElem(Elem e){if(!IsFull()){Array[rear++] = e;if(rear == Maxsize){rear = 0;}}else{cerr<<"队列已满"<<endl;exit(1);}}template<class Elem>void MyQuen<Elem>::DeleElem(Elem &e){if(!IsEmpty()){e = Array[front++];if(front == Maxsize){front = 0;}}else{cerr<<"队列已空"<<endl;exit(1);}}template<class Elem>bool MyQuen<Elem>::IsFull(){return !((rear-front+Maxsize+1)%Maxsize);}template<class Elem>bool MyQuen<Elem>::IsEmpty(){return front == rear;}template<class Elem>Elem MyQuen<Elem>::GetFrontVal(){return Array[front];}

然后就是实现杨辉三角的函数

void YanghuiTri(int num)//num表示要显示的行数{MyQuen<int> mq;int x;for(int i = 0;i <= num;i++)//表示行{for(int j = 0;j <= i;j++)//表示列{if(j == 0){mq.AddElem(1);//第一个元素将1加入队列}else if(j == i){mq.AddElem(1);//每行最后一个将1入队列mq.DeleElem(x);//将上一行最后一个出队cout<<x<<"  ";cout<<"第"<<i<<"行"<<endl;}else{mq.DeleElem(x);//出队上一行cout<<x<<" ";mq.AddElem(x+mq.GetFrontVal());//将此时队首元素+刚出队的元素入队}}}}

最后就是主函数main.cpp

#include"MyQuen.h"#include<iostream>using namespace std;void YanghuiTri(int num);int main(){int n;cout<<"请输入要显示的行数:";cin>>n;YanghuiTri(n);         return 0;}

运行结果如文件3.png
该列子只能显示杨辉三角的前27行，这是由于数组开辟的内存有限所致。这个只需修改MyQuen.h中的Maxsize的值