使用Python查詢第n個二進位制字串中的第k位

假設我們有兩個正值n和k，現在我們可以使用以下規則建立一個二進位制字串S_n：

  • S_1 = "0"

  • S_i = S_(i-1) 連線 "1" 連線 reverse(invert(S_(i-1))) 對於 i > 1

這裡reverse(x)返回反轉後的字串x，invert(x)翻轉x中的所有位。

以下是四個這樣的字串示例

  • S_1 = "0"

  • S_2 = "011"

  • S_3 = "0111001"

  • S_4 = "011100110110001"

我們需要找到S_n中的第k位。

因此，如果輸入像n = 4 k = 10，則輸出將為1，因為S_4 = "011100110110001"，所以第10位是1（第一位在位置1）。

為了解決這個問題，我們將遵循以下步驟：

  • 如果k等於1，則

    • 返回"0"字串

  • 否則，

    • arr := 一個包含單個元素0的陣列

    • arr2 := 一個包含單個元素1的陣列

    • 當k > arr的大小，執行以下操作：

      • templast := arr的副本

      • temp2last := arr2的副本

      • arr := templast 連線 "1" 連線 temp2last

      • arr2 := templast 連線 "0" 連線 temp2last

  • 返回arr中第k-1個元素

讓我們看下面的實現來更好地理解：

示例

def solve(n, k):
   if k == 1:
      return(str(0))
   else:
      arr = [0]
      arr2 = [1]
      while k > len(arr):
         templast = arr.copy()
         temp2last = arr2.copy()
         arr = templast + [1] + temp2last
         arr2 = templast + [0] + temp2last
      return(str(arr[k-1]))
n = 4
k = 10
print(solve(n, k))

輸入

4, 10

輸出

1

更新於：2021年5月29日

瀏覽量：306

啟動您的職業生涯

完成課程獲得認證

開始學習
廣告