杭州电子科技大学 Online Judge 之 “杨辉三角（ID2032）”解题报告
杭州电子科技大学 Online Judge 之 “杨辉三角（ID2032）”解题报告巧若拙（欢迎转载，但请注明出处：http://blog.）
Problem Description
还记得中学时候学过的杨辉三角吗？具体的定义这里不再描述，你可以参考以下的图形：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Input
输入数据包含多个测试实例，每个测试实例的输入只包含一个正整数n（1<=n<=30），表示将要输出的杨辉三角的层数。
Output
对应于每一个输入，请输出相应层数的杨辉三角，每一层的整数之间用一个空格隔开，每一个杨辉三角后面加一个空行。
Sample Input
2 3
Sample Output
1
1 1
1
1 1
1 2 1
算法分析：
本题可以看作是动态规划算法的简单应用。根据空间复杂度的不同，我写了4个不同的实现方法。
算法1：采用最原始的动态规划思维，用一个二维数组把杨辉三角各行元素都记录下来。从第一行开始，利用递推关系：a[i][j] = a[i-1][j-1] + a[i-1][j]; 计算出下一行的元素值。
算法2：观察递推关系，注意到第i行元素值由第i-1行确定，所以没必要把每一行的元素值都记录下来，只需记录两行就够了。我们可以用两个一维数组记录杨辉三角上一行和当前输出行元素，利用递推关系：curRow[j] = preRow[j-1] + preRow[j];计算即可。
注意，每行元素输出后要及时把curRow[j]的值复制到preRow[j]中，以便迭代计算。
算法3：进一步观察递推关系，我们发现只需用到上一行的preRow[j-1] 和 preRow[j]两个元素，所以无需把整行元素都记录下来，只需用两个变量迭代记录这两个元素值就行了。
可以设置两个变量left和right，分别存储preRow[j-1] 和 preRow[j]的值，然后利用递推关系：curRow[j] = left + right;更新curRow[j]的值，并及时更新left和right的值。
算法4：算法3中之所以需要两个变量，是因为preRow[j-1] 和 preRow[j]的值都被更新了，需要先把它们记录下来，才能得到curRow[j]的值。如果我们从右往左处理，那被更新的元素就只有preRow[j]，而preRow[j]由curRow[j]替代，即使被更新了也不影响推导curRow[j]的值。所以我们可以从右往左计算curRow[j]的值，这样根本无需用额外的变量来记录preRow[j-1] 和 preRow[j]的值。
说明：
算法思想：动态规划。
数据结构：数组，基本数据类型。
时间复杂度： 算法1O(n*n)，其他算法O(n)。
12464653 2014-12-11 14:05:25 Accepted 2032
0MS 1060K 937 B
C 巧若拙
12464646 2014-12-11 14:04:39 Accepted 2032
15MS 1072K 983 B
C 巧若拙
12464635 2014-12-11 14:03:37 Accepted 2032
0MS 1064K 1034 B
C 巧若拙
12464617 2014-12-11 14:02:10 Accepted 2032
0MS 1060K 831 B
C 巧若拙
代码如下：
#include<stdio.h>
#define MAXROW 30
void Triangle_1(int row);//使用二维数组记录杨辉三角各行元素
void Triangle_2(int row);//使用两个一维数组记录杨辉三角上一行和输出行元素
void Triangle_3(int row);//使用一个一维数组和两个变量输出杨辉三角
void Triangle_4(int row);//使用一个一维数组从右往左记录杨辉三角
int main()
{
int n;
while (scanf("%d", &n) != EOF)
{
Triangle_1(n);
printf("\n");
}
return 0;
}
void Triangle_1(int row)//使用二维数组记录杨辉三角各行元素
{
int a[MAXROW+1][MAXROW+1] = {1};
int i, j;
for (i=1; i<=row; i++) //记录各行元素
{
for (j=1; j<=i; j++)
{
a[i][j] = a[i-1][j-1] + a[i-1][j];
printf("%d", a[i][j]);
if (j < i)
printf(" ");
}
printf("\n");
}
}
void Triangle_2(int row)//使用两个一维数组记录杨辉三角上一行和输出行元素
{
int preRow[MAXROW+1] = {0};//存储上一行元素
int curRow[MAXROW+1] = {0};//存储输出行元素
int i, j;
preRow[1] = 1; //初始化数据
for (i=1; i<=row; i++) //记录各行元素
{
for (j=1; j<=i; j++)
{
curRow[j] = preRow[j-1] + preRow[j];
}
for (j=1; j<=i; j++)
{
preRow[j] = curRow[j];
printf("%d", curRow[j]);
if (j < i)
printf(" ");
}
printf("\n");
}
}
void Triangle_3(int row)//使用一个一维数组和两个变量输出杨辉三角
{
int curRow[MAXROW+1] = {0};//存储输出行元素
int i, j, left, right;
curRow[1] = 1; //初始化数据
for (i=1; i<=row; i++)
{
left = 0; //初始化数据
for (j=1; j<=i; j++)//记录输出行元素
{
right = curRow[j];
curRow[j] = left + right;
printf("%d", curRow[j]);
if (j < i)
printf(" ");
left = right;
}
printf("\n");
}
}
void Triangle_4(int row)//使用一个一维数组从右往左记录杨辉三角
{
int curRow[MAXROW+1] = {0};//存储输出行元素
int i, j;
curRow[1] = 1; //初始化数据
for (i=1; i<=row; i++)
{
for (j=i; j>=1; j--) //从右往左记录输出行元素
{
curRow[j] += curRow[j-1];
}
for (j=1; j<=i; j++)
{
printf("%d", curRow[j]);
if (j < i)
printf(" ");
}
printf("\n");
}
}
