python - 修复 "Binary period"的解决方案

Question

我找到了这个任务并完全坚持其解决方案。

给出一个由 Q 个字符组成的非空零索引字符串 S。该字符串的周期是最小正整数 P，使得:

P ≤ Q/2 且 S[K] = S[K+P](0 ≤ K < Q − P)。

例如，7 是“abracadabracadabra”的句点。如果 M 是 N 的二进制表示的周期，则正整数 M 是正整数 N 的二进制周期。

例如，1651 的二进制表示为“110011100111”。因此，它的二进制周期是 5。另一方面，102 没有二进制周期，因为它的二进制表示形式是“1100110”并且没有周期。

考虑上述场景并在 Python 中编写一个函数，该函数将接受整数 N 作为参数。给定正整数 N，该函数返回 N 的二进制周期，如果 N 没有二进制周期，则返回 -1。

所附代码在某些输入(9、11、13、17 等)上仍然不正确。目标是发现并修复实现中的错误。您最多可以修改 2 行。

def binary_period(n):
    d = [0] * 30
    l = 0
    while n > 0:
        d[l] = n % 2
        n //= 2
        l += 1
    for p in range(1, 1 + l):
        ok = True
        for i in range(l - p):
            if d[i] != d[i + p]:
                ok = False
                break
        if ok:
            return p
    return -1

Answer 1

我在面试中得到了这段代码。

练习的目的是找出错误所在。

作为函数的输入，您将键入整数以查看其二进制周期。例如，solution(4) 将为您提供二进制数 0011。

但是，问题如下:错误是什么？

这种情况下的错误不是某些崩溃和烧毁代码，而是应该发生但在代码中没有发生的行为。

它被称为 logical error在代码中。逻辑错误是指代码没有破坏但没有满足要求时的错误。

对代码使用暴力是没有帮助的，因为有十亿种可能性。

但是，如果您运行代码，假设从 solutions(1) 到 solutions(100)，您将看到代码运行时没有任何故障。然而，如果您查看代码，如果有错误，它应该返回 -1。

即使您对更大的数字(例如 10000)运行解决方案，代码也不会给出任何 -1。

这里的bug在于-1没有被触发。

那么让我们一步一步地讨论代码。

可能是while部分吗？

while n > 0:
    d[l] = n % 2
    n //= 2
    l += 1

如果你看一下代码，它正在做它应该做的事情，将给定的数字更改为二进制数，即使它是从向后的位置做的。您没有 1011，而是 1101，但它可以完成这项工作。

问题就在于那部分

for p in range(1, 1 + l):
        ok = True
        for i in range(l - p):
            if d[i] != d[i + p]:
                ok = False
                break
        if ok:
            return p
return -1

它没有返回-1。

如果你在代码的某些部分像这样打印一些内容，就会得到这个

for p in range(1, 1 + l):
    ok = True
    for i in range(l - p):
        print('l, which works as an incrementor is substracted to p of the first loop',p,l-p)
        if d[i] != d[i + p]:
            ok = False
            break
    if ok:
        return p
return -1

如果你运行整个脚本，实际上，你可以看到它永远不会结束，即使d[i]不再等于d[i+p].

但是为什么呢？

原因是因为增量器 l 是基于整数除法构建的。因此，您需要执行 1+l//2。

这将为您提供以下内容

def solution(n):
    d = [0] * 30
    l = 0
    while n > 0:
        d[l] = n % 2
        n //= 2
        l += 1
    for p in range(1, 1 + l//2): #here you put l//2
        ok = True
        print('p est ',p)
        for i in range(l - p):
            if d[i] != d[i + p]:
                ok = False
                break
        if ok:
            return

现在，如果您使用 solutions(5) 运行代码，则错误应该已修复，并且您应该得到 -1。

<小时/>

附录:

这个测试是一项困难的测试，算法不容易在很短的时间内处理，而且变量没有任何意义。

第一步是提出以下问题:

• 算法的输入是什么？在本例中，它是一个整数。
• 预期输出是什么？在本例中，-1
• 这是逻辑错误还是崩溃和烧毁类型的错误？在这种情况下，这是一个逻辑错误。

这些分步 ( heuristic ) 将为您指明调试问题的正确方向。