Python程式：查詢將整數變為零所需的最小一位運算元

假設我們有一個數字 n，我們需要使用以下操作任意多次將其轉換為 0：

  • 選擇 n 的二進位制表示中最右邊的位。

  • 當 n 的二進位制表示中的第 (i-1) 位設定為 1 且第 (i-2) 位到第 0 位設定為 0 時，更改第 i 位。

因此，我們最終需要找到將 n 轉換為 0 所需的最少操作次數。

因此，如果輸入類似於 n = 6，則輸出將為 4，因為最初 6 = "110"，然後使用第二個操作將其轉換為 "010"，然後使用第一個操作將其轉換為 "011"，然後使用第二個操作將其轉換為 "001"，最後使用第一個操作將其轉換為 "000"。

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

  • n := 數字 n 的二進位制位列表

  • m:= 一個新的列表

  • last:= 0

  • 對於 n 中的每個 d，執行以下操作：

    • 如果 last 等於 1，則

      • d:= 1-d

    • last:= d

    • 在 m 的末尾插入 d

  • m:= 透過連線 m 的元素來生成二進位制數

  • 以十進位制形式返回 m

示例

讓我們看看以下實現以更好地理解

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

輸入

"95643", "45963"

輸出

4

更新於: 2021年10月7日

255 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告