0

以下のアルゴリズムを検討してください。 

  for(j1 = n upto 0)
     for(j2 = n-j1 upto 0)
       for(j3 = n-j1-j2 upto 0)
        .
         .
           for (jmax = n -j1 - j2 - j_(max-1))
            {
             count++;
             product.append(j1 * j2 ... jmax); // just an example
            }

ご覧のとおり、上記のアルゴ スニペットに関するいくつかの関連ポイント:

  1. 可変数の for ループを持つアルゴリズムをリストしました。
  2. 最も内側の各ループで i が計算した結果は、リストに追加されます。このリストは「count」の次元まで大きくなります。

この問題は再帰の適切な候補ですか? はいの場合、問題を分割する方法が本当にわかりません。私はこれを Python でコード化しようとしていますが、皆さんからのコードは期待していません。正しい方向へのいくつかのポインタまたは例。ありがとうございました。

これはサンプルケースの最初の試みですhttp://pastebin.com/PiLNTWED

4

5 に答える 5

1

あなたのアルゴリズムは、合計以下の負でない整数のすべてのm-tuples (疑似コードからmのmax添字である) を見つけています。Python では、これを表現する最も自然な方法は、再帰ジェネレーターを使用することです。jn

def gen_tuples(m, n):
    if m == 0:
        yield ()
    else:
        for x in range(n, -1, -1):
            for sub_result in gen_tuples(m-1, n-x):
                yield (x,)+sub_result

出力例:

>>> for x, y, z in gen_sums(3, 3):
    print(x, y, z)

3 0 0
2 1 0
2 0 1
2 0 0
1 2 0
1 1 1
1 1 0
1 0 2
1 0 1
1 0 0
0 3 0
0 2 1
0 2 0
0 1 2
0 1 1
0 1 0
0 0 3
0 0 2
0 0 1
0 0 0
于 2013-04-27T10:45:48.150 に答える
0

-- Blckgnht による優れたリストへの応答として -- ここで n = 2 および max = 3 の場合を考えてみましょう 

def simpletest():    

    '''
    I am going to just test the algo listing with assumption
    degree n = 2
    max = dim(m_p(n-1)) = 3, 
    so j1 j2 and upto j3 are required for every entry into m_p(degree2)
    Lets just print j1,j2,j3 to verify if the function
    works in other general version where the number of for loops is not known
    '''
    n = 2
    count = 0
    for j1 in range(n, -1, -1):
        for j2 in range(n -j1, -1, -1):
            j3 = (n-(j1+j2)) 
            count = count + 1
            print 'To calculate m_p(%d)[%d], j1,j2,j3 = ' %(n,count), j1, j2, j3

    assert(count==6)        # just a checkpoint. See P.169 for a proof
    print 'No. of entries =', count

このコードの出力 (そして正しい)。 

    In [54]: %run _myCode/Python/invariant_hack.py
To calculate m_p(2)[1], j1,j2,j3 =  2 0 0
To calculate m_p(2)[2], j1,j2,j3 =  1 1 0
To calculate m_p(2)[3], j1,j2,j3 =  1 0 1
To calculate m_p(2)[4], j1,j2,j3 =  0 2 0
To calculate m_p(2)[5], j1,j2,j3 =  0 1 1
To calculate m_p(2)[6], j1,j2,j3 =  0 0 2
No. of entries = 6
于 2013-04-27T11:56:00.273 に答える
0

通常、ループを再帰呼び出しに変換する場合は、ステートメントをステートメントforに置き換える必要があります。ネストされたループの場合、これらを関数呼び出しに変換します。forif

練習のために、機能するコードの愚かな翻訳から始めて、後で最適化できる場所を確認してみてください。

あなたの状況に適用しようとするアイデアを提供するために、私は次のように翻訳します：

results = []
for i in range(n):
    results.append(do_stuff(i, n))

このようなものに：

results = []

def loop(n, results, i=0):
    if i >= n:
        return results
    results.append(do_stuff(i, n))
    i += 1
    loop(n, results, i)

結果リストを返す処理にはさまざまな方法がありますが、必要に応じて調整できます。

于 2013-04-24T14:10:55.100 に答える
0

おもちゃの例は一種の末尾再帰に変換されるため、個人的には、再帰バージョンがコードのレビューとメンテナンスに役立つとは思いません。

ただし、原則に慣れるために、個々のループから不変部分/一般的な用語を除外して、パターンを識別しようとします (後でそれを証明するのが最善です!)。書かれる再帰的手続きの署名を修正できるはずです。ループ本体に固有の部分で肉付けします（終了条件を忘れないでください）。

于 2013-04-24T13:56:56.250 に答える