- 专栏
- 《蓝桥杯题目》
目录
下面的图形是著名的杨辉三角形：
如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, …
给定一个正整数 N，请你输出数列中第一次出现 N 是在第几个数？
输入一个整数 N。
输出一个整数代表答案。
6
13
对于 20% 的评测用例，1 ≤ N ≤ 10；
对于所有评测用例，1 ≤ N ≤ 1000000000。
如果直接用暴力枚举的话，需要求出每一行的全部数字，然后判断每一行中是否存在该整数，思路可以，但是时间复杂度太大，只能拿30%。如果根据二项式定理，找出从哪一行开始只需要遍历前三个数，然后利用求和公式直接计算答案，就可以大大减少时间复杂度。
首先介绍一下杨辉三角的性质：
1、每个数等于它上方两个数的和。
2、左右对称（说明最先出现的数一定在左边）
3、第n行有n个数，前n行就有(n+1)*n/2个数
4、n+1行的数是（a+b)^n展开后各项的系数
所以，由性质4可得，第n行的m个元素为C(n-1,m-1),由于1 ≤ N ≤ 1000000000,每一行第四个数为N*(N-1)*(N-2)/6，粗略计算，当N>1900时，第四项就大于1000000000了，所以说，从第1901行开始，N若是第一次出现，只可能出现在第二第三项。
因此，在前1900层时，可以直接使用暴力枚举，在判断是否在该层，若不在前面1900层，先粗略估计N所在的层数（先计算在第三项时，因为若存在，就会先出现）int((N*2)**0.5)，这时，就只需要判断三种情况：①N在该层；②N在下一层；③N在N+1层。
最后计算在第几个数上，分为三种情况：
1、在前1900层时，(c*c+c)//2+j+1 ，在c+1层的第j+1个数时（j是在列表中的下表，因此要加1）
2、在1900层之后且是第三项时，(k*(k+1))//2+3，第k+1行
3、在1900层之后且是第二项时，(N*(N+1)//2)+2，第N+1行时
N=int(input())
n=[1] #第一层
c=1 #层数
if N==1:
print(1)
else:
#由于第1900层开始，N只会出现在第二个或第三数字上，所以1900开始，不需要求全部
while c<1900:
n = [1]+[n[j]+n[j+1] for j in range(len(n)-1)]+[1] #杨辉三角递推公式
if N not in n[1:len(n)-1]: #判断N是否在c层上
c=c+1
else:
break
if c==1900:
k=int((N*2)**0.5) #粗略计算出现的层数
#N出现在第三个数上
while (k*(k-1))//2<N:
k=k+1
if (k*(k-1))//2==N:
print((k*(k+1))//2+3)
#N出现在第二个数上
else:
print((N*(N+1)//2)+2) # N会出现在第N+1层
#N在前1900层上时
for j in range(len(n)):
if n[j]==N:
print(((c*c+c)//2)+j+1)
break最后运行一下结果。。。。。
