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 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告