Lösen von Problemen rekursiv in C

Question

Unser Professor hat uns die folgende Zuordnung:

A "correct" series is one in which the sum of its members equals to the index of its first member.

Das Programm soll die Länge der längsten „richtigen“ Serie innerhalb einer Reihe von n Zahlen finden.

Beispiel: Wenn die Eingangsserie arr[4]={1, 1, 0, 0} wäre, wäre der Ausgang (längste "richtige" Serie) 3.
arr[0]=1. 0!=1 daher ist die längste Serie hier 0.
arr[1]=1,and 1=1. aber die folgenden Mitglieder summieren sich auch zu 1 wie folgt:
1=arr[1]+arr[2]+arr[3] = 1+ 0 + 0, daher ist die längste Serie hier 3.

Die Ausgabe in diesem Beispiel lautet 3.

Dies ist, was ich bisher:

int solve(int arr[], int index, int length,int sum_so_far) 
{ 
    int maxwith,maxwithout; 

    if(index==length) 
     return 0; 

    maxwith = 1+ solve(arr,index+1,length,sum_so_far+arr[index]); 
    maxwithout = solve(arr,index+1,length,arr[index+1]); 

    if(sum_so_far+arr[index]==index) 
     if(maxwith>maxwithout) 
      return maxwith; 

    return maxwithout; 

    return 0; 
} 



int longestIndex(int arr[], int index,int length) 
{ 
    return solve(arr,0,length,0); 
} 

Was mache ich falsch hier?

Wir sind nicht uns Schleifen auf diese Aufgabe.

Answer 1

Es scheint mir, dass das Problem hier liegt:

if(sum_so_far+arr[index]==index) 

Du vergleichst die Summe so weit mit dem aktuellen Index, aber man sollte es mit dem ersten Index in der Reihe werden zu vergleichen. Es scheint mir, dass es besser wäre, wenn du mit dem letzten Element von arr in Richtung des ersten beginnst, anstatt in die natürliche Reihenfolge zu gehen. Auf diese Weise beginnen Sie mit dem Summieren von Elementen, bis die Summe dem aktuellen Index entspricht.

Answer 2

Schreiben Sie zuerst eine Funktion, die eine Reihe von gegebenem Startindex und gegebener Länge für die Bedingung "Summe seiner Mitglieder" testet. Schreiben Sie dann eine zweite Funktion, die nach der längsten Reihe in Ihrem Array sucht, in der nur der Startindex angegeben ist (das Schleifen der Unterserienlänge in absteigender Reihenfolge sollte dies tun); Diese Funktion kann die erste aufrufen. Schreiben Sie als letztes eine dritte Funktion, die alle Startindizes durchläuft und die Funktion Nummer zwei aufruft.

Oh, Moment mal, es gibt keine Rekursion erforderlich ist mehr vorhanden, so viel Gehirn-Zwirn ist weg ... :-)

Answer 3

Hmm, gibt es mehrere Probleme mit diesem Programm.

Am offensichtlichsten, "return maxwithout; return 0;" sollte einen Kompilierungsfehler geben: Es gibt keine Möglichkeit, zu dieser letzten Return-Anweisung zu gelangen.

Zweitens rekursiv, um auf dem "maxwith" Pfad zu lösen, bis Sie das Ende des Arrays erreichen. Dann wirst du in maxwithout rekursieren und es zum ersten Mal mit index = 4 treffen. Ich denke nicht, dass das funktionieren wird.

Offen gesagt, glaube ich nicht, dass dieses Problem wirklich Rekursion erfordert. Die natürlichste Lösung wäre eine verschachtelte Schleife:

Oder etwas zu diesem Zweck.

Hat das Problem zur Lösung mit Rekursion aufgerufen, oder war das nur Ihre erste Idee zu einer guten Lösung?

bearbeiten

Okay, so dass Sie Rekursion verwenden. Ich denke, der Sinn der Lektion besteht darin, Rekursion zu lernen, nicht unbedingt, um das Problem auf die natürlichste oder effizienteste Art und Weise zu lösen. (Ich persönlich denke, der Lehrer sollte ein Problem haben, bei dem Rekursion eine natürliche Lösung war, aber ich denke, wir sind heute nicht hier, um den Lehrer zu kritisieren.)

Ich möchte deine Hausaufgaben nicht machen du, aber ich gebe dir einen Hinweis. Sie können Rekursion verwenden, um eine Schleife zu simulieren, indem Sie die break-Bedingung am Anfang der Funktion setzen und den rekursiven Aufruf am Ende der Funktion mit einem Parameter +1 setzen. Das heißt, statt

for (int x=0;x<10;++x) { ... whatever ...} 

Schreiben Sie

void forx(int x) 
{ 
    if (x>=10) 
    return; 
    ... whatever ... 
    forx(x+1); 
} 

Also in diesem Fall schreiben kann ich etwas tun würde, wie:

void endloop(int start, int end) 
{ 
    if (end>=arrayLength) 
    return; 
    ... work on running total ... 
    endloop(start, end+1); 
} 

void startloop(int start) 
{ 
    if (start>=arrayLength) 
    return; 
    endloop(start, start); 
} 
int main() 
{ 
    ... setup ... 
    startloop(0); 
    ... output ... 
} 

Parameterlisten sind nicht unbedingt vollständig. Wie gesagt, ich möchte deine Hausaufgaben nicht für dich machen, sondern nur einen Hinweis geben, um loszulegen.