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