minimum einer Zahlenfolge?
Hi, also ich müsste ein rekursiven Pseudocode (Funktion ruft sich selber auf) schreiben für eine Funktion die das Minimum einer Zahlenfolge a1,....an (a e N) berrechnet. Jedoch komme ich nicht so ganz weiter wie ich es realisieren kann, dass ich jedes Element vergleiche: ich vergleiche das erste mit dem zweiten, davon das kleinere mit dem dritten usw. Wie erreiche ich das in einem Pseudocode ? Dazu hatte ich mir überlegt, dass ich erreichen muss, dass bei jedem erneuten Aufruf die Funktion um 1 Element gekürzt werden muss, das heißt sobald die Funktion in der Funktion aufgerufen wird, wird a1,....an-a an diese übergeben , oder?
Hier ein Beispiel für ein solchen Code (um n! zu berrechnen):
1 Antwort
Ja, du kannst linear rekursiv arbeiten und das erste Element der Liste mit dem rekursiven Aufruf der restlichen Liste vergleichen.
Du kannst aber auch, statt immer linear zu kürzen, die Liste halbieren und rekursiv das Minimum dieser Sublisten ermitteln. Sobald eine Liste nur noch ein oder zwei Elemente besitzt, gibst du dann eben das Minimum davon zurück.
Dieses Minimum der Sublisten vergleichst du dann und gibst das kleinere zurück.
Wie notiere ich , wenn ich eine Liste halbieren will (bzw wie erreiche ich das, mit einer for schleife?)
Du machst das nicht mit einer for-Schleife. Du kannst das - im Pseudocode - direkt angeben:
list = (a_1, ... a_n)
sublist_a = (a_1, ..., a_(n/2))
sublist_b = (a_(n/2 + 1), ..., a_n)
und wenn ich dann aus zb (1,3,4,3,5,7) nun zwei Teilstränge (1,3,4) und (3,5,7) habe vergleich ich nun diese einzelnen Elemente untereinander und habe am ende 1 <3 somit minimum 1.
Du hast einen Vergleich übersprungen, du musst ja erstmal das Minimum von (1, 3, 4) und (3, 5, 7) bestimmen
Was ist jedoch wenn ich eine Liste mit ungerade Anzahl an Elementen habe? Wie teile ich diese dann?
auch da teilst du erstmal rekursiv weiter auf. Wenn du z.B. eine Liste mit drei Elementen hast, hat eine der Sublisten dann eben 2 Elemente und die andere ein Element
Ahhh, ok also definiere ich am Anfang direkt :
Eingabe: a_1.....a_n (e N)
sublist_a <- (a_1....a_(n/2))
sublist_b <- (a_(n/2 +1 )......a_n)
Nun müsste ich ja die rekursive Überprüfung für die beiden Stränge machen:
mach ich dies dann am besten so, dass ich eine if abfrage mach mit a1 <an wenn diese zutrifft dass die Funktion mit Sublist_a (a_1 ....a_(n/2 -1)) aufgerufen wird?
mach ich dies dann am besten so, dass ich eine icabfrage mach mit a1 <an wenn diese zutrifft dass die Funktion mit Sublist_a (a_1 ....a_(n/2 -1)) aufgerufen wird?
Nein. Du überprüfst am besten, ob die Subliste genau ein Element enthält, und gibst dann dieses zurück - denn das ist offensichtlich das Minimum.
In jedem anderen Fall teilst du die Sublisten und ermittelst dann rekursiv das Minimum
ahhh ok, aber ich verstehe nicht ganz wie ich das minimum ermittle wenn es mehr als ein Element enthält?
ahhh ok, aber ich verstehe nicht ganz wie ich das minimum ermittle wenn es mehr als ein Element enthält?
Nehmen wir mal an, wir haben die Liste
(5, -4, 2)
Da die Liste mehr als ein Element enthält, teilen wir sie auf:
(5, -4, 2) -> (5, -4) und (2)
Diese beiden Sublisten bearbeiten wir jetzt rekursiv. Fangen wir mit der ersten an:
(5, -4)
Die Liste enthält mehr als ein Element. Also teilen wir sie auf:
(5, -4) -> (5), (-4)
Also, wieder rekursiv arbeiten:
(5)
enthält offensichtlich nur ein einziges Element, die 5. Das ist also das Minimum dieser Teilliste
(-4)
enthält offensichtlich nur ein einziges Element, die -4. Das ist also das Minimum der Teilliste
Dann geben wir das eben zurück und beim Aufrufer vergleichen wir das Minimum dieser beiden Teillisten:
min(5, -4) = -4
Das Minimum von der Teilliste (5, -4) ist also -4
Jetzt haben wir die zweite Teilliste:
(2)
enthält offensichtlich nur ein einziges Element, ist also das Minimum. Das geben wir zurück.
Jetzt vergleichen wir die beiden Minima der Teillisten (5, -4) und (2) miteinander und geben das kleinere zurück:
min(-4, 2) = -4
Also müsste ich es dann grob so schreiben
wenn n = 1
-> Ausgabe : a1
sonst
->Minimum(Sublist_a)
jetzt ist nur noch die Frage offen wie ich es schaffe dass ich, da ich ja zwei Listen habe, die Ergebnisse beider dann zu vergleichen. Ich bekomme ja hier nur das Ergebnis von Liste Sublist_a
jetzt ist nur noch die Frage offen wie ich es schaffe dass ich, da ich ja zwei Listen habe, die Ergebnisse beider dann zu vergleichen. Ich bekomme ja hier nur das Ergebnis von Liste Sublist_a
Du machst eben nicht nur einen Aufruf, sondern zwei:
So vom Prinzip:
sonst:
min_a = Minimum(sublist_a)
min_b = Minimum(sublist_b)
return min(min_a, min_b)
achsooo, also am Ende dann so:
wenn n = 1
-> Ausgabe : a1
sonst
->min_a <- Minimum(Sublist_a)
min_b <- minimum (sublist_b)
Ausgabe Minimum(min_a, min_b)
Ausgabe Minimum(min_a, min_b)
nein, das sollte dann ein direkter Vergleich sein, kein weiterer rekursiver Aufruf
Also eher eine if abfrage mit min_a < min_b tue ausgäbe min_a sonst ausgäbe min_b?
Danke erstmal für die Antwort. Wie notiere ich , wenn ich eine Liste halbieren will (bzw wie erreiche ich das, mit einer for schleife?)und wenn ich dann aus zb (1,3,4,3,5,7) nun zwei Teilstränge (1,3,4) und (3,5,7) habe vergleich ich nun diese einzelnen Elemente untereinander und habe am ende 1 <3 somit minimum 1. Was ist jedoch wenn ich eine Liste mit ungerade Anzahl an Elementen habe? Wie teile ich diese dann?