在Python中以给定的单调序列查找元素位置
假设我们有一个数l和一个单调递增序列f(m),其中f(m)=am+bm[log2(m)]+cm^3和(a=1,2,3,…),(b=1,2,3,…),(c=0,1,2,3,…)
这里[log2(m)]是以2为底的对数,并将该值四舍五入。所以,
如果m=1,则值为0。
如果m=2-3,则值为1。
如果m=4-7,则值为2。
如果m=8-15,则值为3。依此类推
我们必须找到值m,使f(m)=l,如果序列中不存在l,则必须打印0。我们必须牢记,值是以这样的方式表示的:64位以及三个整数a,b和c小于或等于100。
因此,如果输入像a=2,b=1,c=1,l=12168587437017,则输出将为23001,因为f(23001)=12168587437017
为了解决这个问题,我们将遵循以下步骤-
SMALLER_VAL:=1000000
LARGER_VAL:=1000000000000000
定义一个功能solve()
。这将需要a,b,c,n
回答:=a*n
lg_val:=n的日志基数2的下限
ans:=ans+b*n*lg_val
ans:=ans+c*n^3
返回ans
从主要方法中,执行以下操作-
开始:=1
结束:=SMALLER_VAL
如果c与0相同,则
结束:=LARGER_VAL
回答:=0
在开始<=结束时,执行
开始:=中+1
结束:=中-1
ans:=中
从循环中出来
中:=(开始+结束)/2(仅取整数部分)
val:=solve(a,b,c,mid)
如果val与k相同,则
否则当val>k时
除此以外,
返回ans
示例
让我们看下面的实现以更好地理解-
from math import log2, floor SMALLER_VAL = 1000000 LARGER_VAL = 1000000000000000 def solve(a, b, c, n) : ans = a * n lg_val = floor(log2(n)) ans += b * n * lg_val ans += c * n**3 return ans def get_pos(a, b, c, k) : begin = 1 end = SMALLER_VAL if (c == 0) : end = LARGER_VAL ans = 0 while (begin <= end) : mid = (begin + end) // 2 val = solve(a, b, c, mid) if (val == k) : ans = mid break elif (val > k) : end = mid - 1 else : begin = mid + 1 return ans a = 2 b = 1 c = 1 k = 12168587437017 print(get_pos(a, b, c, k))
输入项
2,1,1,12168587437017
输出结果
23001