前言
本篇文章主要讲述通过队列打印输出杨辉三角的思想及C/C++的代码实现,希望阅读本篇文章以后大家有所收获,帮助大家对相关内容的理解更加深入。
杨辉三角
杨辉三角是公元1261年,我国宋代数学家杨辉在其著作《详解九章算法》中给出的一个用数字排列起来的三角形阵。由于杨辉在书中引用了贾宪著的《开方作法本源》和“增乘开方法”,因此这个三角形也称“贾宪三角”。在欧洲,这个三角形叫帕斯卡三角形,是帕斯卡在1654年研究出来的,比杨辉晚了近400年时间。
——以上介绍引用文章zhuanlan.zhihu.com/p/55686745。
下面是杨辉三角的规律图
特点
1、第一行有 1 个元素,第 n 行有 n 个元素
2、每一行的第一个元素和最后一个元素都是 1
3、从第三行开始,除去首尾位置的元素,每个元素等于上方元素与左上方元素之和
根据这些特点,我们可以直接使用循环来输出杨辉三角,不会绕什么弯子,实现起来应该很简单。
但今天笔者想说说队列实现杨辉三角的思想,那么让我们开始吧。
实现
思想
我们根据特点3知道杨辉三角“除去首尾位置的元素,每个元素等于上方元素与左上方元素之和”,我们想一想有没有什么办法让首尾元素也按照这个规律,这样的话规律就更加统一了。再让我们看看杨辉三角的规律图能不能发现什么规律。我们可以发现只要在每行的首尾位置都补上0,那么我们在杨辉三角中首尾元素的1也可以按照这个规律计算出来。
那么就很棒了,我们直接就可以通过计算出前后两个元素,得到下一行的元素,同时输出出来,依次向后计算,最后这就得到了下一行的所有元素。我们都知道队列的特性是先进先出。利用这个特性我们将第i行存进去,用来计算i+1行,依次下去。那为了杨辉三角继续循环运算得到第n行,我们同时也需要将得到的下一行(i+1行)的所有元素依次入队列。
过程图:箭头表示出队,黄色表示新入队列的元素。曲线表示前后两个元素。
最终队列里的元素,总是上一行的结果。
代码实现
代码逻辑:从第二行开始,先入队一个辅助元素0,作为下一行的首辅助元素与这一行的尾辅助元素。内层循环先删除当前队列的头元素,再得到删除操作后当前队列的头元素,计算两元素之和并输出,同时入队。内层列循环直到遍历到下一个的辅助元素时,退出该循环完成当前行的打印。紧接着继续行循环,向下打印每一行。
#include "pubuse.h"
typedef int QElemType;
#include "LinkQueuedef.h"
#include "LinkQueueAlgo.h"
#include "stdlib.h"
#include <iostream>
#include <string>
using namespace std;
string indent(int count);
void yanghui(int n)
{ /* 打印n行杨辉三角 */
LinkQueue q; int i , j , s , t ;
InitQueue(q);
EnQueue(q,0);//第一行的元素先入栈,0用于辅助计算。
EnQueue(q,1);
printf("%s%d/n",indent(n).c_str(),1);//打印第一行
for(i=2;i<=n;i++)
{ EnQueue(q,0);//0入栈
std::cout<<(char*)(indent(n-i+1).c_str());//缩进
for(j=1; j<=i ; j++)
{ DeQueue(q,s); //出队
GetHead_Q(q,t);//得到头元素
printf("%d%s",s+t,indent(1).c_str());//输出下一行对应的元素
EnQueue(q,s+t );//入队
}
printf("/n");
}
}
string indent(int count)
{
string str="";
for (int i = 0; i < count; i++)
{
str.append(" ");
}
return str;
}
int main( )
{int i,j;
LinkQueue q;
i=InitQueue(q);
if (i)
printf("成功地构造了一个空队列!/n");
printf("请输入要打印的杨辉三角的行数:");
scanf("%d",&j);
yanghui(j);
return 0;
}
为了更加直观的输出杨辉三角,其中indent
函数用于计算缩进间距。
代码里面队列是自己实现的,依赖了
#include "pubuse.h"
typedef int QElemType;
#include "LinkQueuedef.h"
#include "LinkQueueAlgo.h"
大家主要看yanhui函数里面的逻辑即可,这里提供源代码,如有需要可以下载下来研究。
效果