一. 前言
杨辉三角大概在初中就接触到了，在学习数据结构的时候再一次遇到，将所学的内容整理如下：
二. 杨辉三角简介
杨辉三角形，又称贾宪三角形、帕斯卡三角形、海亚姆三角形、巴斯卡三角形，是二项式系数在的一种写法，形似三角形，在中国首现于南宋杨辉的《详解九章算术》得名，书中杨辉说明是引自贾宪的《释锁算术》，故又名贾宪三角形
三. 相关知识点
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
五. 代码实现
我们可以利用队列的知识，实现杨辉三角
#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;
}
请登录之后再进行评论