递推算法4——顺推法之杨辉三角问题

【定义】

杨辉三角也称贾宪三角，具有二项展开式的二项式系数即组合数的性质，这是研究杨辉三角其他规律的基础。杨辉三角具有以下性质：

（1）每行数字左右对称，由1开始逐渐变大，然后变小，返回1。
（2）第n行的数字个数为n个。
（3）第n行的数字之和为 2^(n-1)。
（4）每个数字等于上一行的左右两个数字之和，即 C_n^1 = C_{n-1}^{i-1} +  C_{n-1}^{i}。
（5）第n行的第1个数为1，第2个数为1×(n-1)，第3个数为1×(n-1)×(n-2)/2，第4个数为1×(n-1)×(n-2)×(n-3)/3，依此类推。

一个八阶的杨辉三角如图所示。

【算法思想】

为了程序设计实现上的方便可以使用二维数组存放杨辉三角中的每一个元素。初始时，将第一列和对角线上的元素初始化为1，即a[i][0]=a[i][i]=1。

然后利用每一行元素值是它上一行两个相邻元素之和求其他部分的元素值，即a[i][j]=a[i-1][j]+a[i-1][j-1]。最后将二维数组按行输出即可。

code：

#include<stdio.h>
#include <iostream>
#define N 8
void main()
{
	int a[N + 1][N + 1], i, j;
	for (i = 0; i <= N; i++)
		a[i][i] = a[i][0] = 1;
	for (i = 2; i <= N; i++)
		for (j = 1; j < i; j++)
			a[i][j] = a[i - 1][j] + a[i - 1][j - 1];
	printf("%d阶杨辉三角如下:\n", N + 1);
	for (i = 0; i <= N; i++)
	{
		for (j = 0; j <= i; j++)
			printf("%3d", a[i][j]);
		printf("\n");
	}
	system("pause");
}

结果：