在 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
ans := a * n
lg_val := n 以 2 为底的对数的下限
ans := ans + b * n * lg_val
ans := ans + c * n^3
返回 ans
从主方法中,执行以下操作 −
begin := 1
end := SMALLER_VAL
如果 c 与 0 相同,则
end := LARGER_VAL
ans := 0
当 begin <= end 时,执行
mid :=(begin + end) / 2(只取整数部分)
val := resolve(a, b, c, mid)
如果 val 与 k 相同,则
ans := mid
退出循环
否则当 val > k,则
end := mid - 1
否则,
begin := mid + 1
返回 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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

