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. 71: これにより、長さ 17 のシーケンスが生成され、、、、およびfrom が2ノックアウトさ4れます。58start
  2. 63: これにより、長さ 9 のシーケンスが生成され、 からノックアウトされ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

提案された解決策を同僚に説明した後、答えが私に来ました。この解決策は、テストされている数の範囲外で生成されたシーケンスの長さを考慮していません。したがって、完全なシーケンスの長さを考慮した新しいソリューションを考案する必要があります。

アルゴリズムをテストするために、次のプログラムが作成されました。このメソッドは、閉じた範囲全体のシーケンスに対して機能します。コラッツ問題でこれを達成することはまったく不可能であるため、コードは失敗します。

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 に答える