65
九度题目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;
}
最后更新：2017-04-03 12:56:41