题目描述
杨辉三角形
如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如下数列:
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, …
给定一个正整数 N
,请你输出数列中第一次出现 N
是在第几个数?
样例
输入
6
输出
13
算法1
(暴力枚举) $O(n^2)$
传统写法肯定会爆掉,但是可以拿到一半分
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=10010;
LL n;
LL f[N][N],a[N],cnt;
int main(){
cin>>n;
for(int i=1;i<=100;i++){
for(int j=1;j<=i;j++){
if(i==1||i==j)f[i][j]=1;
else f[i][j]=f[i-1][j]+f[i-1][j-1];
a[cnt++]=f[i][j];
}
}
for(int i=0;i<cnt;i++){
if(n==a[i]){
cout<<i+1<<endl;
break;
}
}
return 0;
}
算法2
1.杨辉三角是对称的,直接删掉右边部分看左边就好
2.从右往左斜着看,每一个斜行的C(X,K)的K是固定的
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n;
LL C(LL a,LL b){//求组合数,因为这里最大只有1e9,可以直接暴力
LL sum=1;
for(int i=a,j=1;j<=b;i--,j++){
sum=sum*i/j;
if(sum>n)return sum;
}
return sum;
}
bool find(int x){//记住这里是求斜着的组合数
LL l=2*x,r=max(n,l);//每个斜行开始都是2*x(依次往下数,0,1,2,3........)
while(l<r){//二分模板,二分该斜行,从右往左看,每个斜行依次是C(1,0),C(2,1),C(4,2).....每一斜行的C(a,,b),b是固定的
LL mid=(l+r)/2;
if(C(mid,x)>=n)r=mid;//这里是找到一个小于等于目标的数
else l=mid+1;
}
if(C(r,x)!=n)return false;
cout<<r*(r+1)/2+x+1<<endl;//r是行数,这一行之前有(r+1)*r/2个数,然后加上K,再+1是为了位置输出的需要
return true;
}
int main(){
cin>>n;
for(LL i=16;i;i--)if(find(i))break;//在第十六斜行就已经超过1e9
return 0;
}