2

サブセット和検索を実行するようにTI-83をプログラムしようとしています。したがって、長さNのリストが与えられた場合、与えられた長さLのすべてのリストを見つけたいと思います。その合計は、与えられた値Vになります。

これは、通常のサブセット和問題とは少し異なります。これは、すべての長さではなく、指定された長さのサブセットのみを検索しているためです。また、作業中のプログラムを呼び出すことができないため、再帰が必ずしも最初の選択肢ではありません。

ネストされたループを使用してタスクを簡単に実行できますが、Lの値が5より大きい場合は面倒になります。動的なソリューションを試していますが、どこにも到達していません。

実際、この時点で、私はリスト参照を正しく取得しようとしているだけなので、それが私が見ているものです。例を見てみましょう：

L1={p,q,r,s,t,u}

それで

N=6

長さ3のすべてのサブセットを探して、比較的短くして、L = 3（6c3 =合計20の出力）にします。

理想的には、検索されるリスト参照は次のとおりです。

{1,2,3}
{1,2,4}
{1,2,5}
{1,2,6}
{1,3,4}
{1,3,5}
{1,3,6}
{1,4,5}
{1,4,6}
{1,5,6}
{2,3,4}
{2,3,5}
{2,3,6}
{2,4,5}
{2,4,6}
{2,5,6}
{3,4,5}
{3,4,6}
{3,5,6}
{4,5,6}

明らかに次の方法で達成されます。

FOR A,1,N-2
    FOR B,A+1,N-1
        FOR C,B+1,N
            display {A,B,C}
        END
    END
END

最初にNのデータを降順で並べ替えて、検索を短縮する条件を検索できるようにします。ループ内のA、B、Cの値をインクリメントすると、FORループを使用してさまざまな場所でデータを少し台無しにします。

また、より優れた動的ソリューションを探しています。私はウェブ上でいくつかの調査を行いましたが、そこにあるものを私の特定の状況に適応させることができないようです。

どんな助けでもいただければ幸いです。小説を書かないように簡潔にしようとしていますが、私が何をしようとしているのかを説明しています。必要に応じて詳細をお知らせします。

4

1 に答える 1

1

最適化のために、すでに値 V を超えている検索のサブツリーを単にスキップしたいだけです。許可される深さに上限を設定するのが最善です。

私はこのようなものに行きます（深さ3の場合）：

N is the total number of array elements.
L is the desired length (3).
V is the desired sum
Y[] is the array
Z is the total

Z = 0
IF Z <= V
  FOR A,1,N-L
    Z = Z + Y[A]
    IF Z <= V
      FOR B,A+1,N-L+1
        Z = Z + Y[B]
        IF Z <= V
          FOR C,B+1,N-L+2
            Z = Z + Y[C]
            IF Z = V
              DISPLAY {A,B,C}
            END
            Z = Z - Y[C]
          END
        END
        Z = Z - Y[B]
      END
    END
    Z = Z - Y[A]
  END
END

これはかなり複雑ですが、基本的には、目的の値を既に超えているかどうかをすべての段階でチェックし、効率対策として下位のサブツリーのチェックを拒否します。また、現在のレベルの現在の合計を保持するため、より低いレベルでチェックするときに多数の追加を行う必要がありません。これは、Z に対する配列値の加算と減算です。

より多くの深さを処理するように変更すると、さらに複雑になります(11 レベルの変数を から まで使用します (移動して下に移動したいD場合や、TI BASIC で変数名に複数の文字が許可されている場合) 。 ）。KNLWX

私が考えることができる唯一の他の非再帰的な方法は、値グループの配列を使用して反復で再帰をエミュレートすることです。

于 2009-12-29T04:28:08.383 に答える