编程思维训练7：杨辉三角

杨辉三角是一个经典的练习程序，要求输出：

1
1   1
1   2   1
1   3   3   1
1   4   6   4   1
1   5  10  10   5   1
1   6  15  20  15   6   1
1   7  21  35  35  21   7   1
1   8  28  56  70  56  28   8   1
1   9  36  84 126 126  84  36   9   1

常规的代码如下：

#include <stdio.h>
#define N 10
int main( ) {
	int a[N][N+1] = {{1},{1,1}};
	int i,j;
	for(i = 1 ; i < N ; i++) {
		a[i][0]=a[i][i]=1;
		for(j=1; j<i; j++)
			a[i][j]=a[i-1][j-1]+a[i-1][j];
	}
	for(i = 0 ; i < N ; i++) {
		for(j=0; j<=i; j++)
			printf("%4d",a[i][j]);
		printf("\n");
	}
}

也可以直接用组合公式C(n,m)计算每一项，代码如下：

#include <stdio.h>
#define N 10
int p(int n) {
	int t=1;
	for(int i=1; i<=n; i++)
		t*=i;
	return t;
}
int c(int n,int m) {
	int v=p(n)/p(m)/p(n-m);
	return v;
}
int main( ) {
	for(int i = 0 ; i < N ; i++) {
		for(int j=0; j<=i; j++)
			printf("%4d",c(i,j));
		printf("\n");
	}
}

其中组合的计算需要得到n、m、n-m三个数的阶乘，考虑到组合计算分子分母可以约简，程序调整如下：

#include <stdio.h>
#define N 10
int p(int begin,int end) {
	int t=1;
	for(int i=begin; i<=end; i++)
		t*=i;
	return t;
}
int c(int n,int m) {
	int v=p(m+1,n)/p(1,n-m);
	return v;
}
int main( ) {
	for(int i = 0 ; i < N ; i++) {
		for(int j=0; j<=i; j++)
			printf("%4d",c(i,j));
		printf("\n");
	}
}

其实，结合前面两种思路，也可以采用递归输出杨辉三角，代码如下：

#include <stdio.h>
#define N 10
int p(int begin,int end) {
	int t=1;
	for(int i=begin; i<=end; i++)
		t*=i;
	return t;
}
int c(int n,int m) {
	int v=p(m+1,n)/p(1,n-m);
	return v;
}
int a[N+1][N+1];
int print(int n) {
	if(n<0) return 0;
	else {
		a[n-1][0]=a[n-1][n]=1;
		for(int i=1; i<=n-1; i++)
			a[n-1][i]=a[n][i]-a[n-1][i-1];
		print(n-1);
		for(int i=0; i<=n; i++)
			printf("%4d",a[n][i]);
		printf("\n");
	}

}
int main( ) {
	for(int i = 0 ; i <= N ; i++) {
		a[N][i]=c(N,i);
	}
	print(N);
}

程序的思路是，先用组合数公式，计算最后一行数据，然后递归计算前一行，递归调用语句后不要忘记输出一行数据即可。递归计算前一行的公式正好与前面相反：

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