1 
def numPens(n):
    """
    n is a non-negative integer

    Returns True if some non-negative integer combination of 5, 8 and 24 equals n
    Otherwise returns False.
    """
    if n < 5:
        return False
    N = n
    while N >= 0:
        if  N % 24 == 0 or N % 8 == 0 or N % 5 == 0: # if N / 24 is equal to 0 then we can buy N pens
            return True
        if N < 5:
            return False    # if N < 5 we cannot buy any pens

        if  N > 24:         # if N is greater than 24 , take away 24 and continue loop
            N -= 24
        elif N > 8:         # if N is greater than 8, take away 8 and continue loop
            N -= 8
        else:
            N -= 5          # else take away 5 and continue loop

私はテストのためにこの関数を作成しなければなりませんでした.問題を再帰的にソートできるかどうか、または最も効率的な解決策は何かと思っています.プログラミングは初めてなので、助けていただければ幸いです.

4

6 に答える 6

6 
if  N % 24 == 0 or N % 8 == 0 or N % 5 == 0

上記のモジュラス () チェックを取り除くと、そのアルゴリズムは貪欲なアルゴリズム%として知られています。反復ごとに可能な最大数を減算します。お気づきかもしれませんが、貪欲なアルゴリズムは機能しません。たとえば、 15 = 5 + 5 + 5に対して間違った答えが返されます。

 15 (-8) --> 7 (-5) --> 2 --> False

モジュラス チェックを追加することで、貪欲なアルゴリズムが改善されました。これは、15 を正しく処理するようになったためです。ただし、まだ穴があります。たとえば、26 = 8 + 8 + 5 + 5 です。

 26 (-24) --> 2 --> False

この問題を正しく解決するには、貪欲なアプローチを放棄する必要があります。可能な最大数を減算するだけでは、必ずしも十分ではありません。あなたの質問に答えるには、はい、ここでは再帰的な解決策が必要です。

def numPens(n):
    """
    n is a non-negative integer

    Returns True if some non-negative integer combination of 5, 8 and 24 equals n
    Otherwise returns False.
    """
    # Base case: Negative numbers are by definition false.
    if n < 0:
        return False

    # Base case: 0 is true. It is formed by a combination of zero addends,
    # and zero is a non-negative integer.
    if n == 0:
        return True

    # General case: Try subtracting *each* of the possible numbers, not just
    # the largest one. No matter what n-x will always be smaller than n so
    # eventually we'll reach one of the base cases (either a negative number or 0).
    for x in (24, 8, 5):
        if numPens(n - x):
            return True

    return False

これは問題を解決するための最も簡単な方法であり、小さな数に対してはかなりうまく機能します。大きな数の場合、同じ数を複数回評価する方法が原因で遅くなります。読者に委ねられた最適化は、動的計画法を使用して重複した計算を排除することです。

于 2013-03-22T16:08:53.853 に答える
3

より効率的な (O(1)) アルゴリズムがあります。

たとえば、次のように追加できます。

if n > 40: 
    return True

あなたのベースケースの1つとして！

残りの値 (n < 40) のルックアップ テーブルを維持することで、さらに効率的にすることができます。

これができる理由は次のとおりです: http://en.wikipedia.org/wiki/Coin_problem#n_.3D_2

于 2013-03-22T17:04:24.667 に答える
1

明らかに、これは再帰的な問題です。以下はおそらく最も単純なコードです。

def numPens(n):
    if n < 5:
        return False
    elif n==5 or n==8 or n==24:
        return True
    else:
        return numPens(n-5) or numPens(n-8) or numPens(n-24)

より効率的で堅牢である必要がある場合は、自分で改善することができます。

于 2013-03-22T16:19:18.267 に答える
1

n=5a+8b+24c <=> n=5a+8(b+3c)、したがって、関数を持つことができます：

def numPens(n):
    if n < 5:
        return False
    if n % 8 == 0 or n % 5 == 0:
        return True
    else:
        return numPens(n-8) or numPens(n-5)
于 2013-03-22T17:00:59.137 に答える
0 
def numPens(n):
    global cantidad
    cantidad = cantidad + 1
    if n < 5:
        return False
    elif n%5==0 or n%8==0 or n%24==0:
        return True
    else:
        return numPens(n-5) or numPens(n-8) or numPens(n-24)
于 2013-03-22T17:14:24.587 に答える