6

オイラー問題 14を解きましたが、使用したプログラムは非常に遅いです。私は他の人が何をしたかを見て、彼らは皆エレガントな解決策を思いついた. 私は彼らのコードを理解しようとしましたが、あまり成功しませんでした。

これが私のコードです（コラッツチェーンの長さを決定する関数

def collatz(n):
a=1
while n!=1:
    if n%2==0:
        n=n/2
    else:
        n=3*n+1
    a+=1
return a

それから私は力ずくを使いました。それは遅く、私はそれが弱いことを知っています。私のコードが弱い理由と、平易な英語でコードを改善する方法を教えてください。私は初心者であり、私のプログラミングスキルは基本的なものであることを覚えておいてください。

4

2 に答える 2

11

最初から最後まで可能なすべてのチェーンを計算するのではなく、チェーンの開始とその結果の長さのキャッシュを保持できます。たとえば、チェーンの場合

13 40  20  10  5  16  8  4  2  1

あなたは次のことを覚えているでしょう：

  1. 13で始まるコラッツチェーンの長さは10です。
  2. 40で始まるコラッツチェーンの長さは9です。
  3. 20で始まるコラッツチェーンの長さは8です。

... 等々。

次に、この保存された情報を使用して、すでにキャッシュにある番号に遭遇するとすぐにチェーンの計算を停止できます。

実装

Pythonで辞書を使用して、開始番号をチェーンの長さに関連付けます。

chain_sizes = {}
chain_sizes[13] = 10
chain_sizes[40] = 9
chain_sizes[40]   # => 9
20 in chain_sizes # => False

ここで、この辞書を利用するようにアルゴリズムを調整する必要があります（値を入力し、中間の数値を検索します）。

ちなみに、これは再帰を使用して非常にうまく表現できます。ここで発生する可能性のあるチェーンサイズは、スタックをオーバーフローしません:)

于 2012-04-09T20:02:17.497 に答える
1

簡単に言えば、私の英語はひどいので;-)

Forall n >= 1, C(n) = n/2     if n even,
                      3*n + 1 if n odd

一度に複数の連続した反復を計算することができます。

k0ビットで終わる数値の k 番目の反復:

C^k(a*2^k) = a

1kビットで終わる数値の (2k) 番目の反復:

C^(2k)(a*2^k + 2^k - 1) = a*3^k + 3^k - 1 = (a + 1)*3^k - 1

参照。ウィキペディアの記事の数式(フランス語) ; 私のウェブサイト(フランス語) と私の Python パッケージDSPythonのモジュールtnp1も参照してください。

次のコードを、Niklas B によって説明されたメモ化の手法と組み合わせます。

#!/usr/bin/env python
# -*- coding: latin-1 -*-
from __future__ import division  # Python 3 style in Python 2
from __future__ import print_function  # Python 3 style in Python 2


def C(n):
    """Pre: n: int >= 1
    Result: int >= 1"""
    return (n//2 if n%2 == 0
            else n*3 + 1)


def Ck(n, k):
    """Pre: n: int >= 1
         k: int >= 0
    Result: int >= 1"""
    while k > 0:
        while (n%2 == 0) and k:  # n even
            n //= 2
            k -= 1

        if (n == 1) and k:
            n = 4
            k -= 1
        else:
            nb = 0
            while (n > 1) and n%2 and (k > 1):  # n odd != 1
                n //= 2
                nb += 1
                k -= 2

            if n%2 and (k == 1):
                n = (n + 1)*(3**(nb + 1)) - 2
                k -= 1
            elif nb:
                n = (n + 1)*(3**nb) - 1

    return n


def C_length(n):
    """Pre: n: int >= 1
    Result: int >= 1"""
    l = 1

    while n > 1:
        while (n > 1) and (n%2 == 0):  # n even
            n //= 2
            l += 1

        nb = 0
        while (n > 1) and n%2:  # n odd != 1
            n //= 2
            nb += 1
            l += 2
        if nb:
            n = (n + 1)*(3**nb) - 1

    return l


if __name__ == '__main__':
    for n in range(1, 51):
        print(n, ': length =', C_length(n))
于 2012-04-14T21:21:45.950 に答える