（递归）杨辉三角实现

问题描述

杨辉三角形又称Pascal三角形，它的第i+1行是(a+b)i的展开式的系数。

它的一个重要性质是：三角形中的每个数字等于它两肩上的数字相加。

下面给出了杨辉三角形的前4行：

1

1 1

1 2 1

1 3 3 1
———————————————

思路：可以用二维数组实现，且二维数组第一列和最后一列全为1，从第三列开始，每个数等于上面两个数之和即f（x，y）=f（x-1，y-1）+f（x-1，y）

实现：使用递归实现当不为第一列或最后一列（即y等于0或x等于y时），递归调用自身实现。使用双层for循环嵌套遍历调用递归函数，求出每个位置的数且输出。

代码:

#include<bits/stdc++.h>
int f(int x,int y){
	if(y==0||x==y)
	return 1;
	else {
		return f(x-1,y-1)+f(x-1,y);
	}
}
using namespace std;
int main(){
	int a[100][100];
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++)
		cout<<f(i,j)<<" ";
		cout<<endl;
	} 
	return 0;  
} 

--------------------------------------------------------------------------------------------------

2022.10.23

突然发现使用递归容易超时，还是老老实实用for吧

#include<bits/stdc++.h>
using namespace std;
int main(){
	int a[100][100];
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
        a[i][0]=1;
        for(int j=1;j<=i;j++){
            a[i][j]=a[i-1][j]+a[i-1][j-1];
        }
    }
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++)
		cout<<a[i][j]<<" ";
		cout<<endl;
	} 
	return 0;  
}