13.4 Fakultät (n!)

13.4 Fakultät: n!

In der Mathematik wird n! häufig definiert als das Produkt

n ^. (n-1) ^. (n-2) ^. ... ^.2 ^. 1

Ein schon etwas anspruchvolleres Programm, das eine while-Schleife benutzt, ist das nächste Beispiel. Es zeigt, wie man die Fakultät einer Zahlberechnen.

import info1.*;

public class FakultaetTest{

   public static void main(String[] args){

      System.out.print("n: ");

      int n = Console.in.readInt();

      System.out.println("n! = "+fak(n));

   }

   static int fak(int n){

      int fakultaet = 1;

      int faktor = 1;

      while (faktor <= n){

        fakultaet = fakultaet*faktor;

        //System.out.println(fakultaet);

        faktor++;

      }

      return fakultaet;

   }

}

Der Schreibtischtest verdeutlicht, was bei den einzelnen Programmschritten geschieht. Ein Schreibtischtest ist eine Tabelle, in die alle Variablen eingetragen und "Entwicklung" ihrer Werte verfolgt werden. Dabei entspricht eine Zeile der Tabelle, jeweils einem Schleifendurchgang

Initialisierungsdaten: faktor=1, fakultaet =1, n = 5 (z.B).

faktor in Bedingung	Bedingung	fakultaet vor der Zuweisung	fakultaet nach der Zuweisung	faktor
1	true	1	1	2
2	true	1	2	3
3	true	2	6	4
4	true	6	24	5
5	true	24	120	6
6	false

Programmausgabe bei n=5

n = 18 Wir wählen n = 18 und lassen uns die Zwischenergebnisse im Schleifenkörper ausgeben:

Wir sehen, dass wegen des Minuszeichens in den letzten beiden Schleifendurchgängen UNsinn ausgegeben wird. Eine genauere Prüfung zeigt, dass schon vorher etwas 'faul' ist, dort nämlich, wo die Werte der Errechnenten Zwischenwerte der Fakultät sinken, satt steigen. Der Grund für die offensichtlich falsche Berechnung des Fakultät liegt nicht am Algorithmus, sondern an der Darstellung von int-Zahlen in Java. Tatsächlich ist der maximale Wert für int Zahlen: 2 147 483 647 (siehe dazu auch 6.1) Wählen wir für die Variable fakultaet an Stelle des Typs int, den Typ long, können wir bis 20! die Fakultäten berechnen. Aber schon ab 21! reicht auch der Grunddatentyp long nicht mehr aus.

Die etwas modifizierte Methode hat folgende Gestalt.:

Downlaod:

FakultaetTest2. java

   static long fak(int n){

      long fakultaet = 1;

      int faktor = 1;

      while (faktor <= n){

        fakultaet = fakultaet*faktor;

        System.out.println(fakultaet);

        faktor++;

      }

      return fakultaet;

   }

Die Definition n! = n ^. (n-1) ^. (n-2) ^. ... ^.2 ^. 1 hat für die Puristen unter den Mathematikern den Nachteil, dass die drei Punkte für usw. stehen, also voraussetzen, dass der Leser wohl weiß, was gemeint sei. Dies ist aber kein mathematisch korrektes Vorgehen. Tatsächlich heißt die exakte Definition:

0! = 1 und n! = n. (n-1)!

Wie wir sehen handelt es sich um eine rekursive Definition. Was liegt also näher, als diese Definition direkt als rekursive Methode zu implementieren?

Die rekursive Methode fakultaet(..)

   private static long fakultaet(int n){

      if (n==0) return 1;

      else return n*fakultaet(n-1);

   }

Download:
Mathematik.java Wie wir sehen, ist der Quellkode nicht nur kürzer, sondern auch einfacher zu lesen. Ein Effizienzvergleich der nichtrekursiven mit der rekursiven Methode zeigt keinen Unterschied. Wegen der leichteren Lesbarkeit übernehmen wir die rekursive Methode in die Klasse Mathematik.

zu 13.5 Übungen

zur Startseite www.pohlig.de (C) MPohlig 2004