九度题目1073：杨辉三角形

题目1073：杨辉三角形
时间限制：1 秒内存限制：32 兆特殊判题：否提交：2903解决：1259
题目描述：
输入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套)

AC代码：
方法一：
一般数组方法：

#include<stdio.h>
#include<string.h>
int a[100][100];
void Fun(int n)
{
     int i,j,m=1;
     while(m<n)
     {
        for(i=0;i<m;i++)
        {
           if(i==0||i==m-1)
           a[m][i]=1;
           else
           {
               a[m][i]=a[m-1][i-1]+a[m-1][i];
           }
        }
        m++;
     }
     for(i=0;i<n;i++)
     {
         if(i==0||i==1)
         continue;
         printf("%d",a[i][0]);
         for(j=1;j<i;j++)
         printf(" %d",a[i][j]);
         puts("");
     }
}
int main()
{
    int i,j,n,m;
    while(scanf("%d",&n)!=EOF)
    {
       memset(a,0,sizeof(a));
       Fun(n+1);
    }
    return 0;
}

方法二：

递归法（注意利用数组优化）：

#include<stdio.h>
#include<string.h>
int a[100][100];
int Fun(int n,int m)
{
     if(a[n][m]!=0)//之前已经计算过的值，下次再次调用的时候就没有必要再次递归运算了
     return a[n][m];
     if(m==1)
     return 1;
     if(m==n)
     return 1;
     else
     {
         a[n][m]=Fun(n-1,m)+Fun(n-1,m-1);
         return a[n][m];
     }
}
int main()
{
    int i,j,n,m;
    while(scanf("%d",&n)!=EOF)
    {
       memset(a,0,sizeof(a));
       for(i=1;i<=n;i++)
       {
          if(i==1) continue;
          for(j=1;j<=i;j++)
          {
             if(j!=1)
             printf(" ");
             printf("%d",Fun(i,j));
          }
          puts("");
       }
    }
    return 0;
}