Methoden

H

hos15

Aktives Mitglied
Hallo Liebe Java Freunde habe folgende Aufgabe :

1. Schreiben Sie zwei Methoden zur Berechnung der Fakultätsfunktion n!, einmal iterativ und einmal rekursiv.

2. Schreiben Sie eine weitere Methode, in der ermittelt wird bis zu welchem Argument n die Methode (eine der beiden genügt) ein sinnvolles Ergebnis liefert. Woran kann man dies erkennen (Tipp: Zahlendarstellung)?

3. In einer Anwendung werden sehr oft die Werte von n! benötigt. Wie könnte man Rechenzeit sparen und vermeiden, dass jedesmal wieder die Rechnung ausgeführt wird (Beschreibung des Prinzips genügt)?


Also zu 1 : Rekrusiv:
Java: 
static int fakultaet_r( int wert ) {
if( wert == 0 || wert == 1) return 1;
else return fakultaet_r(wert - 1) * wert;
}

Literativ :

Java: 
static int fakultaet( int wert ) {
int result = 1;
// Argument ausserhalb des Wertebereiches ?
if( wert < 0 ) return -1;
while( wert > 1 ) {
result *= wert;
--wert;
 
}
return result;
}

Was mein Problem ist ? Die Aufgabe 2 und die Aufgabe 3 bringt mich zum verzweifeln ich verstehe es einfach nicht.
 
njans

njans

Top Contributor
Aufgabe 2: Fakultäten wachsen sehr schnell. Ein Datentyp (int, long, double, float) können nur einen gewissen Wertebereich abdecken. Bei int und long werden ab einer gewissen Größe die Zahlen plötzlich negativ. Einfach mal Werte berechnen und gucken, wann der folgende plötzlich negativ wird.
 
InfectedBytes

InfectedBytes

Top Contributor
Ein int hat eben nur eine feste Größe von 32 Bit und damit lassen sich nur Zahlen im Bereich von etwa -2 Milliarden bis +2 Milliarden darstellen. Irgendwann wird deine Fakultätsfunktion eben zwei Zahlen multiplizieren, welche eben nicht mehr durch einen int darstellbar sind. Es wird zu einem Overflow kommen und plötzlich ist das Ergebnis kleiner als der vorherige Wert.
Bei 2 sollst du nun eine Funktion schreiben welche herausfindet wie groß das Argument n maximal sein darf.

Bei 3: z.b in dem du ein Array anlegst, in welchem du bereits berechnete Werte speicherst.
 
Thallius

Thallius

Top Contributor
Cromewell hat gesagt.:
Spontan würde ich sagen, dass sich eine Hashmap anbieten würde - mit n und n! drin.
Zum Vergrößern anklicken....

Wozu willst du denn den n Wert speichern wenn du eh von 0 - x rechnest? Dann hat Array[x] immer den Wert n!. Da n noch mit zu speichern verdoppelt nur den benötigten Speicher, mal ganz davon abgesehen das ein Zugriff auf eine Hashmap um etliches langsamer ist als ein Zugriff auf ein Array.

Gruß

Claus
 
Thallius

Thallius

Top Contributor
DerWissende hat gesagt.:
Asymptotisch betrachtet nicht, Nein. Aber ich will dich nicht unnötig provozieren. ;)
Zum Vergrößern anklicken....

Hast du eigentlich von irgendwas eine Ahnung du wissender?

Schau dir mal den Bytecode für den Zugriff auf ein Element in einem Array an, welches direkt über den Index angesprochen wird und dann den Zugriffauf eine Hashmap das über einen Key angesprochen wird,. Und danach reden wir dann weiter. Naja oder besser nicht, denn bei Dir kommt eh nichts sinnvolles raus.
 
X

Xyz1

Gast
Naja, du scheinst doch arge Schwierigkeiten mit dem Verständnis von Datenstrukturen und der Mathematik allgemein zu haben... Nicht mein Problem.
 
VfL_Freak

VfL_Freak

Top Contributor
Moin,
DerWissende hat gesagt.:
Angefangen hat alles damit, dass ich eine Aufgabe für eine Klausur als für zu schwierig erachtet hab
Zum Vergrößern anklicken....
Mal ganz davon abgesehen, ob es Dir zusteht, irgendwelche Klausuren von irgendwelchen Schulen/Unis zu kritisieren ... erörtet die Kleinkriege dann doch besser per PN, anstatt hier öffentlich! Das hilft werde dem TO noch macht ihr Euch Freunde damit ;)

Gruß Klaus
 
H

hos15

Aktives Mitglied
vielen Dank für die vielen Antworten Liebe Java freunde ihr seit echt eine große Hilfe ! :)
zu 2: Also ich muss doch zum Code was oben schon da steht eine weitere Kleinigkeit hinzufügen.. so wenn das Ergebnis Negativ wird das der Compiler an der Stelle abbricht aber wie mache ich das ?
 
H

hos15

Aktives Mitglied
Java: 
public static void main( String[]args){
    int i=0;
     for(int n=2;n<100;n++){
         System.out.println(fakultaet(n));
         if(fakultaet(n)<0){
             i=n ;
                
                 System.out.println("Überschritten"+i) ;
         }
     }

    
   
}

wäre das so richtig ? jedesmal wenn die fakultaet<0 ist wird es angezeigt.
Aber ich weiß nicht ob public static void main eine Methode ist bzw ob Der Prof es so meint
 
X

Xyz1

Gast
On-topic: Ungewöhnlich, aber mit Arrays ginge das so:
Java: 
    static int fakultaet_r(int wert) {
        if (wert == 0 || wert == 1) {
            return 1;
        } else {
            return fakultaet_r(wert - 1) * wert;
        }
    }

    static int fakultaet(final int wert) {
        if (wert == 0 || wert == 1) {
            return 1;
        }
        final int[] ia = new int[wert + 1];
        ia[0] = 1;
        ia[1] = 1;
        for (int i = 2; i < wert + 1; i++) {
            ia[i] = ia[i - 1] * i;
        }
        return ia[wert];
    }

    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {
            if (fakultaet_r(i) != fakultaet(i)) {
                System.out.println("Fehler");
            }
        }
    }

Bin mir gerade nicht sicher, ob das überhaupt die Fakultät ist. Jedenfalls, Fakultät von 100 berechnen macht eigentlich nur bei universalen Größenordnungen sinn.

Von mir aus können wir (auch) über das Speicherplatzverhalten diskutieren.

@ TO : Versuche zu verstehen, was dort passiert.
 
M

Meniskusschaden

Top Contributor
njans hat gesagt.:
Aufgabe 2: Fakultäten wachsen sehr schnell. Ein Datentyp (int, long, double, float) können nur einen gewissen Wertebereich abdecken. Bei int und long werden ab einer gewissen Größe die Zahlen plötzlich negativ. Einfach mal Werte berechnen und gucken, wann der folgende plötzlich negativ wird.
Zum Vergrößern anklicken....
InfectedBytes hat gesagt.:
Ein int hat eben nur eine feste Größe von 32 Bit und damit lassen sich nur Zahlen im Bereich von etwa -2 Milliarden bis +2 Milliarden darstellen. Irgendwann wird deine Fakultätsfunktion eben zwei Zahlen multiplizieren, welche eben nicht mehr durch einen int darstellbar sind. Es wird zu einem Overflow kommen und plötzlich ist das Ergebnis kleiner als der vorherige Wert.
Zum Vergrößern anklicken....
Wenn es zu einem Überlauf kommt, ist das errechnete Ergebnis meines Erachtens zwar niedriger als der korrekte Wert, jedoch nicht zwingend negativ und auch nicht unbedingt niedriger als der vorherige Wert. Ich glaube, ich würde zur Kontrolle einfach eine Probedivision machen.
 
X

Xyz1

Gast
Meniskusschaden hat gesagt.:
Wenn es zu einem Überlauf kommt, ist das errechnete Ergebnis meines Erachtens zwar niedriger als der korrekte Wert, jedoch nicht zwingend negativ und auch nicht unbedingt niedriger als der vorherige Wert. Ich glaube, ich würde zur Kontrolle einfach eine Probedivision machen.
Zum Vergrößern anklicken....

Sicher, nicht unbedingt niedriger?

@ TO : Ich weiß leider auch nicht genau, wie dein Prof es meint. Aber zumindest die Funktion fakultaet mit Array(s) hab ich dir richtig aufgeschrieben. :) War das jetzt schon wieder zu viel Hilfe? :(
 
H

hos15

Aktives Mitglied
Mhh das stimmt :/
das habe ich nicht beachtet :/
das mit Arrays würde ich lieber nicht machen das würde in der Klausur zu viel Zeit nehmen. Hat jemand eine "leichtere" Lösung ?
 
M

Meniskusschaden

Top Contributor
H

hos15

Aktives Mitglied
naja es ist schwieriger als ich dachte ich habe mir überlegt es so aufzuschreiben das wenn die Fakultät (n+1) < Fakultät (n) ist Der Compiler mir ein fehler anzeigen soll ab diesem Punkt ( da die Fakultät streng Monoton wächst) aber das klappt nicht immer der Wert (n+1) kann auch etwas größer sein als die Fakultät (n) und trotzdem kann es nicht der exakt korrekte Wert sein.
habe ich das jetzt erklären können was ich meine ?
 
InfectedBytes

InfectedBytes

Top Contributor
Die Array Lösung sollte auch eher in diese Richtung gehen:
Java: 
private static final int N = 12;
private static final int[] cache = new int[N + 1]; // 13! schon zu groß für integer
public static int fakultaet(int n) {
    if(n == 0) return 1;
    if(n < 0 || n > N) throw new IllegalArgumentException("Es muss 0 <= n <= 12 gelten");
    int f = cache[n];
    if(f == 0) // n! wurde noch nicht berechnet
        f = cache[n] = n * fakultaet(n - 1); // Berechnung nachholen und Ergebnis speichern
    return f;
}
Falls die Fakultät für eine Zahl noch nicht berechnet wurde (also cache[n] == 0 ist), so wird die Berechnung einfach nachgeholt und der Wert gespeichert.
Dies führt eben dazu, dass die Fakultät eben nicht immer neu berechnet werden muss.

In deiner Aufgabe steht nicht einmal das du es programmieren musst, sondern du sollst nur die Lösung beschreiben.
 
H

hos15

Aktives Mitglied
Also Leute ich habe eine neue Idee und bin sehr gespannt was ihr dazu sagt :D
Java: 
public class Fakultätet {


    static int fakultaet_i( int wert ) {
        if( wert == 0 || wert == 1) return 1;
        else return fakultaet_i(wert - 1) * wert;
        }
  
   
    static long fakultaet_l( long wert ) {
        if( wert == 0 || wert == 1) return 1;
        else return fakultaet_l(wert - 1) * wert;
        }
  

public static void main (String[]args){
    for(int i=0; i<20;i++){
        if(fakultaet_i(i)!=fakultaet_l(i)){
            System.out.println("fehler");
        }else{
            System.out.println(i);

        }

    }
}
}

Ich habe einfach den selben Code mit long aufgeschrieben und immer die Methode fakultät mit int mit der Methode fakultät long überprüft meint ihr das würde so gehen ? :D
 
Zuletzt bearbeitet von einem Moderator:
InfectedBytes

InfectedBytes

Top Contributor
Gehen würde es schon, ist aber etwas unsinnig, da du eben die Fakultät immer zweimal berechnest.
Und außerdem solltest du noch weiterdenken, was wenn die Aufgabe schon mit long arbeiten würde und du den long auf Überlauf überprüfen müsstest?
 
H

hos15

Aktives Mitglied
genau das gleiche habe ich mich auch gefragt eben :oops:
dein Posting #23 gehört das zur Aufgabe 3 ?
soll ich dann einfach das mit dem Array machen ? Also das hier :
DerWissende hat gesagt.:
On-topic: Ungewöhnlich, aber mit Arrays ginge das so:
Java: 
    static int fakultaet_r(int wert) {
        if (wert == 0 || wert == 1) {
            return 1;
        } else {
            return fakultaet_r(wert - 1) * wert;
        }
    }

    static int fakultaet(final int wert) {
        if (wert == 0 || wert == 1) {
            return 1;
        }
        final int[] ia = new int[wert + 1];
        ia[0] = 1;
        ia[1] = 1;
        for (int i = 2; i < wert + 1; i++) {
            ia[i] = ia[i - 1] * i;
        }
        return ia[wert];
    }

    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {
            if (fakultaet_r(i) != fakultaet(i)) {
                System.out.println("Fehler");
            }
        }
    }

Bin mir gerade nicht sicher, ob das überhaupt die Fakultät ist. Jedenfalls, Fakultät von 100 berechnen macht eigentlich nur bei universalen Größenordnungen sinn.

Von mir aus können wir (auch) über das Speicherplatzverhalten diskutieren.

@ TO : Versuche zu verstehen, was dort passiert.
Zum Vergrößern anklicken....
 
InfectedBytes

InfectedBytes

Top Contributor
genau, Posting #23 ist für Aufgabe 3
Die Array Variante die du zitiert hast, solltest du nicht verwenden, da es einfach nur die iterative Variante ist, welche unnötigerweise in einem lokalen Array zwischenspeichert, welches eben am Ende der Methode wieder gelöscht wird. Das dortige Array bringt dir also rein gar nichts.

Für Aufgabe zwei kannst du beispielsweise eine Probedivision machen, wie schon von @Meniskusschaden vorgeschlagen. Die Idee ist folgende:
Du berechnest n! wie folgt:
n! = n * (n-1)!
Um nun zu prüfen ob das Ergebnis stimmt, kannst du prüfen ob folgendes gilt:
n! / n = n-1
Denn falls es zu einem Überlauf kam, wird diese Bedingung nicht gelten.
 
H

hos15

Aktives Mitglied
Also die Aufgabe 2 verstehe ich jetzt zum Teil aber die Aufgabe 3 habe ich nicht verstanden auch mit deiner Erklärung leider nicht :(
 
X

Xyz1

Gast
InfectedBytes hat gesagt.:
genau, Posting #23 ist für Aufgabe 3
Die Array Variante die du zitiert hast, solltest du nicht verwenden, da es einfach nur die iterative Variante ist, welche unnötigerweise in einem lokalen Array zwischenspeichert, welches eben am Ende der Methode wieder gelöscht wird. Das dortige Array bringt dir also rein gar nichts.
Zum Vergrößern anklicken....

Ich habe lediglich das erbetene/gewünschte/angeforderte umgesetzt - nicht mehr, nicht weniger. Und alle Aufgaben löse ich ihm nicht. So far.
 
InfectedBytes

InfectedBytes

Top Contributor
hos15 hat gesagt.:
du meinst aber glaube ich n! /n = (n-1)!
Zum Vergrößern anklicken....
genau! Sorry, habe versehentlich das Ausrufezeichen weggelassen^^

DerWissende hat gesagt.:
Ich habe lediglich das erbetene/gewünschte/angeforderte umgesetzt - nicht mehr, nicht weniger. Und alle Aufgaben löse ich ihm nicht. So far.
Zum Vergrößern anklicken....
Nunja, nicht unbedingt. Dein Code beinhaltet nur eine rekursive und eine iterative Fakultätsfunktion. Diese hatte der TE jedoch schon selbst gelöst, er brauchte Hilfe zur zweiten/dritten Aufgabe
 
X

Xyz1

Gast
InfectedBytes hat gesagt.:
Nunja, nicht unbedingt. Dein Code beinhaltet nur eine rekursive und eine iterative Fakultätsfunktion. Diese hatte der TE jedoch schon selbst gelöst, er brauchte Hilfe zur zweiten/dritten Aufgabe
Zum Vergrößern anklicken....

Achso, dann hab ich das mehr oder weniger wiederholt...

https://de.wikipedia.org/wiki/Arithmetischer_Überlauf
Manche Prozessoren können einen Überlauf durch ein Überlaufbit registrieren.
Zum Vergrößern anklicken....

Darauf kann aber nicht zurückgegriffen werden... Also bei Aufgabe 2 Probedivision und bei 3... Ein Wort: "Zwischenspeichern", wird viell. nicht genügen - sollte aber vorkommen.
 
H

hos15

Aktives Mitglied
Also habe dann die 2 so gelöst :

Java: 
public static void main( String[]args){
        int o=0;
     for (int i=2;i<15; i++){
         if(F(i)/i != F(i-1) ) {          
              o=i;
              System.out.println(o);
            break;  
         }       
     }
    }
 
Zuletzt bearbeitet von einem Moderator:
X

Xyz1

Gast
Einfach mal folgende Methode implementieren:
Java: 
    static int n = 0;
    static int[] faks = new int[13];

    static int fakultaet_r(int wert) {
        if (wert == 0 || wert == 1) {
            return 1;
        } else {
            return fakultaet_r(wert - 1) * wert;
        }
    }

    static int fakultaet(int wert) {
        // ToDo
    }

    public static void main(String[] args) {
        Random r = new Random();
        long t1 = System.currentTimeMillis();
        for (int i = 0; i < 10000000; i++) {
            int temp = r.nextInt(13);
            if (temp != 0 && fakultaet_r(temp) / temp != fakultaet_r(temp - 1)) {
                System.out.println("Ohje");
            }
        }
        long t2 = System.currentTimeMillis();
        for (int i = 0; i < 10000000; i++) {
            int temp = r.nextInt(13);
            if (temp != 0 && fakultaet(temp) / temp != fakultaet(temp - 1)) {
                System.out.println("Ohje");
            }
        }
        long t3 = System.currentTimeMillis();
        System.out.println(t2 - t1);
        System.out.println(t3 - t2);
        System.out.println(100.0 / (t3 - t2) * (t2 - t1) - 100 + " % schneller");
    }

Wenn alles "glatt" läuft, dann sollte:
a) es keine Ausgabe "Ohje" geben,
b) deine Methode fakultaet 100 bis 115 % schneller sein als fakultaet_r.

:)

Edit: Jetzt hab ich ihm nicht die Lösung gezeigt, sondern nur Hinweise gegeben. ;)
 

Aktuelle Jobs

Neue Themen


Oben