杨辉三角算法集锦.docx
《杨辉三角算法集锦.docx》由会员分享，可在线阅读，更多相关《杨辉三角算法集锦.docx（12页珍藏版）》请在冰点文库上搜索。
杨辉三角算法集锦
杨辉三角算法集锦
/*
Name:
杨辉三角算法集锦
分别使用了二维数组，一维数组，队列，二项式公式，组合公式推论和递归方法等9种算法
*/
#include
#include
usingnamespacestd;
constintMAXROW=40;
voidPrintBlank（intn）;
intCom（intn,intm）;
intTry（introw,intcel）;
voidFun_1（introw）;
voidFun_2（introw）;
voidFun_3（introw）;
voidFun_4（introw）;
voidFun_5（introw）;
voidFun_6（introw）;
voidFun_7（introw）;
voidFun_8（introw）;
voidFun_9（introw）;
intmain（）
{
introw;
cin>>row;
Fun_1（row）;
cout
Fun_2（row）;
cout
Fun_3（row）;
cout
Fun_4（row）;
cout
Fun_5（row）;
cout
Fun_6（row）;
cout
Fun_7（row）;
cout
Fun_8（row）;
cout
Fun_9（row）;
system（
return0;
}
//输出n个空格
voidPrintBlank（intn）
{
for（inti=0;i
cout
}
//使用二维数组输出杨辉三角
voidFun_1（introw）
{
constintDIS=6;
intblank=32;
inta[MAXROW][MAXROW]={0};
for（inti=0;i
{
PrintBlank（blank-=DIS/2）;//输出第i行空格
for（intj=0;j
{
if（j==0||j==i）
a[i][j]=1;
else//规律:
左上与正上元素之和
a[i][j]=a[i-1][j-1]+a[i-1][j];
cout
if（j==i）
cout
}
}
}
//使用队列输出杨辉三角
voidFun_2（introw）
{
constintDIS=6;
intmax=row+2;
intblank=30;
int*a=newint[max];
intfront,rear;
front=0;a[0]=1;
rear=1;a[1]=1;
PrintBlank（blank）;//输出第一行空格
while（front!
=（rear+1）%max）
{
if（a[front]==1&&a[（front+1）%max]==1）//到i-1行尾部{
rear=（rear+1）%max;a[rear]=1;//第i行尾部
rear=（rear+1）%max;a[rear]=1;//队尾进入第i+1行
cout
front=（front+1）%max;//对头进入第i行PrintBlank（blank-=DIS/2）;//输出第i行空格
}
//处理中间数据
rear=（rear+1）%max;a[rear]=a[front]+a[（front+1）%max];if（front!
=rear）//队列非空时输出
cout
front=（front+1）%max;//删除对头元素
}
delete[]a;
}
//使用两个一维数组代替二维数组输出杨辉三角
voidFun_3（introw）
{
constintDIS=6;
intblank=33;
int*a=newint[row];//存储下一行
int*b=newint[row];//存储输出行
b[0]=1;
for（intn=1;n
{
//输出第n行
PrintBlank（blank-=DIS/2）;
cout
cout
if（n==row）//已经到最后一行则不再复制
continue;
//生成第n+1行数据
a[0]=b[0];
for（inti=1;i
a[i]=b[i]+b[i-1];
a[n]=1;
//复制第n+1行数据
for（inti=0;i
b[i]=a[i];
}
delete[]a;
delete[]b;
}
//使用一个一维数组和两个临时变量代替二维数组输出杨辉三角：
很巧妙voidFun_4（introw）
{
constintDIS=6;
intblank=30;
int*a=newint[row];//存储输出行
intleft,right;
//输出第一行
PrintBlank（blank）;//输出第1行空格
cout
a[0]=1;//左侧数据永远为1
for（intn=1;n
{
left=a[0];
//生成第n行数据
for（inti=1;i
{
right=a[i];
a[i]=left+right;//left=a[i-1]，right=a[i]
left=right;
}
a[n]=1;//设置右侧的数据1
//输出第n行
PrintBlank（blank-=DIS/2）;
cout
cout
}
delete[]a;
}
//使用一个一维数组和两个临时变量代替二维数组输出杨辉三角：
方法同Fun_4，但更具有技巧，有点难懂
voidFun_5（introw）
{
constintDIS=6;
intblank=33;
int*a=newint[row];//存储输出行
for（inti=1;i
a[0]=1;
intleft,right;
for（intn=1;n
{
left=0;
//生成第n行数据
for（inti=0;i
{
right=a[i];
a[i]=left+right;//left=a[i-1]，right=a[i]
left=right;
}
//输出第n行
PrintBlank（blank-=DIS/2）;
for（inti=0;i
cout
cout
}
delete[]a;
}
//使用一个一维数组输出杨辉三角；两侧的1不变，计算中间的元素voidFun_6（introw）
{
constintDIS=6;
intblank=30;
int*a=newint[row];
//输出第一行
PrintBlank（blank）;//输出第1行空格
cout
a[0]=1;//最左侧为1，永远不变
for（intn=1;n
{
a[n]=1;//设置最右侧的1
for（inti=n-1;i>0;i--）//设置中间的元素，由于a[i]的值变化，故应从右到左计算
{
a[i]+=a[i-1];//杨辉三角的规律
}
//输出第n+1行
PrintBlank（blank-=DIS/2）;
for（inti=0;i
cout
cout
}
delete[]a;
}
//使用二项式定理输出杨辉三角
voidFun_7（introw）
{
constintDIS=6;
intblank=30;
//输出第一行
PrintBlank（blank）;//输出第1行空格
cout
for（inti=1;i
{
PrintBlank（blank-=DIS/2）;//输出第i行空格
for（intj=0;j
{
cout
}
cout
}
//输出组合c（n,m）
intCom（intn,intm）
{
ints1=1;
ints2=1;
m=（m>n/2）?
（n-m）:
m;//取小的，以减少计算量
for（inti=1;i
{
s1*=n;
s2*=i;
if（s1%s2==0）//防止溢出
{
s1/=s2;
s2=1;
}
n--;
}
returns1;
}
//使用组合公式推论输出杨辉三角:
C（n,m）=（n-m+1）/m*C（n,m-1）voidFun_8（introw）
{
constintDIS=6;
intblank=30;
//输出第一行
PrintBlank（blank）;//输出第1行空格
cout
for（intn=1;n
{
intc=1;
PrintBlank（blank-=DIS/2）;//输出第i行空格
cout
for（intm=1;m
{
c=c*（n-m+1）/m;
cout
}
cout
}
//使用递归方法输出杨辉三角:
C（n,k）=1（k=0或者n=k）;C（n,k）=C（n-1,k-1）+C（n-1,k）
voidFun_9（introw）
{
constintDIS=6;
intblank=33;
for（intn=0;n
{
PrintBlank（blank-=DIS/2）;//输出第i行空格
for（intm=0;m
{
cout
}
cout
}
}
//递归函数，输出杨辉三角:
C（n,k）=1（k=0或者n=k）;C（n,k）=C（n-1,k-1）+C（n-1,k）
intTry（intn,intk）
{
if（k==0||k==n）//在左右两侧返回1
return1;
returnTry（n-1,k-1）+Try（n-1,k）;//递推公式
}
升级会员 