九度OJ 1073：杨辉三角形 （递归）

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：3780

解决：1631

题目描述：

输入n值，使用递归函数，求杨辉三角形中各个位置上的值。

输入：

一个大于等于2的整型数n

输出：

题目可能有多组不同的测试数据，对于每组输入数据，
按题目的要求输出相应输入n的杨辉三角形。

样例输入：

6

样例输出：

1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

来源：

2002年清华大学计算机研究生机试真题(第I套)

思路：

用函数递归会超时。

用数组递归，可以利用前面的计算结果，效率比较高。

代码：

#include <stdio.h>
#include <string.h>
/*
int yanghui(int x, int y)
{
    if (y == 1)
        return 1;
    if (x == y)
        return 1;
    return yanghui(x-1, y-1) + yanghui(x-1, y);
}
*/
int main(void)
{
    int i, j, n;
    int a[1000][1000];
 
    while (scanf("%d", &n) != EOF)
    {
        for (i=2; i<=n; i++)
        {
            for (j=1; j<=i; j++)
            {
                if (j == 1 || i == j)
                    a[i][j] = 1;
                else
                    a[i][j] = a[i-1][j-1] + a[i-1][j];
                printf("%d", a[i][j]);
                if (i != j)
                    printf(" ");
            }
            printf("
");
        }
    }
 
    return 0;
}
/**************************************************************
    Problem: 1073
    User: liangrx06
    Language: C
    Result: Accepted
    Time:10 ms
    Memory:4744 kb
****************************************************************/