0

私は、以下に詳述されているプロジェクタイラー パズルを解こうとしています。私の現在の関数は 1 から 10 の数字に対して機能しますが、1 から 20 を試してみると、結果が得られずに永遠にループします。

2520 は、1 から 10 までの各数値で割り切れる最小の数値です。1 から 20 までのすべての数で割り切れる最小の正の数は?

def calculate():
    results = dict()
    target = 20
    num_to_test = 1
    while len(results) < target:
        for j in range(1, target+1):
            results[num_to_test] = True
            if num_to_test % j != 0:
                # current num_to_test failed in the 1-10, move on
                del results[num_to_test]
                break

        num_to_test += 1
    return min(results)

誰でもロジックの問題を見ることができますか?特に、ターゲットが 10 であるのに 20 ではない理由を知りたいです。ありがとう

4

5 に答える 5

5

あなたのアルゴリズムはかなり非効率的ですが、問題の核心は、results辞書が 1 から 20 までの数字で割り切れる整数ごとに 1 つの値を蓄積していて、whileそのような数字が 20 個になるまでループを続けようとしていることです。

これは、この非効率なアルゴリズムを実装する正しい方法の 1 つです。

def calculate():
    target = 20
    candidate = 1
    success = False
    divisors = range(1, target+1)
    while not success:
        for divisor in divisors:
            if candidate % divisor != 0:
                candidate += 1
                break
        else:
            success = True

    return candidate

このelse句は、if ループではなく、実際には for ループにあることに注意してください。フロー制御に関するチュートリアルから:

ループ ステートメントには、else 句を含めることができます。ループがリストの枯渇によって終了したとき (for を使用)、または条件が false になったとき (while を使用) に実行されますが、break ステートメントによってループが終了したときは実行されません。

もう少し簡潔な表現は次のようになります。

candidate = 0
while not success:
    candidate += 1
    success = all((candidate % divisor == 0 for divisor in divisors))

これはジェネレーター式を使用するため、all短絡して不要な計算を回避できます。

これはパズルなので、より良いアルゴリズムを提案します。

于 2013-07-31T20:25:37.680 に答える
4

実際、私はその問題に対して非常に効率的なアルゴリズムを持っています。コードは教えませんが、方法は教えます

N = 10 の場合

1. 5 から 10 までのすべての数のすべての因数を計算します。

 [[2, 3], [7], [2, 2, 2], [3, 3], [2, 5]]

2.リスト内の各素数の最大数を計算する

 {2: 3, 3: 2, 5: 1, 7: 1}

3.キーパワー値の積を得る

 2^3 * 3^2 * 5 * 7 = 2520
于 2013-07-31T20:51:23.450 に答える
1

すべてを保存しないでください。代わりに、見つけたらすぐに戻り、その結果の辞書を取り除きます。ちなみに、これはまったく最適ではありません。クリーンアップするだけです

def calculate():
    target = 20
    num_to_test = 0
    while True:
        num_to_test += target
        if all((num_to_test % j == 0) for j in range(1,target+1)):
            return num_to_test
    return -1

また、最大値の倍数ではない数値をテストする必要はありません。20倍速くなります。

all()ジェネレーターを使用して、数値が1 から 20 までの数値で割り切れるかどうかをテストすることに切り替えました。

独自のアルゴリズムを作成し、コピーしないための小道具:)

于 2013-07-31T20:30:35.247 に答える
1

あなたのアルゴリズムは非常に非効率的ですが、この小さな変更を加えると少しは役立つかもしれません

        if num_to_test % j = 0:
            results[num_to_test] = True
        else:
            # current num_to_test failed in the 1-10, move on
            break

なぜそれらすべてを保存しているのかわかりませんか？おそらくデバッグ用ですか？

ヒント。結果の素因数を計算し、それらを単純に乗算する方がよいでしょう。

# spoiler  






























def calculate(target):
    n = 1
    for i in range(1, target+1):
        for j in range(1, target+1):
            if (n * j) % i == 0:
                n *= j
                break
    return n
于 2013-07-31T20:32:33.487 に答える