一個錯誤的答案顯然意味着一個邏輯錯誤，但什麼是錯誤的思想？

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

在向同事解釋提議的解決方案之後，答案就出現了：該解決方案沒有考慮在被測試的數字範圍之外生成的序列的長度。因此，需要設計一個考慮完整序列長度的新解決方案。

爲了測試算法，編寫了以下程序。該方法適用於整個封閉範圍內的序列。在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() 

Answer 2

# 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之間的每個數字。除非你能證明這是事實，否則沒有理由認爲你的解決方案是正確的。

Answer 3

錯誤的假設是在這裏：

# 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.