试题 历届真题 杨辉三角形【第十二届】【省赛】【B组】

 思路

杨辉三角的前两行都为1，并且每一行首尾都为1，所以当输入的N=1时，直接输出位置1

然后当我们输入的N大于1

我们开始建立杨辉三角的第三行，判断N如果在第三行中，则输出位置，结束循环。这个位置的计算方法就是获取当前行数，计算 前几行的长度 还有 当前行N出现的索引位置 的和。(杨辉三角第几行就有几个值，所以我们计算第五行第三个的位置，就是(1+2+3+4) + 3，这是一个等差数列)

如果第三行没有找到，我们就要根据第三行的值计算第四行的值，然后在判断N是否存在于第四行中。我们把第三行的值赋予给a，通过循环依次取a的值计算第四行，完事后把第四行赋值给b，把a清空。当我们继续计算第五行的时候，就可以把第五行赋值给a，把b清空给第六行用。

以下代码的b列表是杨辉三角第二行的两个 亿

我们通过两个a,b列表存储杨辉三角的 当前行 和 前一行，这样依次就可以计算N所在的行

n = int(input())
a = []
b = [1,1]
while True:if n == 1:print(1)breakelse:for i in range(len(b)+1):if i == 0 or i==len(b):a.insert(i,1)else:a.insert(i,b[i-1]+b[i])b = []if n in a:m=len(a)-1m = m + m*(m-1)/2print(int(m+a.index(n)+1))breakfor i in range(len(a)+1):if i == 0 or i == len(a):b.insert(i,1)else:b.insert(i,a[i-1]+a[i])a = []if n in b:m=len(b)-1m = m + m*(m-1)/2print(int(m+b.index(n)+1))break

这个代码依旧有缺陷，在比赛网站测试它会超时，并不能计算太大的值 ，当N==2345时，运行时间是0.9394

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！