在 Python 中查詢單調序列中的元素位置

假設我們有一個數字 l 和一個單調遞增序列 f(m)，其中 f(m) = am + bm [log₂(m)] + cm³，(a = 1, 2, 3, …), (b = 1, 2, 3, …), (c = 0, 1, 2, 3, …)

這裡 [log₂(m)] 是以 2 為底的對數，並向下取整。所以，

如果 m = 1，則值為 0。

如果 m = 2-3，則值為 1。

如果 m = 4-7，則值為 2。

如果 m = 8-15，則值為 3，以此類推。

我們必須找到使 f(m) = l 的值 m，如果 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³

  • 返回 ans

  • 從主方法中執行以下操作：

  • begin := 1

  • end := SMALLER_VAL

  • 如果 c 等於 0，則

    • end := LARGER_VAL

  • ans := 0

  • 當 begin <= end 時，執行

    • mid := (begin + end) / 2（僅取整數部分）

    • val := solve(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

更新於：2020年8月25日

206 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告