在 Python 中查找给定单调序列中的元素位置

pythonserver side programmingprogramming更新于 2025/10/10 6:04:17

假设我们有一个数字 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

相关文章


有用资源