Entwickler-Ecke :: Thema anzeigen - Rekursion: Index des kleinsten Elementes ermitteln

Smaik - Mo 15.03.10 17:48
Titel: Rekursion: Index des kleinsten Elementes ermitteln

Hallo,

habe nur eine kleine, aber mir kopfzerreißende Frage.
Und zwar beschäftige ich mich gerade mit Funktionen in C#, sowohl iterativ als auch rekursiv.

Nun soll ich eine rekursive Funktion schreiben, welche den Index des kleinsten Elements im Array ausgibt.

Das Gerüst sieht wiefolgt aus:

C#-Quelltext

1:
2:
3:
4:

static int MinIndexrekursiv(int[] zahlen, int anfang)
{

}

zahlen ist das Int-Array und der Integer anfang beschreibt eben den Anfangsindex der "Suche".
Brauche diese Funktion für mein SelectSort, was ich danach auch noch iterativ und rekursiv proggen muss :)
Iterativ ist das für mich alles kein Problem, aber bei der Rekursion muss man die Gehirnzelle schon etwas mehr anstrengen :P.
PS: Habe schon Vorkenntnisse zum Thema Rekursion (Fakultät, Fibonacci, Potenzieren etc.)

Please, help me!!!

Thx, im Voraus.

Moderiert von Christian S.: C#-Tags hinzugefügt

danielf - Mo 15.03.10 17:58

Hallo und :welcome:,

da es eine Übungsaufgabe ist, werde ich keinen konkreten Code liefern (sonst machts ja keinen Sinn für dich ;)

Also rekursion heißt ja immer, dass die Methode sich selber aufruft. Also muss du innerhalb der Methode wiederum die Methode aufrufen. Des weiteren brauchst du eine End-Bedingung, die diesen Kreislauf verlässt, sonst hast du eine Endlosschleife.

Deshalb sieht eine rekursive Funktion prinzipiell wie folgt aus:

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

<modifier> <rueckgabewert> <NameDerRekursivenMethode>(<Parameter>)
{
   <logik>

   if (<Bedingung>)
   {   // rekursion
       return <NameDerRekursivenMehotde>(<AngepassterParameter>);
   }
   else
   {
      return <value>;
   }
}

Ich hoffe das war nicht zu viel und nicht zu wenig :)

Gruß Daniel

danielf - Mo 15.03.10 18:17

hmmmmm, ....

Also du musst solang rekursiv gehen, bis du nur noch zwei Zahlen übrig hast. Das ist die Bedingung.

Dann musst du vergleichen ob eben die Letzte oder die Vorletzte kleiner ist (dazu kannst du Math.Min verwenden ... oder if/else ;) ) und die kleiner zurück geben.

Die von dem Aufruf merkst du dir und vergleichst sie dann mit der aktuellen Zahl (wobei du wieder die kleinste zurück gibst). Und zack fertig :)

Hilf das?

Christian S. - Do 18.03.10 10:24

Smaik hat folgendes geschrieben :

Sooo... 3 Tage sind verstrichen und es funzt immer noch nicht :( weiß echt nicht mehr weiter.

Schön. Was hast Du denn in den drei Tagen gemacht, um das Problem zu lösen? Wo kommst Du nicht weiter, welcher Teil der Erklärungen hier ist Dir unklar?

Ich vermisse irgendwie Eigeninitiative von Deiner Seite!

danielf - Do 18.03.10 10:58

Wie weit bist du den?
Ich habe es für dich Implementiert, da ich aber keinen (lern-)Sinn darin sehe, dir einfach den Code hinzuschmeißen habe ich den Algorithmus in meinem vorherigen Post versucht in Worte zu schreiben. Hast du mal versucht das so umzusetzen?

Bitte versuche das und poste den Code, dann helfe ich dir gerne bei den Details.

Smaik - Do 18.03.10 12:20

sooo... habs jetzt fast so gemacht wie du es beschrieben hast.
die kleinste zahl bekomm ich am ende auch, allerdings ist das ja nicht die lösung, zudem ich mir das ganze array "zerstöre" und somit am ende nicht mehr auf den index zurückkomme:

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

static int MinIndexrekursiv(int[] zahlen, int anf)
        {
            int zahlmin = zahlen[anf];
            if (zahlen.Length == anf + 1)
                return zahlmin;
            else if (zahlmin > zahlen[zahlen.Length-1])
            {                   
                zahlen[anf] = zahlen[zahlen.Length-1];
                Array.Resize(ref zahlen, zahlen.Length-1);
                return MinIndexrekursiv(zahlen, anf);
            }
            Array.Resize(ref zahlen, zahlen.Length - 1);
            return MinIndexrekursiv(zahlen, anf);
        }

Er vergleich also immer die kleinste Zahl mit der letzten des Arrays und merkt sie sich dann entweder in zahlen[anf] oder nicht und verkleinert danach das Array um 1.
Bis jetzt hab ich noch keinen anderen Weg gefunden... ja ich weiß, die Lösung ist übelst schlecht und führt nicht mal zum ziel:P

Die wirkliche Problematik ist bei mir, dass ich ja n Integer zahlmin erstelle und dieser bei jedem Aufruf der Funktion neu zugewiesen wird mit den veränderten Parametern.

Moderiert von Christian S.: Code- durch C#-Tags ersetzt

danielf - Do 18.03.10 12:32

Ähhhh, wüßte gar nicht das ich irgendwas von Array.Resize oder Werte ändern geschrieben habe?

Zitat:

Also du musst solang rekursiv gehen, bis du nur noch zwei Zahlen übrig hast. Das ist die Bedingung.

C#-Quelltext

1:
2:

if (anfang < zahlen.Length - 2)
   // rekursion

Zitat:

Dann musst du vergleichen ob eben die Letzte oder die Vorletzte kleiner ist (dazu kannst du Math.Min verwenden ... oder if/else ;) ) und die kleiner zurück geben.

C#-Quelltext

1:	return Math.Min(zahlen[anfang], zahlen[anfang + 1]);

Zitat:

Die von dem Aufruf merkst du dir und vergleichst sie dann mit der aktuellen Zahl (wobei du wieder die kleinste zurück gibst). Und zack fertig :)

C#-Quelltext

1:	return Math.Min(min, zahlen[anfang]);

Bisschen was drum herum fehlt noch... aber um meine Worte eindeutiger zu machen (Code kann niemals zweideutig interpretiert werden?! (These ;) )

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!