MezData-Logo Creative Commons License 321 Lösungen Button :JAVA: Die Fakultät Funktion

Was ist die Fakultät?

Man stelle sich folgendes Problem vor, wie viele Möglichkeiten gibt es 2 Hüte auf 2 Haken zu verteilen?
Wieviele Möglichkeiten gibt es bei 3 Hüten und 3 Haken usw. Man nennt diese Problemklasse auch Permutation.

Beispiel für zwei Hüte:
Möglichkeit Nr. Haken 1 Haken 2
1 Hut 1 Hut 2
2 Hut 2 Hut 1

Wenn bei drei Hüten einer auf dem ersten Haken hängt, bleiben für die restlichen beiden Hüte nur noch zwei Möglichkeiten. Jeder der drei will mal der erste sein, somit 3*2 Möglichkeiten.

Beispiel für drei Hüte:
Nr. Haken 1 Haken 2 Haken 3
1 Hut 1 Hut 2 Hut 3
2 Hut 1 Hut 3 Hut 2
3 Hut 2 Hut 1 Hut 3
4 Hut 2 Hut 3 Hut 1
5 Hut 3 Hut 1 Hut 2
6 Hut 3 Hut 2 Hut 1

In der Mathematik wird das '!' Zeichen für die Fakultätsfunktion benutzt:

1! = 1 2! = 2 3! = 6 Allgemein: x!= 1*2*...*x

D.h.. Sollen 4 Hüte auf 4 Haken verteilt werden, gibt es 4! =1*2*3*4 = 24 Möglichkeiten!

Aufgabe: Ein Java-Applet erstellen, das die Fakultäts-Funktion berechnet.

Hilfestellung: Noch in Arbeit...

Download des J-Builder Projekts: Fakultaet_einstieg.zip (7kB) Quelltext anschauen

Warum wird das Ergebnis für 17! negativ?

Grund dafür ist die interne Darstellung der Zahlen, beim hier verwendeten Typ int werden 32 Bit verwendet,
ist das vorderste Bit 1 so ist die Zahl negativ. 17! ist größer als 31 Bit, beim Überlaufen wird das vorderste Bit
gesetzt, die Zahl wird als negative Zahl interpretiert. Siehe Zahlendarstellung im Computer...

Tip: Verwendet man statt int den long Typ (64 Bit) können die berechneten Fakultäten größer werden, bis die Ergebnisse negativ werden ;-)

For- durch While- Schleife ersetzen

Aufgabe: Im Skript nachschauen und die For-Schleife durch eine While-Schleife ersetzen!

Diskussion: Welche Anweisung ist universeller? Wo setzt man was besser ein, Vor- und Nachteile

Funktionen und Unterprogramme

In der Mathematik kennt man beispielsweise folgende Funktion f(x) = 3x+4; Sprich: ef von ix ist gleich drei ix plus vier

Man kann eine Funktion als eine Variable für eine Berechnungsvorschrift auffassen, ruft man obige Funktion f mit dem Wert 3 auf,
so gibt sie gemäß ihrer Berechnungsvorschrift f(3) = 3*3+4 = 13 zurück.

Betrachte die Funktion fact(x) = 1*2*...*x, die Fakultätsfunktion, die Berechnung dieser Funktion wurde in obigen Applet z.B. so programmiert:

  int x,i,erg; // x Eingabe i Laufvariable erg Ergebnis
  erg = 1;       // erg initialisieren
  for (i=1; i<=x; i++){ // i von 1 bis x zählen
    erg = erg*i;  // bisheriges Ergebnis mit i multiplizieren
  } // - i von 1 bis x zählen

Statt immer diese Folge von Anweisungen zu schreiben um die Fakultät zu berechnen wäre es doch bequemer, dieses Teilprogramm
in eine Funktion zu verpacken um später nur noch zu schreiben: ergebnis = fact(x);

Verpacken des Fakultätsberechnungsunterprogramms in eine Funktion

Die Fakultäts-Funktion braucht einen Eingang mit Datentyp einen Ausgang mit Datentyp und einen Namen, da Funktionen mehrere Eingänge haben können, benötigt man noch Bezeichner für die Eingänge, damit es später keine Verwechslungen gibt. Diese Eingänge nennt man Parameter der Funktion:

  Ausgangstyp Funktionsname (Eingangstyp Bezeichner)
     int          fact      (    int         x     ) 

Wunderbar: Ein Funktionskopf mit Schnittstelle nach Außen. Wenn man nur den Kopf hinschreibt heißt das auch Deklaration der Funktion, der Compiler weis nun wie die Funktion aussieht, allerdings muß sie auch irgendwo definiert werden, sonst checkt der Compiler ja nicht was er berechnen lassen soll wenn die Funktion aufgerufen wird.
Die Funktion benötigt noch einen Rumpf mit dem sie rechnet, inklusive des Ausgebens eines Wertes:

  int fact(int x){

    return Ausgabe;
  }

Immer wenn in einer Funktion eine return-Anweisung auftaucht wird der Wert der Anweisung als Wert der Funktion zurückgegeben und die Funktion sofort verlassen, auch wenn das in der Mitte oder sogar am Anfang ist, sobald es irgend etwas zum Ausgeben gibt ist für die Funktion der Fall erledigt!

So sieht die ganze fact-Funktion aus:

  int fact(int x){ // Fakultätsfunktion mit Eingabe int x und Ausgabe vom Typ int
  int i,erg;       // i Laufvariable erg Ergebnis
    erg = 1;       // erg initialisieren
    for (i=1; i<=x; i++){ // i von 1 bis x zählen
      erg = erg*i; // bisheriges Ergebnis mit i multiplizieren
    } // - i von 1 bis x zählen
    return erg;    // erg ausgeben
  }

So wird die fact-Funktion verwendet:

  void button1_actionPerformed(ActionEvent e) {
  int x,erg; // x Eingabe erg Ergebnis
    x = Integer.valueOf(textField1.getText()).intValue();  // Auslesen aus Feld
    erg = fact(x);       // fact(x) aufrufen und Ausgabe in erg merken
    label4.setText(Integer.toString(erg)); // Ergebnis ausgeben
  }

Funktionen müssen immer vor ihrer Verwendung deklariert werden, ist genau wie bei den Variablen...

Sichtbarkeit der inneren Variablen einer Funktion nach außen

Die inneren Variablen sind nach außen nicht sichtbar, d.h. auf i und erg der fact-Funktion kann außerhalb der Funktion nicht zugegriffen werden,
man nennt diese Variablen deshalb auch lokale Variablen. Beim Aufruf einer Funktion wird für diese Variablen Platz im Speicher reserviert,
dieser Platz ist nach Verlassen der Funktion wieder freigegeben.

Sichtbarkeit der äußeren Variablen innerhalb von Funktionen

Die Variablen die außerhalb der Funktion definiert wurden sind in der Regel innerhalb sichtbar und können verwendet werden,
man nennt diese Variablen auch globale Variablen. Ausnahme: Wenn ein lokaler Bezeichner einen Globalen verdeckt,
kann auf den Globalen nicht ohne weiteres zugegriffen werden: Beispiel: Sei eine globale Variable x, diese wird innerhalb von fact nicht gesehen,
da sie von der Parmetervariabeln x verdeckt ist.

Übung: Implementiere eine Funktion summe(int x,int y), die als Ergebnis x+y zurückgibt.

Fakultät Rekursiv

Schauen wir uns noch mal die Fakultätsfunktion genau an:

1! = 1 2! = 2 3! = 6 4! = 4 * 3! Allgemein: 1! = 1, sonst x!= x * (x-1)!

Jedesmal wenn ein neuer Hut dazu kommt, kann man die Möglichkeiten auf die schon bekannten reduzieren, das ist eine Rekursion!

Sowas kann man auch programmieren:

  int factr(int x){  // Fakultät rekursiv
    if (x==1) return 1;  //  1! = 1
    else return x*factr(x-1); // sonst x! = x * (x-1)!
  }

Ist das nicht wahre Zauberei?

Informatiker lieben die Rekursion, sie kann das Leben so einfach machen, die Arbeit macht dann der Computer ;-)

Aufgabe: Was passiert genau wenn factr(4) aufgerufen wird, auf Papier nachvollziehen...

Tip: Warum die factr-Funktion nicht etwas "gesprächiger" machen? Hier ein Vorschlag:

  int factr(int x){  // Fakultät rekursiv
    // Ausgabe in z.B. Listbox: "Aufruf factr(2)"
    if (x==1) return 1;  //  1! = 1
    else{
      // Ausgabe: "2*factr(1)
      return x*factr(x-1); // sonst x! = x * (x-1)!
    }
  }

Wenn ich eine Funktion nicht verstehe, oder sie Probleme macht, bringe ich sie geschickt zum plappern!
Alternativ kann auch die Debugger-Funktion des J-Builders genutzt werden.