| 求杨辉三角中元素首次出现位置【2021蓝桥杯】 | 您所在的位置：网站首页 › php打印杨辉三角形 › 求杨辉三角中元素首次出现位置【2021蓝桥杯】 |
求杨辉三角中元素首次出现位置【2021蓝桥杯】
|
问题
输入一个整数n,求出n在杨辉三角中首次出现的位置。（从上至下，从左至右算） 输入规模:n10亿，所以从16斜行开始算即可。 #python index = 1; #元素首次出现位置，初始化为1 #斜行 for k in range(16,1,-1): #从16斜行递减，算每一斜行 if index!=1: #说明结果已算出，结束 break j = 2*k #起始行为2k+1 while 1: result = combi(j,k) #combi函数为自定义的组合数函数 if result==n: index = getIndex(j+1,k+1) #根据行、列，返回位置 print("level ",j+1,"pos ",k+1) break; elif result>n: #不在这一斜行的情况 break; j+=1 #每次加1行分析一下时间复杂度。k=2时，只需计算二次函数。k=3时，C(2000,3)>10亿，k=4时，C(500,4)>10亿。当k=10时，C(50,10)就远大于10亿。也就是说一个只需计算2500次左右的阶乘，而且大多数情况k很小。（计算组合数和求位置代码见文末） 如果在内部斜行都没找到，说明那个元素就在最外面的斜行，即在n+1行第2个。 组合数求法做了优化，具体见注释。 完整代码 #python combiArr = [0 for i in range(0,20)] #求组合数 #如果用n！除以r!和(n-r)!，需要算3个阶乘，而且n!会很大。由于n-r>r,所以可先约分，算 #(n-r+1)*(n-r+2)*...*n,再除以r！。此外每次算出r!可存入数组中，第二次便无需重算。 def combi(n,r): global combiArr; result = 0 #分子 a = 1 for i in range(n-r+1,n+1): a*=i #分母 b=1 if combiArr[r]!=0: b = combiArr[r] else: for i in range(1,r+1): b*=i combiArr[r]=b result = a//b return result #根据行列求位置 def getIndex(l,p): return int(l*(l-1)/2+p) n = int(input()); index = 1; #元素首次出现位置，初始化为1 #斜行 for k in range(16,1,-1): #从16斜行递减，算每一斜行 if index!=1: #说明结果已算出，结束 break j = 2*k #起始行为2k+1 while 1: result = combi(j,k) #combi函数为自定义的组合数函数 if result==n: index = getIndex(j+1,k+1) #根据行、列，返回位置 print("level ",j+1,"pos ",k+1) break; elif result>n: #不在这一斜行的情况 break; j+=1 #每次加1行 #外层斜行 if index==1: if n!=1: print("level ",n+1,"pos ",2) index = getIndex(n+1,2) print(index) 运行时间由于是逆序计算，所在斜行越靠外，会先把里面的斜行遍历，计算时间越长。输入n=6测试计算时间，不到1s. 考试的时候就没想到，直接硬算，直接没了。。 |
【本文地址】
公司简介
联系我们