首页 > 代码库 > 杭州电子科技大学 Online Judge 之 “杨辉三角(ID2032)”解题报告
杭州电子科技大学 Online Judge 之 “杨辉三角(ID2032)”解题报告
杭州电子科技大学 OnlineJudge之 “杨辉三角(ID2032)”解题报告
巧若拙(欢迎转载,但请注明出处:http://blog.csdn.net/qiaoruozhuo)
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"); } }
杭州电子科技大学 Online Judge 之 “杨辉三角(ID2032)”解题报告