首页 > 代码库 > 杭州电子科技大学 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]两个元素,所以无需把整行元素都记录下来,只需用两个变量迭代记录这两个元素值就行了。

可以设置两个变量leftright,分别存储preRow[j-1] preRow[j]的值,然后利用递推关系:curRow[j] = left +right;更新curRow[j]的值,并及时更新leftright的值。

算法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)”解题报告