Chương trình tìm các phép toán một bit tối thiểu để tạo số nguyên bằng không trong Python

Giả sử chúng ta có một số n, chúng ta phải chuyển nó thành 0 bằng các phép toán sau bất kỳ số lần nào -

• Chọn bit ngoài cùng bên phải trong biểu diễn nhị phân của n.

• Thay đổi bit thứ i trong biểu diễn nhị phân của n khi bit thứ (i-1) được đặt thành 1 và bit thứ (i-2) đến bit thứ 0 được đặt thành 0.

Vì vậy, cuối cùng chúng ta phải tìm số phép toán tối thiểu cần thiết để biến đổi n thành 0.

Vì vậy, nếu đầu vào là n =6, thì đầu ra sẽ là 4 vì ban đầu 6 ="110", sau đó chuyển đổi thành "010" bằng thao tác thứ hai, sau đó chuyển đổi thành "011" bằng thao tác đầu tiên, sau đó chuyển đổi thành " 001 "sử dụng thao tác thứ hai và cuối cùng chuyển đổi thành" 000 "bằng thao tác đầu tiên.

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

• n:=danh sách các bit nhị phân của số n

• m:=một danh sách mới

• cuối cùng:=0

• cho mỗi d trong n, làm

  • nếu cuối cùng bằng 1, thì

    • d:=1-d

  • cuối cùng:=d

  • chèn d vào cuối m

• m:=tạo số nhị phân bằng cách nối các phần tử của m

• trả về m ở dạng thập phân

Ví dụ

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

def solve(n):
   n=list(map(int,bin(n)[2:]))
   m=[]
   last=0
   for d in n:
      if last==1:
         d=1-d
      last=d
      m.append(d)
   m=''.join(map(str,m))
   return int(m,2)

n = 6
print(solve(n))

Đầu vào

"95643", "45963"

Đầu ra

4