0

私は問題に対処しており、可能なすべての組み合わせをテストし、「最も安い」ものを表示する再帰的な方法を作成しようとしています。

タスクは次のとおりです。

  • 動的に割り当てられて埋められた Array[n] 番号があります。たとえば、{1、3、4、2}。配列は次のように定義されます。
    int *array;
  • 配列のサイズを好み、変数 Size に入れました。
  • 配列内の 2 つの数値はそれぞれセグメントの上部と下部を示しているため、この場合、配列には 3 つのセグメントがあります。セグメントは、A = 1 3 、B = 3 4 、C = 4 2 です。
  • 私は彼らがいる順番で彼らに参加しなければなりません。最後の2つから最初の1つに参加することも、中央から側面に参加することもできますが、「最も安い」方法を選択する必要があります.
  • 2 つのセグメントに参加するたびに: A = 1 3 と B = 3 4 。そのコストを次のように計算します: (1 * 4) + 3. セグメントの端にある数値を乗算し、セグメント間の数値に合計します。
  • 入力は常に 2 つ以上のセグメントであり、配列内の 3 つ以上の数字を意味します。

実際に私がする必要があるのは：

For two segments: array= "1 2 3"
A={1,2},B={2,3} ---- (1*3)+2 -> Cost = 5

For three segments: array= "30 20 25 10"
A={30,20},B={20,25},C={25,10} ----
case1 - [(30*25)+20] + [(30*10)+25] -> Cost = 1095
case2 - [(20*10)+25] + [(30*10)+20] /> Cost = 545

したがって、2 番目のコストの方が優れていることがはっきりとわかるので、その値を返します。より多くのセグメントでは、計算の数が大幅に増加しますが、それは私が必要とするものには問題ありません.

私はさまざまな方法で何度も試してきましたが、すべてのポインターと混乱しており、再帰関数も苦手です。私が十分に具体的であったかどうかはわかりませんが、何か明確でない場合は喜んで説明します.

コード全体を必要としないことは確かです。おそらく、それを行う方法についての説明やアイデアが評価されるでしょう:)

4

1 に答える 1

0

数Aの配列n、A[j]j番目の要素、および A[i,k]i番目からk番目の要素までのAのサブ配列とします。インデックスは0からカウントを開始するため、A = A[0, n-1]。結合操作の結果は何ですか？たとえば、A = { 1, 2, 3 }2つのセグメントが1,2あり、2,3正しく結合されていると仮定します1,3。

それぞれが2つの部分でバイパートAを結合するため、可能なすべての結合A、つまりn-2可能性をテストし、最小のコストで1つを選択することで再帰できます。多分この方程式はあなたにアイデアを与えるでしょう。

/* cost of join two segments of A ending respective starting at j */
cost(A,j) = ( A[j-1]*A[j+1] ) + A[j]

 /* minmal cost of joining(A) when joining at j */
mincost(A,j) = mincost( A[0,j-1] ) + cost(A,j) + mincost( A[j+1,n-1] )

/* test all possible join, use minimal one */
mincost(A) = min[j]: mincost(A,j)

n=3を使用すると、再帰を終了しますcost(A,1)。

使用可能なアルゴリズムの場合、おそらくこれをキャッシュする必要がありmincost(A[x,y])ます。これは動的計画法と呼ばれます。

C では、asはC構造に直接対応しない場所A[j]に翻訳できますが、大まかに次のように翻訳できます。*(A+j)A[i,k]

 struct Array { 
          int * A; 
          int index_first;
          int index_last;
 };
于 2012-11-28T16:03:21.537 に答える