4. Fakultäten in Java berechnen

Fakultäten in Java berechnen

  • W

    Hallo,

    ich habe gerade versucht verschiedene Fakultäten zu berechnen und bin auf etwas (für mich) merkwürdiges gestoßen:
    Wenn ich z.B. eine Fakultät von 17 berechnen möchte, bietet sich ein einfacher int nicht mehr als Datentyp an, da das Ergebnis größer als 2.147.483.647 wäre (also außerhalb des Wertebereichs).
    Für diesen Zweck hab ich mal verschiedene Werte jeweils mit long und int berechnet und bemerkt, dass die Ergebnisse schon bei kleineren Ergebnissen voneinander abweichen (also obwohl das Ergebnis noch im Wertebereich von int und long liegt). Im unteren Beispiel ist das zum Beispiel bei !13 der Fall.
    Kann mir das bitte jemand mal näher erläutern?
    Danke schonmal

    Hier der entsprechende Code:

    public class Fakultaet
{
    public static void main(String[] args)
    {
        long[] fakultaet = new long[33]; // bzw. mit int deklariert
        for (int i=1; i<fakultaet.length; i++)
        {
            fakultaet[i] = 1; // Wert mit 1 initialsieren
            for (int zahl=1; zahl<=i; zahl++)
            {
                fakultaet[i] = fakultaet[i] * zahl;
            }
        }

        for (int j=1; j<fakultaet.length; j++)
        {
            System.out.print("Die Fakultaet von " + j + " ist ");
            System.out.println(fakultaet[j]);
        }
    }
}

    Ausgabe int schrieb:

    Die Fakultaet von 1 ist 1
Die Fakultaet von 2 ist 2
Die Fakultaet von 3 ist 6
Die Fakultaet von 4 ist 24
Die Fakultaet von 5 ist 120
Die Fakultaet von 6 ist 720
Die Fakultaet von 7 ist 5040
Die Fakultaet von 8 ist 40320
Die Fakultaet von 9 ist 362880
Die Fakultaet von 10 ist 3628800
Die Fakultaet von 11 ist 39916800
Die Fakultaet von 12 ist 479001600
Die Fakultaet von 13 ist 1932053504
Die Fakultaet von 14 ist 1278945280
Die Fakultaet von 15 ist 2004310016
Die Fakultaet von 16 ist 2004189184
Die Fakultaet von 17 ist -288522240
Die Fakultaet von 18 ist -898433024
Die Fakultaet von 19 ist 109641728
Die Fakultaet von 20 ist -2102132736
Die Fakultaet von 21 ist -1195114496
Die Fakultaet von 22 ist -522715136
Die Fakultaet von 23 ist 862453760
Die Fakultaet von 24 ist -775946240
Die Fakultaet von 25 ist 2076180480
Die Fakultaet von 26 ist -1853882368
Die Fakultaet von 27 ist 1484783616
Die Fakultaet von 28 ist -1375731712
Die Fakultaet von 29 ist -1241513984
Die Fakultaet von 30 ist 1409286144
Die Fakultaet von 31 ist 738197504
Die Fakultaet von 32 ist -2147483648

    Ausgabe long schrieb:

    Die Fakultaet von 1 ist 1
Die Fakultaet von 2 ist 2
Die Fakultaet von 3 ist 6
Die Fakultaet von 4 ist 24
Die Fakultaet von 5 ist 120
Die Fakultaet von 6 ist 720
Die Fakultaet von 7 ist 5040
Die Fakultaet von 8 ist 40320
Die Fakultaet von 9 ist 362880
Die Fakultaet von 10 ist 3628800
Die Fakultaet von 11 ist 39916800
Die Fakultaet von 12 ist 479001600
Die Fakultaet von 13 ist 6227020800
Die Fakultaet von 14 ist 87178291200
Die Fakultaet von 15 ist 1307674368000
Die Fakultaet von 16 ist 20922789888000
Die Fakultaet von 17 ist 355687428096000
Die Fakultaet von 18 ist 6402373705728000
Die Fakultaet von 19 ist 121645100408832000
Die Fakultaet von 20 ist 2432902008176640000
Die Fakultaet von 21 ist -4249290049419214848
Die Fakultaet von 22 ist -1250660718674968576
Die Fakultaet von 23 ist 8128291617894825984
Die Fakultaet von 24 ist -7835185981329244160
Die Fakultaet von 25 ist 7034535277573963776
Die Fakultaet von 26 ist -1569523520172457984
Die Fakultaet von 27 ist -5483646897237262336
Die Fakultaet von 28 ist -5968160532966932480
Die Fakultaet von 29 ist -7055958792655077376
Die Fakultaet von 30 ist -8764578968847253504
Die Fakultaet von 31 ist 4999213071378415616
Die Fakultaet von 32 ist -6045878379276664832
    0
  • A

    Bei 13 geht dir einfach schon der Integer-Zahlenraum aus. 6227020800 modulo 2147483647 ist nämlich genau 1932053504. 🤡

    0
  • J

    Richtig!

    Ausserdem würde ich die Berechnung so ausführen:

    long[] fakultaet = new long[33];
fakultaet[0] = 1;
for (int i=1; i<fakultaet.length; i++) 
    fakultaet[i] = i*fakultaet[i-1];
    0
  • W

    Javaner schrieb:

    Richtig!

    Ausserdem würde ich die Berechnung so ausführen:

    long[] fakultaet = new long[33];
fakultaet[0] = 1;
for (int i=1; i<fakultaet.length; i++) 
    fakultaet[i] = i*fakultaet[i-1];

    Stimmt, es klappt auch mit deinem Codebeispiel. Ich dachte, dass man das fakultaet-array komplett mit 1 initialisieren muss, da in der darauffolgenden for-Schleife sonst alle Ergebnisse mit 0 multipliziert werden würden.
    Warum es jetzt aber auch so klappt (also lediglich fakultaet[0] = 1), hab ich ehrlich gesagt, noch nicht ganz verstanden

    0
  • J

    Weil die einzelnen Fakultäten sukzessive über den Vorgänger berechnet werden.

    f[0] = 1;
f[1] = 1 * f[0] = 1 * 1 = 1;
f[2] = 2 * f[1] = 2 * 1 = 2;
f[3] = 3 * f[2] = 3 * 2 = 6;
usw...
    0
  • A

    Fakultät berechnen schreit ja quasi nach Rekursion: 😉

    public class Fakultaet 
{ 
    long fakultaet(int x)
    {
     	if (x == 0) {
            return 1;
      	} else {
            return x * fakultaet(x-1);
        }
    }

    public static void main(String[] args) 
    { 
            System.out.print("Die Fakultaet von 13 ist "); 
            System.out.println(fakultaet(13)); 
    } 
}

    😃

    0
  • ?

    Ajaw schrieb:

    Fakultät berechnen schreit ja quasi nach Rekursion: 😉

    Sieht toll aus, aber bei Fakultät ist Rekursion genau das, was man nicht benutzen sollte.

    0
  • G
    Mod

    Entenverwickler schrieb:

    Ajaw schrieb:

    Fakultät berechnen schreit ja quasi nach Rekursion: 😉

    Sieht toll aus, aber bei Fakultät ist Rekursion genau das, was man nicht benutzen sollte.

    Warum nicht? Ich verstehe diesen Einwand ja, wenn es um Fibonaccizahlen oder so geht. Aber bei der Fakultät? Meinst Du, Java hat mit 13 rekursiven Aufrufen ein Problem? 🙂

    0
  • V

    BTW: Größere Zahlen lassen sich berechnen indem du dir selber ne Klasse für größe Zahlen schreibst:

    Naive Implementierung:
    http://loop.servehttp.com/~vertexwahn/oldwiki/public_html_an_turing/BigInt.java

    0
  • L

    Vertexwahn schrieb:

    BTW: Größere Zahlen lassen sich berechnen indem du dir selber ne Klasse für größe Zahlen schreibst:

    Naive Implementierung:
    http://loop.servehttp.com/~vertexwahn/oldwiki/public_html_an_turing/BigInt.java

    Da gibt es schon eine Klasse, nämlich java.math.BigInteger

    0
  • G

    Zum Fall Fakultät berechnen gibt es grundsätzlich zwei Methoden:

    1. Iteration while (!exit) {...} oder for (...) {...}

    2. Rekursion recursiveFunction(int value) ruft "rekursiv" recursiveFunction(int value)

    Beide Methoden haben ihre Vor- un Nachteile:

    1. Häufig ist der Code simpler aber dafür muss man einen möglichen Stack-Overflow im Auge behalten.

    2. Iterartion rufen sich nicht selber auf, darum wird deshalb kaum ein Stack-Overflow riskiert.
      Dafür muss jedoch für etwas mehr "Infrastruktur" gesorgt werden.

    Sollte man besser und tiefer erklären, aber zum Thema kann ich nicht mehr beitragen! 🙂

    Zur Demonstration einer rekursiven Funktion wird gerne das Problem der FakultätsBerechnung genommen.
    Fazit: Hierzu sollte eine Fülle an Infos zu finden sein!

    0
  • P

    Iterativ:

    public static long fakultaet(long n) {
    long ret = 1;
    for(int i = 1; i <= n; ++i) {
        ret *= i;
    }
    return ret;
}

    rekursiv:

    public static long fakultaet(long n) {
    if(n = 1)
        return 1;
    else
        return n * fakultaet(n-1);
}

    Hoffe, dass die Rekursion so stimmt.

    0
  • ?

    Nein, ist sie nicht. Erstens gilt 0!=1 und sollte damit das Abbruchkriterium sein und zweitens wird bei deiner Version, bei n<1, mit hunderprozentiger Sicherheit eine Stackoverflow-Exception auftreten.

    Gruss

    0
  • J

    dgsgdter schrieb:

    und zweitens wird bei deiner Version, bei n<1, mit hunderprozentiger Sicherheit eine Stackoverflow-Exception auftreten.

    Nein! Es wird mit 100% Sicherheit keine Stackoverflow-Exception auftreten.

    Dazu müßte das Programm erst mal laufen
    und dazu erst mal kompilierbar sein.
    ( if(n = 1) )

    😃
    *SCNR*

    0
Anmelden zum Antworten