Kombinatorik in der Informatik |
| 06.12.2011, 18:51 | sharksen | Auf diesen Beitrag antworten » |
| Kombinatorik in der Informatik Für Algorithmik sollen wir die Anzahl der möglichen Reihenfolgen finden, wie man einen balancierten binären Suchbaum bestückt, und zwar für einen Suchbaum mit 15 Elementen. Der Baum wird am Ende wie folgt aussehen: http://dl.dropbox.com/u/20843750/Unbenannt.gif Es ist klar, dass die 8 als erstes in den Baum gefügt werden muss. Danach dann entweder die 4 oder die 12. Danach dann entweder 2, 6, 10 oder 14, je nachdem was man zuvor gewählt hat.. und so weiter. Vielleicht ist es für den Anfang einfacher, sich auf einen Baum mit 7 Elementen beschränken, der dann so aussieht: http://dl.dropbox.com/u/20843750/Unbenannt2.gif Ich versuche mein eigentliches Problem mal mathematisch abzuwandeln: Wiie viele Permutationen der folge 1, 2, 3, 4, 5, 6, 7 gibt es, wenn - die 4 immer vorne steht - die 2 immer vor der 1 und der 3 vorkommt - die 6 immer vor der 5 und der 7 vorkommt? Meine Ideen: Ich habe zumindest ein Programm beschrieben, dass alle Permutationen der Länge 7 (also 7! Stück) generiert und davon dann die rauspickt, die die obigen Eigenschaften erfüllen, mit dem Ergebnis, dass es 80 Stück gibt: http://dl.dropbox.com/u/20843750/permutationen.txt Die Zahlen 15 und 7 kommen daher, dass die Bäume vollständig sein müssen. Ich würde es gerne auch einfach so für 15 Elemente machen, aber.. 15! ist wohl etwas zuviel und es lässt sich nicht mehr generieren :/ |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
Wichtig: