Rekursiv Minimum in einer Queue

14.01.2016, 14:17

Chirs

Rekursiv Minimum in einer Queue

Meine Frage:
Hallo,

ich hätte nochmal eine Frage bzgl. Queue und zwar möchte ich gerne eine Funktion schreiben, die rekursiv das Minimum einer Queue bestimmt.

Ich verwende hierzu bereits Funktionen die wir im Studium definiert haben:

emptyqueue() -> gibt leere Queue zurück
rest() -> Entfernt erstes Element
head() -> gibt erstes Element zurück
append() -> fügt hinten ein Element an

Leider weiß ich nicht wie ich den Vergleich des ersten Elements mit dem Nächsten rekursiv realisieren soll.

Vielleicht kann mir hier jemand weiterhelfen.

Danke schon mal für eure Bemühungen

Grüße

Meine Ideen:

code:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:	unsigned int min(queue *q) { if (q == 0) return emptyqueue(); else if (head(q)== ) ??? return head(q); else return min(rest(q));

14.01.2016, 16:57

Auf diesen Beitrag antworten »

eulerscheZahl

Du musst immer ein int zurückgeben, das tust du bei emptyqueue() nicht.

code:
1: 2: 3: 4: 5: 6:	unsigned int findMin(queue* q) { if (head(q) == NULL) return -1; unsigned int current = head(q); unsigned int restMin = findMin(rest(q)); return min(current, restMin); }

Der Code wird ziemlich sicher nicht compilierbar sein, sollte dir aber trotzdem einen Absatz geben, wie du die Aufgabe lösen kannst: Berechne das Minimum des Rests und vergleiche mit dem aktuellen Wert.
Wenn es keinen Rest mehr gibt, wird der größte mögliche Wert zurückgegeben. (-1 als unsigned gibt einen Überlauf, weshalb -1 der größtmögliche Wert ist).

14.01.2016, 19:59

Auf diesen Beitrag antworten »

Chirs

Dankeschön für die schnelle Antwort und für die Hilfe. Daumen hoch

Leider möchte ich jedoch das gefundene Minimum ausgeben.
Also im return möchte ich gern head(q) stehen haben wenn es das Minimum ist smile

Trotzdem vielen Dank für den Denkanstoß smile

14.01.2016, 20:19

Auf diesen Beitrag antworten »

eulerscheZahl

Aber head(q) ist nur ein Wert von vielen. Woher nimmst du die Gewissheit, dass gerade dort das Minimum steht und nicht in den Werten danach? Den Rest werte ich per rekursivem Aufruf aus, um ihn dann mit head(q) zu vergleichen. Irgendwo musst du da das Minimum aus beidem berechnen.

14.01.2016, 21:15

Auf diesen Beitrag antworten »

Chirs

Ja du hast recht das andere funktioniert nur wenn ich head() mit einem zu suchenden Element vergleichen kann smile

Aber was ich noch nicht ganz verstehe ist wenn ich jetzt diese Funktion in findMax ändern möchte dann muss ich nur die Zeile return -1 ändern oder ?

Grüße

15.01.2016, 06:39

Auf diesen Beitrag antworten »

eulerscheZahl

Da, dann gibst du einfach das Minimum (also bei unsigned: 0) zurück.

Neue Frage »

Antworten »

Rekursiv Minimum in einer Queue

Verwandte Themen