杨辉三角算法集锦Word文档下载推荐.docx

杨辉三角算法集锦Word文档下载推荐.docx

《杨辉三角算法集锦Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《杨辉三角算法集锦Word文档下载推荐.docx（12页珍藏版）》请在冰点文库上搜索。

voidFun_6（introw）;

voidFun_7（introw）;

voidFun_8（introw）;

voidFun_9（introw）;

intmain（）

{

introw;

cin>

>

row;

Fun_1（row）;

cout

Fun_2（row）;

Fun_3（row）;

Fun_4（row）;

Fun_5（row）;

Fun_6（row）;

Fun_7（row）;

Fun_8（row）;

Fun_9（row）;

system（

return0;

}

//输出n个空格

voidPrintBlank（intn）

for（inti=0;

i

//使用二维数组输出杨辉三角

voidFun_1（introw）

constintDIS=6;

intblank=32;

inta[MAXROW][MAXROW]={0};

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];

if（j==i）

//使用队列输出杨辉三角

voidFun_2（introw）

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行尾部

//队尾进入第i+1行

front=（front+1）%max;

//对头进入第i行PrintBlank（blank-=DIS/2）;

//处理中间数据

a[rear]=a[front]+a[（front+1）%max];

if（front!

=rear）//队列非空时输出

//删除对头元素

delete[]a;

//使用两个一维数组代替二维数组输出杨辉三角

voidFun_3（introw）

intblank=33;

int*a=newint[row];

//存储下一行

int*b=newint[row];

//存储输出行

b[0]=1;

for（intn=1;

n

//输出第n行

if（n==row）//已经到最后一行则不再复制

continue;

//生成第n+1行数据

a[0]=b[0];

for（inti=1;

a[i]=b[i]+b[i-1];

a[n]=1;

//复制第n+1行数据

b[i]=a[i];

delete[]b;

//使用一个一维数组和两个临时变量代替二维数组输出杨辉三角：

很巧妙voidFun_4（introw）

//存储输出行

intleft,right;

//输出第一行

//输出第1行空格

//左侧数据永远为1

left=a[0];

//生成第n行数据

right=a[i];

a[i]=left+right;

//left=a[i-1]，right=a[i]

left=right;

//设置右侧的数据1

方法同Fun_4，但更具有技巧，有点难懂

voidFun_5（introw）

left=0;

//使用一个一维数组输出杨辉三角；

两侧的1不变，计算中间的元素voidFun_6（introw）

//最左侧为1，永远不变

//设置最右侧的1

for（inti=n-1;

i>

0;

i--）//设置中间的元素，由于a[i]的值变化，故应从右到左计算

a[i]+=a[i-1];

//杨辉三角的规律

//输出第n+1行

//使用二项式定理输出杨辉三角

voidFun_7（introw）

//输出组合c（n,m）

intCom（intn,intm）

ints1=1;

ints2=1;

m=（m>

n/2）?

（n-m）:

m;

//取小的，以减少计算量

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）

intc=1;

for（intm=1;

m

c=c*（n-m+1）/m;

//使用递归方法输出杨辉三角:

C（n,k）=1（k=0或者n=k）;

C（n,k）=C（n-1,k-1）+C（n-1,k）

voidFun_9（introw）

for（intn=0;

for（intm=0;

//递归函数，输出杨辉三角:

intTry（intn,intk）

if（k==0||k==n）//在左右两侧返回1

return1;

returnTry（n-1,k-1）+Try（n-1,k）;

//递推公式