größte Zahl aus einem Array mittels rekursive Fkt ermitteln



  • Ich habe nicht das Beispiel kritisiert sondern seldons Ausschweifung zu Threading. Den Bezug habe ich extra zitiert ...



  • Mit der Ausschweifung bezog ich mich auf SeppJs Bisektionsidee, die bei großen Arrays mit Threading durchaus Sinn macht. Wobei man in der Realität wohl auch nicht komplett rekursiv vorgehen würde.



  • Ich habe nun folgende Lösung per Rekursion:

    float tmp_max;
    
    float max_zahl(int anzahl, float zahlen[]){
    
    	if (anzahl > 0)
    	{
    		if (tmp_max < zahlen[anzahl-1])
    		{
    			tmp_max=zahlen[anzahl-1];
    		}
    		max_zahl(anzahl-1, zahlen);
    	}
    	else
    		return tmp_max;
    } 
    
    int main(){ 
    
    	float zahlen[] = {1.1, 1.4, 2.5, 2.1, 9.5, 4.7}; 
    	int anzahl=(sizeof(zahlen)/sizeof(*zahlen)); 
    
    	max_zahl(anzahl, zahlen);
    
    	cout << tmp_max << endl;
    
    	system("PAUSE"); 
    }
    

    Problem ist hierbei tmp_max (globale)Variable.
    Wenn ich der Funktion definiere, darf es nur bei dem ersten Aufruf deklariert werden, wiederum kann ich dann die Variable in main() nicht aufrufen.

    Habt ihr hierzu Verbesserungsvorschläge?
    Hiermit ist die Rekursion erfüllt, oder?

    Danke



  • Du gibst tmp_max doch per return zurück, wieso benutzt du nicht den Rückgabewert? Außerdem fehlt in dem if-Zweig das return-Statement ... fällt dir natürlich nicht auf, aber undefiniertes Verhalten dürfte es trotzdem haben...


  • Mod

    dslpro schrieb:

    Habt ihr hierzu Verbesserungsvorschläge?

    Reich die Daten weiter! Deine Funktion darf ja ruhig auch mehr Parameter haben. Zur Not machst du einen Wrapper um die eigentliche Rekursion:

    float eigentliche_rekursion(float momentanes_maximum, float zahlen[], int anzahl)
    {
      // Überlasse ich dir.
    }
    
    float max_zahl(int anzahl, float zahlen[])
    {
      if (anzahl > 0)
      {
        return eigentliche_rekursion(zahlen + 1, anzahl - 1);
      }
      else
        // Was auch immer
    }
    

    An sich ist diese Technik aber gar nicht nötig, seldons Beitrag zeigt doch schon eine Möglichkeit, das alles in einer Funktion zu machen. Du denkst noch viel zu imperativ. Bei der Rekursion geht es nicht darum, einen Schritt nach dem anderen zu machen. Du musst nicht zwei Zahlen vergleichen, das Ergebnis irgendwohin packen, dann den nächsten Schritt aufrufen. Das ist Schleifendenken. Darum geht es ja gerade nicht. Das rekursive Programm legt erst einmal alles auf den Stack und dann, wenn es am Ende der Rekursion angekommen ist, wird alles rückwärts abgearbeitet. Dabei geben die Ebenen oben auf dem Stack ihre Ergebnisse an die unteren Ebenen weiter, nicht umgekehrt.

    Schleifendenken, Maximum von 5 Zahlen:
    -Setze erste Zahl als bisheriges Maximum
    -Setze bisheriges Maximum als max(bisheriges Maximum, zweite Zahl)
    -Setze bisheriges Maximum als max(bisheriges Maximum, dritte Zahl)
    -Setze bisheriges Maximum als max(bisheriges Maximum, vierte Zahl)
    -Setze bisheriges Maximum als max(bisheriges Maximum, fünfte Zahl)
    -Maximum ist gleich bisherigem Maximum

    Rekursiv gedacht, Maximum von 5 Zahlen:
    -Maximum ist gleich max(erste Zahl, max(zweite Zahl, max(dritte Zahl, max(vierte Zahl, fünfte Zahl) ) ) )

    Hiermit ist die Rekursion erfüllt, oder?

    Technisch ja, aber globale Variablen würde ich dir als Lehrer um die Ohren hauen. Die Lösung ist derzeit noch zu schlecht. Außerdem noch die Fehler, die Bashar genannt hat. Und natürlich mein obiger, langer Absatz, dass du noch nicht verstanden hast, worum es überhaupt geht (was normal ist, Rekursion finden viele Leute schwer, wenn sie vorher imperative Programmierung gewöhnt sind).



  • Du brauchst doch kein globales tmp_max.

    Du nimmst in der Funktion max_zahl einen Wert aus dem Array
    Dann rufst du max_zahl mit dem Rest von dem Array auf und speicherst auch diesen Wert loakal ab. Den Maximalwert von diesen beiden gibst du zurück.
    Wenn das Array nur aus einem Element besteht, hast du schon mal einen Maximalwert gefunden.

    float max_zahl(int anzahl, float zahlen[])
    { float max_rest, aktuell;
    
      if ( irgendetwas mit anzahl)
        aktuell = zahlen[0];
        max_rest = max_zahl(anzahl-1,zahlen+1);
    ....
    
    }
    


  • Ich habe mich heut nochmal hingesetzt und und nach hin und her eine Möglichkeit gefunden und die globale Variable abgeschafft
    stattdessen static variable eingeführt.

    Wenn ich die Funktion als void deklariere und per cout ausgeben, funktioniert es,
    wenn ich jedoch mit Rückgabe Werten arbeite, funktioniert es nicht bzw.
    erhalte als Ausgabe: -1.#IND

    Wo mache ich ein Fehler?
    Code:

    float max_zahl(int anzahl, float zahlen[]){
    
    	static float tmp_max = zahlen[anzahl];
    
    	if (anzahl > 0)
    	{
    		if (tmp_max < zahlen[anzahl-1])
    		{
    			tmp_max=zahlen[anzahl-1];
    		}
    		max_zahl(anzahl-1, zahlen);
    	}
    	else
    		return tmp_max;
    } 
    
    int main(){ 
    
    	float zahlen[] = {1.1, 12.4, 2.5, 2.1, 9.5, 4.7}; 
    	int anzahl=(sizeof(zahlen)/sizeof(*zahlen)); 
    
    	float erg=max_zahl(anzahl, zahlen);
    
    	cout << erg << endl;
    
    	system("PAUSE"); 
    }
    


  • lokal-statische Variablen sind fast genauso schlimm wie globale!
    Vermeide sie doch einfach ganz und gehe da ganz anderes dran, nämlich rekursiv:

    SeppJ schrieb:

    Rekursiv gedacht, Maximum von 5 Zahlen:
    -Maximum ist gleich max(erste Zahl, max(zweite Zahl, max(dritte Zahl, max(vierte Zahl, fünfte Zahl) ) ) )



  • dslpro schrieb:

    Ich habe mich heut nochmal hingesetzt und und nach hin und her eine Möglichkeit gefunden und die globale Variable abgeschafft
    stattdessen static variable eingeführt.

    Toll, das ist bis auf die Sichtbarkeit mehr oder weniger das gleiche 🙂

    Wenn ich die Funktion als void deklariere und per cout ausgeben, funktioniert es,
    wenn ich jedoch mit Rückgabe Werten arbeite, funktioniert es nicht bzw.
    erhalte als Ausgabe: -1.#IND

    Ich hatte dir schon geschrieben, dass bei dir nicht in jedem Zweig ein return steht. Das erzeugt undefiniertes Verhalten, konkret in deinem Fall komische Werte. Aber ich schreib dir das gerne immer wieder.


  • Mod

    Wenn dein Compiler cout akzeptiert, dann ist das übrigens ein C++-Compiler. Und das cout selber ist auch C++. Der Rest des Programms ist jedoch C (naja, so wirklich stark un-C++-ig ist es nicht, aber du möchtest ja anscheinen C machen). Mische nicht C mit C++! Das geht nur ganz am Anfang noch gut und wird dir schon sehr bald um die Ohren fliegen. Benutze für C auch einen C-Compiler. Die meisten C++-Compiler können auch C. Man muss sie in der Regel bloß ein bisschen anders aufrufen.


Anmelden zum Antworten