杨辉三角
问题描述
编写程序,根据输入的行数,屏幕显示杨辉三角。
基本要求
(1) 行数不大于20行。
(2) 基于队列的操作来实现杨辉三角的不断生成过程。(注:不要用其它的公式计算的方法或者二维数组来实现)
(3) 基于数组实现队列的物理数据结构。
输入输出
输入 n= 6
输出
1 n=0
1 1 n=1
1 2 1 n=2
1 3 3 1 n=3
1 4 6 4 1 n=4
1 5 10 10 5 1 n=5
1 6 15 20 15 6 1 n=6
概要设计:
基本操作:
SeqQueue()
操作结果:构造一个空队列Q
makeEmpty()
初始条件:队列Q已存在
操作结果:将Q清为空队列
IsEmpty()
初始条件:队列Q已存在
操作结果:若Q为空队列,则返回TRUE,否则FALSE
getSize()
初始条件:队列Q已存在
操作结果:返回Q的元素个数,即队列长度
EnQueue(const T& x)
初始条件:队列Q已存在
操作结果:若队列不满,则将x进队,否则一处处理
DeQueue(T& x);
初始条件:Q为非空队列
操作结果:删除Q的队头元素,并用x返回其值
具体程序
#include "stdlib.h"
#include "stdio.h"
#define OK 1
#define error 0
#define maxsize 100
typedef int Qelemtype;
typedef int status;
typedef struct{
Qelemtype *base;
int f;
int r;
}Squeue;
status InitQueue(Squeue & Q)
{
Q.base=(Qelemtype*)malloc(maxsize*sizeof(Qelemtype));
Q.base=new(Qelemtype);
if(!Q.base)return error;
Q.f=Q.r=0;
return OK;
}
int Queuelength(Squeue & Q)
{
return (Q.r-Q.f+maxsize)%maxsize;
}
status EnQueue(Squeue & Q,Qelemtype e)
{
if((Q.r+1)%maxsize==Q.f)
{
printf("队列已满\n");
return error;
}
Q.base[Q.r]=e;
Q.r=(Q.r+1)%maxsize;
return OK;
}
status DeQueue(Squeue & Q,Qelemtype &e)
{
if(Q.f==Q.r)
{
printf("队列已空\n");
return error;
}
e=Q.base[Q.f];
Q.f=(Q.f+1)%maxsize;
return OK;
}
void YangHui(int n)
{
Squeue q; //建立队列对象
int i=1,j,s=0,t,u; //计算下一行系数时用到的工作单元
InitQueue(q);
printf("\n 1");
EnQueue(q,1);
EnQueue(q,1); //预先放入第一行的两个系数
for(i=1;i<=n;i++) //逐行处理
{
printf("\n"); //换一行
EnQueue(q,0); //各行间插入一个
for(j=1;j<=i+2;j++) //处理第i行的i+2个系数(包括一个)
{
DeQueue(q,t); //读取一个系数
u=s+t;
EnQueue(q,u); //计算下一行系数,并进队列
s=t;
if(j!=i+2)
printf("%3d",s); //打印一个系数,第i+2个是
}
}
}
void main() //主函数
{
int n;
printf("输入n=");
scanf("%d",&n);
printf("输出:");
YangHui (n);
printf("\n");
system("pause");
}
运行结果:
算法的时空分析
时间复杂度为O(N)
输入输出格式
输入:
直接输入想要行数n
输出:如果输入小于条件给予的20,则显示如题所要求的杨辉三角
展开阅读全文