Kombinationen

Im t„glichen Leben hat jeder Mensch Entscheidungen zu tref-
fen. Fr welche der gebotenen M”glichkeiten man sich auch 
entscheidet - es stehen immer neue M”glichkeiten zur Wahl. 
Um einen šberblick zu bekommen, kann man zun„chst die Gesamt-
zahl der Entscheidungsm”glichkeiten berechnen. Wenn die Ent-
scheidungen nacheinander zu treffen sind und jede Entscheidung 
eine bestimmte Anzahl von Alternativen zul„át, kann man die 
Gesamtzahl der Entscheidungen berechnen, indem man die ein-
zelnen Anzahlen miteinander multipliziert. Die Gesamtzahl 
der Entscheidungsm”glichkeiten (N) erh„lt man, indem die ein-
zelnen Anzahlen (n1 bis nk) miteinander multipliziert werden 
(s.o.).

n=n1*n2*n3*...*nk        

Diese Regel wird Produktregel genannt.

Beispiel: 

Steffen m”chte Musik h”ren. Er hat die Wahl zwischen Video-
Clips, CD, Cassette und Schallplatte. Er wrde - weil das ge-
rade seiner Stimmung entspricht - zwischen Pop, Country & 
Western und Hard-Rock w„hlen. Dann stehen jeweils 6 verschie-
dene Gruppen zur Wahl. Von jeder Gruppe hat er zwei unter-
schiedliche Lieblingsstcke zur Auswahl. Er hat bei seinen 
Entscheidungen zun„chst 4 verschiedene M”glichkeiten. Diese 
bieten jeweils 3 M”glichkeiten, die ihrerseits wieder 6 M”g-
lichkeiten er”ffnen. Jede dieser M”glichkeiten er”ffnet wieder
2 M”glichkeiten. Die Liste dieser M”glichkeiten ist dann: 
		
                4 3 6 2  

Um das entsprechende Produkt auszurechnen, kann man das fol-
gende BASIC - Programm bemhen (KOMBI1_1.BAS) :

CLS
PRINT
INPUT "  Wieviele Entscheidungen? ", E%          
			     REM   ^das Komma unterdrckt das 
			     REM Fragezeichen bei der Ausgabe
			     REM des INPUT-Befehl
PRINT
N$=""
FOR I=1 TO E%
PRINT "  Geben Sie bitte die Zahl der M”glichkeiten fr die ";
PRINT STR$(I,1);". Entscheidung ein: ";
INPUT, N%
N1$=LTRIM$(STR$(N%)) :REM der Befehl LTRIM$ unterdrckt das
		      REM fhrende Leerzeichen bei der Umwand-
		      REM lung des Wertes in einen String
N$=N$+N1$             REM DAS Ergebnis ist die Liste mit dem
		      REM String "4362" 
NEXT I
GOSUB PROD
PRINT
PRINT "  Die Anzahl der M”glichkeiten ist: ";
PRINT (STR$(PRODZ##,18)):REM Ausgabe des Produktwertes als
			 REM Flieákommazahl mit erweiterter 
			 REM Genauigkeit 
			 REM Ausgabe mit 18 Stellen 
END

PROD:
PRODZ##=1            :REM Setzen der Variablen als Flieákomma-
		      REM zahl mit erweiterter Genauigkeit
FOR I=1 TO E%
A%=VAL(MID$(N$,I,1)) :REM Umwandlung eines Zeichens des Strings
		      REM in einen NUMERISCHEN Wert bei jedem
		      REM Schleifendurchlauf
PRODZ##=(PRODZ##)*A% :REM Berechnen des Produkts
NEXT I
RETURN  

Funktionsweise des Programms.

Zun„chst wird die Anzahl der Entscheidungen festgestellt. Dann
wird die Zahl der M”glichkeiten bei den einzelnen Entschei-
dungen festgehalten. Die Eingaben werden zu einem String zu-
sammengefaát, der in der Unterprozedur weiterverarbeitet wird.
Man k”nnte natrlich auch die Liste direkt einprogrammieren und
dann an die Unterprozedur weitergeben. Aber das w„re ja wohl 
doch zu einfach. Und ich h„tte auch nicht mit Kenntnissen zur 
Manipulation von Variablen protzen k”nnen. 
Einen gravierenden Nachteil hat das Programm allerdings.
Fehleingaben wie 0 oder 1 werden nicht abgefangen. Wo ist denn 
die Alternative, wenn es keine oder nur eine Entscheidungsm”g-
lichkeit gibt? Auáerdem fhrt der vorgefhrte Algorithmus nur 
bei Eingabe von einstelligen Zahlen fr N% zu einem richtigen 
Ergebnis.
Das folgende Programm bercksichtigt diese M„ngel. Es wird 
keine Liste erstellt, die in einem Unterprogramm wieder aufge-
splittet werden muá; Fehleingabe werden in einer Subroutine 
bearbeitet (KOMBI1_2.BAS)
	 
CLS
PRODZ##=1
PRINT
INPUT "  Wieviele Entscheidungen? ", E%
PRINT
N$=""
FOR I=1 TO E%
PRINT "  Geben Sie bitte die Zahl der M”glichkeiten fr die ";
PRINT STR$(I,1);". Entscheidung ein: ";
INPUT, N%
IF N%<2 THEN GOSUB FEHLER
PRODZ##=(PRODZ##)*N%
NEXT I
PRINT
PRINT "  Die Anzahl der M”glichkeiten ist: ";
PRINT (STR$(PRODZ##,18))
END

FEHLER:
PRINT "         FEHLEINGABE!"
N%=1
I=I-1
RETURN

Mit dem Errechnen der Gesamtzahl der M”glichkeiten ist aber 
noch nichts ber die Zusammenh„nge von Entscheidungen gesagt. 
Viele M”glichkeiten werden infolge vorheriger Entscheidungen 
wohl gar nicht mehr wahrgenommen werden k”nnen. Andererseits 
sind gleichartige Entscheidungen nicht ausgeschlossen.

Anders sieht es aus, wenn wir dies ausschlieáen. Wir denken 
uns einen Topf mit fnf verschiedenfarbigen Perlen. Wenn wir 
diese Perlen zu einer Kette aufreihen, k”nnen wir jede Perle 
nur einmal benutzen. Aber wir schaffen verschiedene Muster -
indem wir die Reihenfolge vertauschen! Bei fnf verschiedenen 
Perlen k”nnen wir 120 verschiedene Muster (Perlenanordnungen) 
schaffen. Wir gehen von einem Grundmuster (M0) aus und ver„n-
dern die Stelle einer Perle im Muster so oft, bis kein neues 
Muster mehr entsteht. Danach stellen wir das Grundmuster wie-
der her und ver„ndern ebenso die Stellung zweier Perlen; da-
nach wird die Stelle dreier Perlen, von vier Perlen und 
schlieálich von fnf Perlen ver„ndert (wobei wir notgedrungen 
auch das Grundmuster einmal wiederherstellen). Nach der Pro-
duktformel (s.o) ist die Gesamtzahl der M”glichkeiten 

	n=1*2*3*4*5=120. 
	
Insgesamt gibt es also 120 verschiedene Muster, die aus 5 
verschiedenen Perlen hergestellt werden k”nnen. Fr diesen 
mathematischen Zusammenhang gibt es eine Formel:

n!=1*2*3*4*...(n-1)*n

In Worten: Es gibt n! (= n Fakult„t) M”glichkeiten, n ver-
schiedene Elemente so anzuordnen, daá die Reihenfolge sich 
nicht wiederholt. Voraussetzung ist natrlich, daá kein Ele-
ment mehr als einmal benutzt wird!
Das dieser Formel entsprechende BASIC-Pogramm zur Berechnung 
der M”glichkeiten k”nnte so aussehen (KOMBI1_3.BAS) :

	 CLS
	 INPUT "Geben Sie bitte eine Zahl ein: ", N%
	 GOSUB FAK
	 PRINT "Die Fakult„t der Zahl";N%;" lautet: ";
	 PRINT (STR$(FAKZ##,18))
	 END

	 FAK:
	 FAKZ##=1
	 FOR I=1 TO N%
	 FAKZ##=(FAKZ##)*I
	 NEXT I
	 RETURN

Dieses Programm berechnet n! iterativ (d.h. schrittweise, 
durch wiederholtes Multiplizieren), da durch Erh”hen der Vari-
ablen I der n„chste Faktor bereitgestellt wird.
Die Verwandschaft mit dem Unterprogramm PROD ist nicht zu ver-
leugnen.

Die Variante fr GW-Basic k”nnte so aussehen (KOMBI1_4.BAS) :

2 FAKULTAET!=1
3 CLS
4 INPUT "Geben Sie bitte eine Zahl ein: ", N%
5 Z%=N%
6 GOTO 10
7 PRINT "Die Fakult„t der Zahl"; Z%; " lautet: "; FAKULTAET!
8 END
10 REM  FAKULTAET! (N!)
11 IF (N%=0) OR (N%=1) THEN FAKULTAET! = FAKULTAET!*1 : GOTO 7
12 FAKULTAET! = FAKULTAET!*N% : N%=N%-1 : GOTO 11

Diese Programm enth„lt die Behandlung der Werte 0! und 1!. 
Auáerdem liegt hier ein Pseudo-Selbstaufruf vor (GOTO 11).
Das Programm liefert bis 32! recht verl„áliche Ergebnisse.
Dann jedoch zeigen sich infolge Stackberlaufs Fehler.

Wenn wir bedenken, daá 1!=1 ist, erhalten wir durch Umformung:

n!=n*(n-1)!        

Entsprechend dieser Definition k”nnen wir auch (unter Aus-
nutzung der Funktion DEFINE FUNCTION ein BASIC-Programm rekur-
siv schreiben (KOMBI1_5.BAS).

$STACK &H1800
CLS
INPUT "Geben Sie bitte eine Zahl ein: ", N%
PRINT "Die Fakult„t der Zahl";N%;" lautet: "; FNFakultaet## (N%)
DEF FNFakultaet##(N%)
  IF N% >1 AND N%<=150 THEN
    FNFakultaet## = N%*FNFakultaet##(N%-1)
  ELSEIF N%=0 OR N%=1 THEN
    FNFakultaet## = 1
  ELSE
    FNFakultaet##=-1
  END IF
END DEF

Funktionsweise des Programms.

Da es sich um eine rekursive Prozedur handelt, muá der Stack 
in der ersten Zeile vergrӇert werden, da sonst infolge der 
Vielzahl von Stackoperationen schnell ein Stack-šberlauf-
Fehler eintreten wrde. Die angegebene Stackgr”áe máte bis 
zur Berechnung der Fakult„t von 150 gengen.
Dann folgt der Funktionsblock zur Definition der rekursiven 
Funktion. Eingebaut ist die Abfrage auf "normale" Werte (>1 
und <=150) und die Behandlung der "Ausnahmen" 0! und 1!.  
Der rekursive Selbstaufruf erfolgt in der siebten Zeile durch
"FNFakultaet##(N%-1)"
Anzumerken ist noch, daá trotz 18-stelliger Ausgabe die Be-
rechnung ab 20! an Genauigkeit verliert.

An dieser Stelle ist noch etwas zur Rekursion zu sagen.
Die Programmiertechnik der Rekursion ist eine effiziente Pro-
grammiertechnik, da sie Speicherplatz spart, indem (Unter-)
Programme mehrfach benutzt werden. Das erfordert zwangsl„ufig,
daá eine Abbruchbedingung zu definieren ist (IF N% >1 AND 
N%<=150 THEN ...), die auf die Ver„nderung von Parametern 
angewiesen ist. Es ist wohl selbstverst„ndlich, daá diese 
Parameter im Aufruf der Routine oder der Funktion bergeben 
werden mssen (FNFakultaet##(N%-1)).

Fr die Besitzer von QBasic k”nnte die Routine so aussehen.
(KOMBI1_6.BAS)

 DECLARE FUNCTION fakultaet (n!) :REM Definition der Funktion
 CLEAR , , 5000                  :REM VergӇern des Stapels 
 CLS
 INPUT "Geben Sie bitte eine Zahl ein: ", n!
 PRINT "Die Fakult„t der Zahl"; n!; " lautet: "; fakultaet(n!)

 FUNCTION fakultaet (n!)
  IF n! = 0 THEN fakultaet = 1 
     ELSE fakultaet = n! * fakultaet(n! - 1) :REM rekursiver 
					      REM Aufruf der
					      REM Funktion
 END FUNCTION

Das war's denn fr heute. Demn„chst geht's weiter mit weiteren 
Kombinationen mit

				Herbie