4

欧拉计划的第 14题描述了许多人在这里问过的一个难题。我的问题不是如何解决问题或如何解决其他人的错误。想了想谜底，写了下面的“解法”，但似乎是错误的。有人可以解释我的错误吗？

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

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

4

3 回答 3

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

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

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

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

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

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

于 2012-12-12T16:05:16.187 回答
2

错误的假设在这里：

# whatever number was used last should yield the longest sequence

考虑我们从而range(1, 13)不是开始的情况range(1, 1000000)。然后你的算法进行如下：

number result                                  start
-----------------------------------------------------------------------------------
 1     {1}                                     {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
 2     {2}                                     {3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
 3     {3, 4, 5, 8, 10, 16}                    {4, 5, 6, 7, 8, 9, 10, 11, 12}
 6     {6}                                     {7, 9, 11, 12}
 7     {34, 7, 40, 11, 13, 17, 52, 22, 20, 26} {9, 11, 12}
 9     {9, 28, 14}                             {12}
12     {12}                                    {}

所以最后使用的数字是 12。但是以这个范围内的数字开头的最长序列是 9 → 28 → 14 → 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16→8→4→2→1（长度20）；序列 12 → 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 的长度只有 10。

只有当您得到正确答案（开始最长序列的数字）时，您的方法才有效，该范围内的所有较高数字要么已经找到，要么在生成以正确答案。

但是在这个例子中，当我们到达 9 时，数字 12 还没有在任何序列中找到，也没有在从 9 开始的序列扩展过程中找到。

于 2012-12-12T16:13:13.030 回答
0

在向同事解释了建议的解决方案后，我得到了答案：这个解决方案没有考虑到在被测试的数字范围之外生成的序列长度。因此，需要设计一种考虑完整序列长度的新解决方案。

为了测试算法，编写了以下程序。该方法适用于整个封闭范围内的序列。这在 Collat​​z 问题中是完全不可能完成的，因此代码失败了。

import random
import time

class Sequencer:

    def __init__(self, limit, seed):
        random.seed(seed)
        self.__sequence = tuple(random.sample(range(limit), limit))

    def __call__(self, start):
        yield from self.__sequence[self.__sequence.index(start):]

    @property
    def longest(self):
        return self.__sequence[0]

def main(limit):
    while True:
        sequence = Sequencer(limit, str(time.time()))
        longest = find_longest(limit, sequence)
        print('Found longest ' +
              ('' if longest == sequence.longest else 'in') +
              'correctly.')

def find_longest(limit, sequence):
    start, found = set(range(limit)), set()
    while start:
        number = start.pop()
        result = set(get_sequence(sequence(number), found))
        start -= result
        found |= result
    return number

def get_sequence(sequence, found):
    for number in sequence:
        if number in found:
            break
        yield number

if __name__ == '__main__':
    main(1000000)

代码的更正版本在其设计中遵循类似的模式，但会跟踪原始范围之外的值。已发现执行时间与该难题的其他 Python 解决方案相似。

def main():
    start, found = set(range(2, 1000000)), {1: 1}
    while start:
        scope = reversed(tuple(sequence(start.pop(), found)))
        value = dict(map(reversed, enumerate(scope, found[next(scope)] + 1)))
        start -= frozenset(value)
        found.update(value)
    lengths = dict(map(reversed, found.items()))
    print(lengths[max(lengths)])

def sequence(n, found):
    while True:
        yield n
        if n in found:
            break
        n = 3 * n + 1 if n & 1 else n >> 1

if __name__ == '__main__':
    main()
于 2012-12-12T16:04:44.117 回答