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

Cho n, k dương. Xây chuỗi S_n: S_1="0"; S_i = S_{i-1} + "1" + reverse(invert(S_{i-1})) cho i>1. Tìm bit thứ k trong S_n.

Ví dụ: S_1="0", S_2="011", S_3="0111001", S_4="011100110110001". n=4, k=10 → 1.

Thuật toán

• Nếu k==1: return "0"
• arr=[0], arr2=[1]
• While k > len(arr):
  • templast = arr.copy(), temp2last = arr2.copy()
  • arr = templast + [1] + temp2last
  • arr2 = templast + [0] + temp2last
• Return arr[k-1]

Code Python

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

Input

4, 10

Output

1