Chương trình tìm bit thứ K trong chuỗi nhị phân thứ n bằng Python

Giả sử chúng ta có hai giá trị dương n và k, bây giờ chúng ta có thể tạo một chuỗi nhị phân S_n bằng cách sử dụng các quy tắc sau -

• S_1 =0

• S_i =S_i-1 nối "1" nối ngược (invert (S_i-1)) cho i> 1

Ở đây reverse (x) trả về chuỗi x đã đảo ngược và invert (x) lật tất cả các bit trong x.

Đây là ví dụ về bốn chuỗi như vậy

• S_1 ="0"

• S_2 ="011"

• S_3 ="0111001"

• S_4 ="011100110110001"

Chúng ta phải tìm bit thứ k trong S_n.

Vì vậy, nếu đầu vào là n =4 k =10, thì đầu ra sẽ là 1 vì S_4 ="011100110110001", vì vậy bit thứ 10 là 1 (bit đầu tiên ở vị trí 1).

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu k giống với 1 thì

  • trả về 0 dưới dạng chuỗi

• nếu không,

  • arr:=một mảng có một phần tử 0

  • arr2:=một mảng có 1 phần tử duy nhất

  • while k> size of arr, do

    • templast:=bản sao của arr

    • temp2last:=bản sao của arr2

    • arr:=templast concatenate 1 concatenate temp2last

    • arr2:=templast concatenate 0 concatenate temp2last

• trả về phần tử thứ k-1 từ arr

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

4, 10

Đầu ra

1