次の計算を行うための宿題用の再帰関数を作成しました。
入力の場合:
1 2 3 4
これを行う必要があります:
((1*3)+2) + ((1*4)+3) = 13
、これは より小さいため、((2*4)+3) + ((1*4)+2) = 17
13 を返します。文字では、この計算を行う必要があります:((A*C)+B) + ((A*D)+C)
他のオプションと比較します。この場合、2 つのオプションがあります: ((B*D)+C) + ((A*D)+C)
.
一言で言えば。数字は、セグメントの両端にある「ネジ」の数を示しています。セグメントは常に 2 つの数字で形成されます。セグメント A {1 2}、B {2 3}、C {3 4}。
タスクは、すべての N セグメントを結合することです。それを行うための「最も安い」方法を見つけなければなりません。2 つのセグメント (たとえば A と B) に参加するたびに、次のようにします。
A の「下のネジ」(1 - 最初の数字)* B の「上のネジ」(3 - 3 番目の数字)+「結合ネジ」(2 - 間の数字)。
私はそれらを順番に結合する必要があり、常に ABCD の順番で終了する必要があります。しかし、私はどこから始めるかを選ぶことができます。A を B に結合してから AB を C に結合するか、B を C に結合してから A を BC に結合することができます。基本的に、「コスト」が最も低くなる場合があり、それが返される値になります。
今のところこれを行いましたが、混乱しました:
これ*help
は、再帰で取得した新しい値を格納するために使用する相互計算配列です。
int *help;
は、次の*mezi
ように定義された動的に割り当てられる配列です。
int *mezi;
内部は のように見え{0,4,1,2,3,4,-1}
ます。
mezi[0] = here is stored the total prize in the recursion.
mezi[1] = here is stored the number of values in the array, 4 for 4 values (3 segments).
mezi[n+2] = the last number (-1), its just an identifier to find out the number of values.
これが私のコードです:
int findmin(int *mezi, int *pomocny)
{
int i,j,k;
int prize, prizemin, mini, minih;
for (i=3;i<mezi[1];i++) {
prize = mezi[i-1] * mezi[i+1] + mezi[i];
if (i==3) { mini = i; minih = prize; }
if (prize < minih) { mini = i; minih = prize; }
if (mezi[1] > 3){
k=2;
for (j=2;j<mezi[1];j++) {
if (j != mini) help[k] = mezi[j];
k++;
}
help[1] = (mezi[1]-1);
}
help[0] += prize;
findmin(help,help);
}
prizemin = help[0];
return prizemin;
}
少し前に C を使い始めましたが、再帰関数が私を混乱させます。私は助けに感謝します。ありがとう :)