九度题目1073:杨辉三角形

  1. 云栖社区>
  2. 博客>
  3. 正文

九度题目1073:杨辉三角形

光仔december 2014-05-15 20:21:00 浏览900
展开阅读全文
题目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;
}

网友评论

登录后评论
0/500
评论
光仔december
+ 关注