www.fernstudenten.de

Verfasst: **01.06.09 16:09**

Hallo Leute,

hat schon jemand von euch die Einsendeaufgabe zu ALG01 fertig gemacht?
Ich hänge an den Aufgaben 2 und 3, wo es darum geht die Anzahl der Knoten und Ebenen im Binärbaum zu zählen.

zu 2.: Um die Anzahl der Knoten zu ermitteln, lasse ich ihn einfach alle Knoten durchgehen und einen Zähler hochzählen.

zu 3.: Für die Anzahl der Ebenen lasse ich Ihn jeweils links und rechts bis zur letzten Zahl nach unten laufen und zähle die "Stufen".

Klappt auch beides soweit, jedoch benötige ich zur Realisierung globale Hilfsvariablen, weil man ja durch die Rekursion keine Variablen innerhalb der Funktionen erzeugen kann.
Ich weiß nicht ob das so OK ist oder ob es nicht bessere Lösungen gibt.
Vielleicht kann mir jemand mal seine Ansätze posten.

Gruß
Jan

Verfasst: **04.06.09 19:08**

Du kannst doch eine Rekursive Funktion schreiben, die immer zurückgibt, wieviele Knoten unterhalb der aktuellen Rekursionsebene vorhanden sind. Dann brauchst Du keine globalen Variablen.

Also beispielsweise

Code: Alles auswählen

    class Program
    {
        static void Main(string[] args)
        {
            int wert = x(4);
            Console.WriteLine("Wert=" + wert);
            Console.ReadKey();
        }
        static int x(int zahl)
        {
            int zaehler = 0;
            if (zahl > 0)
            {
                // Anzahl Rekursionen wird durch übergebene zahl bestimmt
                for(int i=0;i<zahl;i++) zaehler += x(zahl - 1);
            }
            // bei zahl 0 wird ist man in der untersten Ebene und 
            // die Funktion gibt 1 zurück da es keine weitere Rekursion mehr gibt
            if (zahl == 0) zaehler = 1;
            return zaehler;
        }
    }

Das Beispiel ist zwar in C# dürfte aber leicht nachzuvollziehen sein.

Die Ausgabe ist 24 da die Funktion insgesamt 24 mal aufgerufen wird. Ruft man x(3) auf, dann ist der Wert 6, bei x(2) wird er 3 sein, bei x(1) gibt es nur den einen Aufruf, daher ist die Ausgabe 1.

www.fernstudenten.de

ALG01 - Einsendeaufgaben

ALG01 - Einsendeaufgaben