问题描述

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

问题分析

Problem Analyse

本题是为C语言初学者提供的。

Algorithm Analyse

把杨辉三角压缩进数组中，就会发现它的规律:

f(i, i) = f(i, 1) = 1 (i < 0)
f(i, j) = f(i-1, j) + f(i-1, j-1) (j < i)

或者 f(i, j) = C^j_i

算法实现

因为f(i, j) = f(i-1, j) + f(i-1, j-1)，所以我们在编程的时候，完全可以只开一个一维数组。从i倒退到1，执行A[j] += A[j-1];这样就得到第i行的结果了~

参考源码