Ich kann nur Brute-Force-Lösung denken. Wie kann ich Rekursionen durchführen?

Question

Es gibt zwei Integer-Arrays A und B gleicher Länge. Füge Elemente von A zu Elementen von B hinzu, so dass alle Elemente in B (wenn möglich) gleich werden. Man kann i-tes Element von A zu i'th oder i + 1 (wenn i! = Len (A)) Element von nur B hinzufügen, oder nichts hinzufügen und zum nächsten Element weitergehen. Ein Element von A kann nur einmal verwendet werden.

Beispiel: B = [3,5,4,2], A = [2,1,2,1]

B [0] + = a [0]

B [2] + = A [1]

B [3] + = A [2] + A [3]

So wird B [5,5,5,5]

Answer 1

Ich würde keine Rekursion für dieses Problem in Betracht ziehen. Eine einfache while ist ausreichend.

Das erste, was ist zu bemerken, dass b_new [0] nur zwei Werte haben kann

b_new[0] = b[0];  // and a[0] not used 
b_new[0] = b[0] + a[0]; // and a[0] used 

Für b_new [1], die vier Möglichkeiten verlässt

b_new[1] = b[1];    // and a[1] not used 
b_new[1] = b[1] + a[0];  // and a[1] not used, only valid if a[0] wasn't used 
b_new[1] = b[1] + a[0] + a[1]; // and a[1] used, only valid if a[0] wasn't used 
b_new[1] = b[1] + a[1];  // and a[1] used 

Für diese Sie immer Vorrang geben sollte die beiden ersten, so dass a [1] zur Berechnung von b [2] frei ist.

in einer Funktion zum Ausdruck, dass sein würde:

int tryit(int idx, int target, int* a, int* b, int previous_a_used) 
{ 
    if (b[idx] == target) 
    { 
    return 0; // a[idx] is free 
    } 

    if (!previous_a_used) 
    { 
    if ((b[idx] + a[idx-1]) == target) 
    { 
     printf("Trying: b[%d] += a[%d]\n", idx, idx-1); 
     return 0; // a[idx] is free 
    } 

    if ((b[idx] + a[idx-1] + a[idx]) == target) 
    { 
     printf("Trying: b[%d] += a[%d] + a[%d]\n", idx, idx-1, idx); 
     return 1; // a[idx] is used 
    } 
    } 

    if ((b[idx] + a[idx]) == target) 
    { 
    printf("Trying: b[%d] += a[%d]\n", idx, idx); 
    return 1; // a[idx] is used 
    } 

    return -1; // failed - no solution 
} 

Die Funktion verwendet werden kann, wie:

printf("Trying: b[%d] += a[%d]\n", 0, 0); 

    target = b[0] + a[0]; // Try one of the two possibilities for target 
    previous_a_used = 1; // a[0] was used 
    idx = 1;    // move on to next index for b 

    while (idx < N) 
    { 
    previous_a_used = tryit(idx, target, a, b, previous_a_used); 
    if (previous_a_used < 0) 
    { 
     printf("failed\n"); 
     break; 
    } 
    ++idx; // move on to next index for b 
    } 

    if (previous_a_used >= 0) 
    { 
    printf("Solved\n"); 
    } 

Denken Sie daran, fügen Sie Code zur Überprüfung der anderen Zielwert (das heißt target = b[0]).