Kombinationen II Wenn aus einem Gef„á mit n verschiedenfarbigen Kugeln ohne Zu- rcklegen und ohne Bercksichtigung der Reihenfolge (man nennt das "Ziehen mit einem Griff" oder "auf einen Griff") k Kugeln gezogen werden, ergibt sich folgende Anzahl von M”g- lichkeiten: n*(n-1)*(n-2)*(n-3)*...*(n-k+1) n! -------------------------------- = ----------- 1 AND X%<=170 THEN FNFakultaet## = X%*FNFakultaet##(X%-1) ELSEIF X%=0 OR X%=1 THEN FNFakultaet## = 1 ELSE FNFakultaet## = -1 END IF END DEF Die Verwandtschaft mit dem Programm zur Berechnung der Fakul- t„t ist klar zu erkennen und beabsichtigt. Hier wird die Effi- zienz des rekursiven Programmierens deutlich. Eine Unterrou- tine wird mehrmals benutzt - und auch noch mit verschiedenen Variablen! Natrlich geht das in QBASIC auch (KOMBI2_2.BAS) : DECLARE FUNCTION fakultaet# (x!) CLEAR , , 10000 CLS INPUT "Geben Sie bitte eine Zahl fr n ein: ", n! INPUT "Geben Sie bitte eine Zahl fr k ein: ", k! PRINT "Die Zahl der M”glichkeiten fr"; n!; "ber"; k!; ": "; PRINT fakultaet#(n!) / (fakultaet#(k!) * fakultaet#(n! - k!)) END FUNCTION fakultaet# (x!) IF x! = 0 THEN fakultaet# = 1 ELSE fakultaet# = ... ... x! * fakultaet#(x! - 1) REM die letzten zwei Zeilen sind eigentlich eine Zeile. REM Wegen des Formats dieses Magazins ist leider diese REM Schreibweise n”tig. Die Punkte mssen natrlich wegge- REM lassen werden, wenn das Programm bernommen wird. END FUNCTION Wir k”nnen die obige Formel auch umformen, wenn wir folgende Setzungen bercksichtigen: Diese Beziehung ergibt sich aus: (n) ³ ³ = 1 (0) (n) n*(n-1)*(n-2)*(n-3)*...*(n-k+1) ³ ³ = --------------------------------- (k) k*(k-1)*(k-2)*...*2*1 n*(n-1)*(n-2)*(n-3)*...*((n-1)-(k-1)+1) = ----------------------------------------- k*(k-1)*(k-2)*...*2*1 n (n-1) = - * ³ ³ k (k-1) In Worten: n ber k ist gleich dem Produkt aus dem Quotienten n/k und n-1 ber k-1. Das sieht ja ganz gut aus. Dieser Algorithmus erspart einen rekursiven Aufruf der Funktion und schont damit den Stapel- speicher. Hier liegt eine M”glichkeit der Programmoptimierung. Das Programm arbeitet schneller. Hurra! Ob das aber auch meábar ist, bleibt nachzuprfen. ŽTSCHIBŽŽŽTSCH! Die Formel sieht zwar einfacher aus, ben”tigt aber offenbar mehr Stapelspeicher als die erste Form. Scheinbar wird wohl der Stackbereich nach dem Abarbeiten eines rekursiven Aufrufs zurckgesetzt. Deshalb wird auch in dem Beispiel der Stackbe- reich vergr”áert. Man kann das austesten, indem man die h”chsten Zahlen bis zum Stapelberlauf feststellt und dann sieht, ob die erste Version nicht weniger Stapelspeicher fr dieselbe Zahlenkombination ben”tigt. Fazit: Faszinierende L”sungen sind nicht immer optimal! Das war kein Hack! Trotzdem: Hier ist das POWERBASIC-Programm: Jedenfalls kann es als Illustration zum Aufruf einer Funktion mit 2 Variablen dienen (KOMBI2_3.BAS). $STACK &H2700 CLS INPUT "Geben Sie bitte eine Zahl fr n ein: ", N% INPUT "Geben Sie bitte eine Zahl fr k ein: ", K% PRINT "Die Zahl der M”glichkeiten betr„gt fr";N%;"ber"; PRINT K%;":";Q##=N%/K% PRINT Q##*FNFakultaet##((N%-1),(K%-1)) END DEF FNFakultaet##(X%,Y%) IF Y% =>1 AND Y%<=200 THEN FNFakultaet## = X%/Y%*FNFakultaet##((X%-1),(Y%-1)) ELSEIF Y%=0 THEN FNFakultaet## = 1 ELSE FNFakultaet## = -1 END IF END DEF Und das QBASIC-Programm folgt sogleich (KOMBI2_4.BAS). DECLARE FUNCTION fakultaet# (x!, y!) CLEAR , , 10000 CLS INPUT "Geben Sie bitte eine Zahl fr n ein: ", N! INPUT "Geben Sie bitte eine Zahl fr k ein: ", K! PRINT "Die Zahl der M”glichkeiten fr"; N!; "ber"; K!; ": "; PRINT N! / K! * fakultaet#((N! - 1), (K! - 1)) END FUNCTION fakultaet# (x!, y!) IF y! = 0 THEN fakultaet# = 1 ELSE fakultaet# = ... ... x! / y! * fakultaet#((x! - 1), (y - 1)) REM Auch die letzten beiden Zeilen sind wieder nur eine REM Zeile. Das Format ... Na, ja, ihr wiát schon. END FUNCTION Jedenfalls k”nnen wir nun berechnen, wieviele Lottoscheine man ausfllen muá, um am Samstag mit Sicherheit "6 Richtige" zu haben. Leider ist das Ergebnis nicht ermutigend. Jetzt wird auch klar, warum beim alten Mittwochslotto (6 aus 36) die Gewinne niedriger als beim Lotto 6 aus 49 waren. Wurde es deshalb abgeschafft? Aber es gibt auch noch andere Anwendungsm”glichkeiten: z.B.: Das Machoproblem! Wir denken an folgende (allt„gliche) Situation: Thomas und Gero m”chten zwei ihrer Schulfreundinnen Tina, Lisa, Anne, Beate und Carla zum Eis einladen. Wieviele M”g- lichkeiten haben sie, ihre Wahl zu treffen? Das ist ja noch ganz einfach. 5 (M„dels) ber 2 (Jungs). Hmmmmm! Interessanter w„re es jedoch, sich eine Liste mit allen m”glichen Kombinationen ausgeben zu lassen. Einfacher gesagt, wir brauchen ein Programm, das die Liste aller "k-elementigen Teilmengen" (genauer: Teillisten) einer Menge (n„mlich der Ursprungsliste) ausgibt. Alles klar? Oder? (KOMBI2_5.BAS) 10 CLS 20 DIM KOMBI$(200) 30 PRINT 40 ZAHL%=1 : KOMBI$(ZAHL%)="" 50 INPUT " Wieviele Jungen";JK% 60 INPUT " Wieviele M„dchen";MN% 70 PRINT 80 IF MN%J(I-1) THEN 270 500 J(I)=J(I)+1 510 H$=NAMEN$(I) : NAMEN$(I)= NAMEN$(J(I)) : NAMEN$(J(I))=H$ 520 IF J(I)JK% THEN 410 700 ZAHL%=ZAHL%-1 : PRINT 710 PRINT " Anzahl der Kombinationen: "; ZAHL% : PRINT 720 FOR A=1 TO ZAHL% 730 PRINT USING "###";A; : PRINT ". Kombination: ";KOMBI$(A) 750 NEXT A 760 END Nach dem Start geben wir als Zahl der Jungen 2 ein, die Zahl der M„dchen ist 5 und die Namen sind: Tina Lisa Anne Beate und Carla Anmerkung zur Probleml”sung: Wenn wir den Namen Elemente zuordnen, erhalten wir als Ele- mentnummern: Name: Tina Lisa Anne Beate und Carla Element(nummer): 1 2 3 4 5 (5) Die ³ ³ = 10 Kombinationen der Elemente 1 2 3 4 5 sind: (2) Tausch: Stelle genutze ³nicht genutzte Tausch: Stelle A gegen B Elemente ³ Elemente A gegen B ³ 1 2³3 4 5 2 gegen 3 1 3³2 4 5 2 gegen 4 1 4³2 3 5 2 gegen 5 1 5³2 3 4 1 gegen 3 2 3³1 4 5 2 gegen 4 2 4³1 3 5 2 gegen 5 2 5³1 3 4 1 gegen 4 3 4³1 2 5 2 gegen 5 3 5³1 2 4 1 gegen 5 4 5³1 2 3 Durch diese Darstellung wird der Zweck der šbung deutlich: Das erste Element (1) wird mit allen ihm folgenden Elementen (2-5) verbunden. Dann wird das zweite Element (2) mit allen ihm folgenden Elementen (3-5) verbunden. Dann das dritte Ele- ment (3) mit dem ihm folgenden (4 und 5); schlieálich das vierte Element (4) mit dem ihm folgenden Element (5). Das funktioniert aber nur, wenn die Reihenfolge der nicht ge- nutzten, weil momentan nicht dargestellten Elemente verwaltet wird. Tausch A gegen B heiát also, daá das Element, das gerade an der Position A steht, gegen das Element getauscht wird, das sich gerade an der Position B befindet. Es drfen also nicht die Elementnummern (=NAMEN$(I)) getauscht werden! Es mssen die Positionen getauscht werden! Zeile 260 : Jedesmal, wenn die neue Tauschposition gew„hlt wird, wird I um 1 erh”ht und J(I) auf JK% (in un- serem Beispiel auf 2) gesetzt. Zeile 270 : Die Namen an den entsprechenden Positionen werden ausgetauscht (sog. Dreieckstausch) Zeile 280 : Die Kennzahl J(I) wird um 1 vermindert Zeile 300 : Die hergestellte Kombination wird als Variable (KOMBI$(ZAHL%)) gespeichert. Zeile 400 : Dieses Verfahren wird fortgesetzt, solange I J(I-) ist, noch einmal getauscht (Zeile 270), an- dernfalls das letzte Element abgearbeitet (500). Zeile 500 : J(I) wird um 1 erh”ht; die Namenelemente werden getauscht. Zeile 520 : Dieser Vorgang wird wiederholt, wenn J(I)