python - 一个错误的答案显然意味着一个逻辑错误，但是这个想法有什么问题呢？

Question

Problem 14在 Project Euler描述了很多人在这里问到的某个难题。我的问题不是如何解决问题或如何纠正其他人的错误。思前想后，写下了下面的“解法”，但似乎是错误的。有人可以解释我的错误吗？

def main():
    # start has all candidate numbers; found has known sequence numbers
    start, found = set(range(1, 1000000)), set()
    # if are numbers in start, then there are still unfound candidates
    while start:
        # pick a random starting number to test in the sequence generator
        number = start.pop()
        # define the set of numbers that the generator created for study
        result = set(sequence(number, found))
        # remove them from the candidates since another number came first
        start -= result
        # record that these numbers are part of an already found sequence
        found |= result
    # whatever number was used last should yield the longest sequence
    print(number)

def sequence(n, found):
    # generate all numbers in the sequence defined by the problem
    while True:
        # since the first number begins the sequence, yield it back
        yield n
        # since 1 is the last sequence number, stop if we yielded it
        if n == 1:
            break
        # generate the next number in the sequence with binary magic
        n = 3 * n + 1 if n & 1 else n >> 1
        # if the new number was already found, this sequence is done
        if n in found:
            break

if __name__ == '__main__':
    main()

该文档是后来添加的，希望足够清楚地解释为什么我认为它会起作用。

Answer 1

# whatever number was used last should yield the longest sequence
print(number)

由于您正在以随机顺序查看 start 的元素，因此上述评论和结论是错误的。

假设我们正在寻找从 1 和 8 之间的数字开始的最长序列。由于您的算法的目的是“选择一个随机的起始数字进行测试”，让我们按以下顺序选择数字:

1. 7:这会产生一个长度为 17 的序列，并剔除 1、2、4、5 和 8 来自 start。
2. 6:这会产生一个长度为 9 的序列，并从 start 中剔除 3。

start 中没有更多数字了。您的代码得出结论，6 是最佳解决方案，当然，它不是。

更一般地说，假设您碰巧在第一步中选择了最佳起始数字。对于您的工作方法，第一个序列需要包括 1 和 999,999 之间的每个数字。除非您可以证明这就是发生的情况，否则没有理由认为您的解决方案是正确的。