โปรแกรมค้นหา Kth bit ในสตริงไบนารีที่ n โดยใช้ Python

สมมติว่าเรามีค่าบวกสองค่า n และ k ตอนนี้เราสามารถสร้างสตริงไบนารี S_n ได้โดยใช้กฎต่อไปนี้ -

• S_1 =0

• S_i =S_i-1 เชื่อม "1" ต่อกันแบบย้อนกลับ (กลับด้าน (S_i-1)) สำหรับ i> 1

reverse(x) จะคืนค่าสตริงที่กลับด้าน x และ invert(x) จะพลิกบิตทั้งหมดใน x

นี่คือตัวอย่างสี่สตริงดังกล่าว

• S_1 ="0"

• S_2 ="011"

• S_3 ="0111001"

• S_4 ="01110011011001"

เราต้องหา kth bit ใน S_n

ดังนั้น หากอินพุตเป็น n =4 k =10 เอาต์พุตจะเป็น 1 เนื่องจาก S_4 ="01110011011001" ดังนั้นบิตที่ 10 จึงเป็น 1 (บิตแรกอยู่ที่ตำแหน่ง 1)

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ถ้า k เท่ากับ 1 แล้ว

  • คืนค่า 0 เป็นสตริง

• มิฉะนั้น

  • arr :=อาร์เรย์ที่มีองค์ประกอบเดียว 0

  • arr2 :=อาร์เรย์ที่มีองค์ประกอบเดียว 1

  • ในขณะที่ k> ขนาดของ arr ทำ

    • templast :=สำเนาของ arr

    • temp2last :=สำเนาของ arr2

    • arr :=templast concatenate 1 concatenate temp2last

    • arr2 :=templast concatenate 0 concatenate temp2last

• ส่งคืนองค์ประกอบที่ k-1 จาก arr

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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