3

可変長配列 ( A[i]for all iinなど) を使用する言語で作業していて、 length の可変長配列内の項目の( ) 可変長配列を受け取る1..A.lengthルーチンを作成する必要があり、すべてのプロシージャを呼び出す必要があるとします。最初の配列から最初の配列が選択され、2 番目の配列から 2 番目の配列が選択されます 。nn : 1..8nn

視覚化する具体的な何かが必要な場合は、ルーチンが次のようなデータを取得する必要があると想像してください。

[ [ 'top hat', 'bowler', 'derby' ], [ 'bow tie', 'cravat', 'ascot', 'bolo'] ... ['jackboots','galoshes','sneakers','slippers']]

そして、次のプロシージャ コールを (任意の順序で) 行います。

try_on ['top hat', 'bow tie', ... 'jackboots']
try_on ['top hat', 'bow tie', ... 'galoshes']
 :
try_on ['derby','bolo',...'slippers']

これは中国語のメニューの問題と呼ばれることもあり、for fixednは非常に簡単にコーディングできます (たとえばn、疑似コードで for = 3)。

procedure register_combination( items : array [1..3] of vararray of An_item)
    for each i1 from items[1]
        for each i2 from items[2]
            for each i3 from items[3]
                register( [ii,i2,i3] )

しかし、n次のような署名を与えると、変化する可能性があります。

procedure register_combination( items : vararray of vararray of An_item)

書かれているコードには見苦しい case ステートメントが含まれていましたが、これをより単純なソリューションに置き換えました。しかし、これがリファクタリングの最良の方法であるかどうかはわかりません (そして、これが唯一の方法ではないことは確かです)。

どのようにしますか？巧妙で驚くべきことは良いことですが、明確で保守しやすいことはより優れています。私はこのコードを通過しているだけで、コールバックされたくありません。簡潔で、明確で、賢いことが理想的です。

編集: 他の人が応答する機会があった後、今日の後半にソリューションを投稿します。

Teaser: 私は再帰的なソリューションを売り込もうとしましたが、彼らはそれを受け入れなかったので、HLL で fortran を書くことに固執しなければなりませんでした。

私が行った答えは、以下に投稿されています。

4

3 に答える 3

2

再帰アルゴリズム

procedure register_combination( items )
        register_combination2( [], items [1:] )

procedure register_combination2( head, items)
    if items == []
        print head
    else
       for i in items[0]
           register_combination2( head ++ i, items [1:] )

または、インデックスに配列を使用して最適化された末尾の呼び出しと同じであり、対応する配列の長さに達するまで最後のインデックスをインクリメントし、インクリメントを繰り上げます。

于 2009-03-18T17:00:18.350 に答える
1

再帰。

または、さらに良いことに、スタックのような構造と while ステートメントを使用して再帰を排除しようとします。

あなたが述べた問題（可変引数で関数を呼び出す）については、コーディングしているプログラミング言語に完全に依存します。それらの多くは、可変引数を渡すことができます。

于 2009-03-18T16:55:42.353 に答える
0

彼らは再帰に反対していたので（質問しないでください）、私は厄介なケースステートメントに反対していたので（結局のところ、バグを隠していました）、私はこれに行きました：

procedure register_combination( items : vararray of vararray of An_item)
    possible_combinations = 1
    for each item_list in items
        possible_combinations = possible_combinations * item_list.length
    for i from 0 to possible_combinations-1
        index = i
        this_combination = []
        for each item_list in items
            item_from_this_list = index mod item_list.length
            this_combination << item_list[item_from_this_list]
            index = index div item_list.length
        register_combination(this_combination)

基本的には、組み合わせがいくつあるかを計算し、それぞれに番号を割り当ててから、対応する組み合わせを生成する番号をループします。新しいトリックではないと思いますが、知っておく価値のあるトリックです。

より短く、リストの長さの実際的な組み合わせで機能し (2^60 を超える組み合わせがある場合、別の問題があります)、再帰的ではなく、バグもありません。

于 2009-03-20T17:50:35.897 に答える