1

私は次のことをするように頼まれました：x、x + 1、…、x + 5セットのマックナゲットを購入できる場合、いくつかのxについては、任意の数のマックナゲット>=xを購入することができます。マックナゲットは6、9、20パックで提供されます。正確な数量で購入できないマックナゲットの最大数を見つける反復プログラムを作成します。

これが私が思いついたコードですが、それは無限ループで立ち往生しています：

count = 0
n = 1
while count < 6:
    six_consequtive = True
    for a in range(n):
        for b in range(n):
            for c in range(n):
                if 6*a + 9*b + 20*c == n:
                    six_consequtive = False
    if six_consequtive:
        count += 1
    else:
        count = 0

    n += 1

print("Largest number of McNuggets that cannot be bought in exact quantity: %d." % (n - 5))

どうもありがとうございます！

4

2 に答える 2

0

問題が何であるかはかなり明らかなようですcount。正確な量を取得できる場合にのみ増分します。インクリメントしないときはいつでもcount0にリセットし、ループはこれが6を超えたときにのみ停止します。これにはしばらく時間がかかる場合があります。

三重にネストされたforループを作成したので、getが大きいnほど、これらのループの速度は遅くなります。十分に長く実行させると、成功していつか終了する可能性があります。しかし、基本的なアルゴリズムは遅すぎます。

ループをprintステートメントでインストルメント化することで詳細を知ることができます。試したところ、出力が得られませんでした。これはおそらくバッファリングの問題が原因であると考えたので、文字列を出力してからフラッシュして出力がすぐに表示されるようにする簡単な出力関数を作成しました。

これがそのように編集されたあなたのプログラムです：

import sys

def out(s):
    sys.stdout.write(s + "\n")
    sys.stdout.flush()

count = 0
n = 1
while count < 6:

    six_consecutive = True
    for a in range(n):
        for b in range(n):
            for c in range(n):
                #out("a: %d b: %d c: %d  n: %d" % (a, b, c, n))
                if 6*a + 9*b + 20*c == n:
                    six_consecutive = False

    out("n == %d  count == %d  six_consecutive == %s" %
            (n, count, str(six_consecutive)))

    if six_consecutive:
        count += 1
    else:
        count = 0

    n += 1

print("Largest number of McNuggets that cannot be bought in exact quantity: %d." % (n - 5))

「six_consecutive」のスペルも修正しました。

では、これをどのように修正する必要がありますか？これを捨てて、より良いアルゴリズムで書き直すべきだと思います。他の人がこの問題または同様の問題をどのように解決したかを確認することをお勧めします。これは、異なる金種のコインのセットが与えられたときに、どのように変更を加えるかという古典的な問題に非常に似ていると私は思います。

注：変更を加えるという古典的な問題は、通常、値1のコインを含む、賢明なコインのセットを想定しています。最大のコインから始めて下に向かっていく単純な「欲張り」アルゴリズムは常に成功します。「コイン」セットが奇妙で、見つからない値があるため、これはもう少し興味深いものです。したがって、古典的なコインの問題は、私が思っていたほど関連性がない可能性があります。

于 2012-06-22T22:27:32.023 に答える
0

申し訳ありませんが、ブール値が逆になっていることに気づきました。ループの最初の最初のsix_consequtiveにはFalseを割り当て、2番目のsix_consequtiveにはTrueを割り当てる必要があります。繰り返しになりますが、ばかげた質問をして大変申し訳ありません。

于 2012-06-22T22:28:12.737 に答える