计算步数达到 0 的函数

Question

给定一个二进制数，我需要编写一个函数来计算达到零的总步数。规则是：

偶数除以2
如果是奇数就减1

例如，“1110”(14)需要迭代六次才能变成0：

14 / 2 = 7
7 - 1 = 6
6 / 2 = 3
3 - 1 = 2
2 / 2 = 1
1 - 1 = 0

我想出了一个简单的计算解决方案，但是这个算法无法处理非常大的数字。

def test(x):
    a = int(x,2)
    steps = 0
    while a != 0:
        if a % 2 == 0:
            a = a // 2  
        else:
            a = a - 1
        steps += 1
    return steps

test("1000")
Out[65]: 4

test("101")
Out[66]: 4

test("001")
Out[67]: 1

test("0010010001")
Out[68]: 10

test("001001")
Out[69]: 5

我需要知道的：如何避免进行计算并拥有快速/可以处理大数的算法？

Answer 1

您的算法对奇数不正确。你只在数字为偶数时才除法，这不是你描述的 "steps."

你想要

def test(x, 2):
x_int = int(x)
steps = 0
while x_int <= 0:
    x_int //= 2
    x -= 1
    steps += 1

你应该澄清你的算法，因为你描述它的方式，你不能保证所有输入都收敛到 0。您描述的方式是奇数的无限循环。只需尝试 1:

#test(1)
1 // 2 = 0
0 - 1 = -1
...

现在你永远不会达到 0，这就是为什么你应该检查 x_int <= 0。

我建议你重新考虑一下你为什么要这么做。我相当确定您甚至不需要迭代算法来知道需要多少 "steps"，应该只需要一个数学公式即可。

Answer 2

您也可以使用递归方法：

def stepsToZero(N):
    return N if N < 2 else 2 + stepsToZero(N//2-1)

这将使您得到最多 N = 2**993（这是一个相当大的数字）的结果，并且函数非常简洁（恕我直言，更优雅）。

运行更快的方法是用数学方法解决这个问题

例如：

import math
def steps2Zero(N):
    if N < 2: return N
    d = int(math.log(N+2,2))-1
    s = int(N >= 3*2**d-2)
    return 2*d+s

请注意，对于 N=2^900，数学求解比递归快一百倍。另一方面，递归函数的响应时间不到一秒，而且可读性更高。因此，根据它的使用方式和大小，性能考虑可能毫无意义

Answer 3

假设您的代码是正确的并且规则是：

测试(0) = 0
test(n) = 1 + test(n / 2) 如果 n 是偶数；
1 + test(n − 1) 否则

需要注意的重要一点是：

偶数以二进制0结尾
除以 2 会删除末尾的 0（除此之外什么都没有）
奇数以二进制1结尾
减 1 将最后一个 1 变成 0（除此之外别无其他）

所以除了第一个之外，每1位增加2步，每一个有效的0位增加1步。这意味着对于以 1 开头的输入，您可以这样写：

def test(x):
    return x.count('1') + len(x) - 1

现在您只需要考虑前导零，或者如果前导零不可能，则只需考虑 "0" 的特定情况。

Answer 4

我今天在编码测试中遇到了这个问题，我有 40 分钟的时间来完成测试。不幸的是，我只是在计时器达到限制后才想出一个好的解决方案。

你不需要计算除法和减法(!)。你可以遍历S的字符，如果字符是1，需要两步, 如果字符是0, 只需要一步。

末尾有1就减1
如果末尾有0，除以2，数字会右移
第一个字符异常(S[0])

解决方法如下：

def iterate_string(S: str):
    acc = 0
    for c in S:
        if c == "0":
            acc += 1
        else:
            acc += 2
    acc -= 1 # the very first 1 is only + 1, thus - 1
    return acc

举个例子：

1001 (17) - 1 = 1000 (16)
1000 (16) / 2 = 100 (8)
100 (8) / 2 = 10 (4)
10 (4) / 2 = 1
1 - 1 = 0

# First digit, requires two steps:
   |
1001

# Second digit, requires one step:
  |
1001

# Third digit, requires one step:
 |
1001

# S[0] is 1, but requires only one step:
|
1001

=> total of 5 steps:

0:  1001    # (-1)
1:  1000    # (/2)
2:   100    # (/2)
3:    10    # (/2)
4:     1    # (-1)
5:     0

祝下一个面临同样挑战的人好运！ :)

这是无法处理大数字的幼稚解决方案：

def do_calculations(S: str):
    decimal_value = int(S, 2)
    iterations = 0
    while decimal_value > 0:
        if decimal_value % 2 == 1:
            decimal_value = decimal_value - 1
        else:
            decimal_value = decimal_value / 2
        iterations += 1
    return iterations

计算步数达到 0 的函数

a function to count the step reaching 0

python

zero