# Methoden



## hos15 (21. Jul 2016)

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:

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

Literativ :


```
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 (22. Jul 2016)

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 (22. Jul 2016)

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.


----------



## Cromewell (22. Jul 2016)

InfectedBytes hat gesagt.:


> z.b in dem du ein Array anlegst, in welchem du bereits berechnete Werte speicherst.


Spontan würde ich sagen, dass sich eine Hashmap anbieten würde - mit n und n! drin.


----------



## Thallius (22. Jul 2016)

Cromewell hat gesagt.:


> Spontan würde ich sagen, dass sich eine Hashmap anbieten würde - mit n und n! drin.



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


----------



## Xyz1 (22. Jul 2016)

Thallius hat gesagt.:


> , mal ganz davon abgesehen das ein Zugriff auf eine Hashmap um etliches langsamer ist als ein Zugriff auf ein Array.



Asymptotisch betrachtet nicht, Nein. Aber ich will dich nicht unnötig provozieren.


----------



## Thallius (22. Jul 2016)

DerWissende hat gesagt.:


> Asymptotisch betrachtet nicht, Nein. Aber ich will dich nicht unnötig provozieren.



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.


----------



## Xyz1 (22. Jul 2016)

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


----------



## VfL_Freak (22. Jul 2016)

Leute, Leute .... ha'm wir's jetzt ?????


----------



## Xyz1 (22. Jul 2016)

VfL_Freak hat gesagt.:


> Leute, Leute .... ha'm wir's jetzt ?????



Angefangen hat alles damit, dass ich eine Aufgabe für eine Klausur als für zu schwierig erachtet hab - und damit offenbar nicht Claus' Geschmack getroffen hab.


----------



## VfL_Freak (22. Jul 2016)

Moin,


DerWissende hat gesagt.:


> Angefangen hat alles damit, dass ich eine Aufgabe für eine Klausur als für zu schwierig erachtet hab


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


----------



## Cromewell (22. Jul 2016)

Thallius hat gesagt.:


> Wozu willst du denn den n Wert speichern


Frage ich mich auch gerade


----------



## hos15 (22. Jul 2016)

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 ?


----------



## hos15 (22. Jul 2016)

```
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


----------



## Xyz1 (22. Jul 2016)

On-topic: Ungewöhnlich, aber mit Arrays ginge das so:

```
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.


----------



## Meniskusschaden (22. Jul 2016)

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.





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.


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.


----------



## Xyz1 (22. Jul 2016)

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.



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?


----------



## hos15 (22. Jul 2016)

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 ?


----------



## Xyz1 (22. Jul 2016)

hos15 hat gesagt.:


> Hat jemand eine "leichtere" Lösung ?



Ja, aber das klingt schon arg nach Erschleichen von Hausaufgaben.  Nee, mach ich nicht.


----------



## Meniskusschaden (22. Jul 2016)

DerWissende hat gesagt.:


> Sicher, nicht unbedingt niedriger?


Ja, falls `korrekterWert-(2*Integer.MAX_VALUE)>vorherigerWert`gilt (zumindest ungefähr, bin zu faul, es ganz exakt auszurechnen).


hos15 hat gesagt.:


> Hat jemand eine "leichtere" Lösung ?


Wozu denn? Soweit ich es erkennen kann, ist der Vorschlag von @DerWissende eine Lösung zu Aufgabe 1). Da hast du doch längst eine Lösung.


----------



## hos15 (22. Jul 2016)

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 ?


----------



## Meniskusschaden (22. Jul 2016)

Ja, das ist ungefähr dasselbe, wie das, was ich in Posting #16 geschrieben habe. Dort steht auch mein Lösungsvorschlag.


----------



## InfectedBytes (22. Jul 2016)

Die Array Lösung sollte auch eher in diese Richtung gehen:

```
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.


----------



## hos15 (22. Jul 2016)

Also Leute ich habe eine neue Idee und bin sehr gespannt was ihr dazu sagt 

```
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 ?


----------



## InfectedBytes (22. Jul 2016)

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?


----------



## hos15 (22. Jul 2016)

genau das gleiche habe ich mich auch gefragt eben 
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:
> 
> ```
> static int fakultaet_r(int wert) {
> ...


----------



## InfectedBytes (22. Jul 2016)

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.


----------



## mrBrown (22. Jul 2016)

Oder man nutzt die Methoden aus Math zum multiplizieren, dann gäb's ne Exception wenns überläuft


----------



## hos15 (22. Jul 2016)

Mhh ich verrstehe  Ich werde das gleich ausprobieren vielen dank dafür


----------



## hos15 (22. Jul 2016)

du meinst aber glaube ich n! /n = (n-1)!


----------



## hos15 (22. Jul 2016)

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


----------



## Xyz1 (22. Jul 2016)

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.



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


----------



## InfectedBytes (22. Jul 2016)

hos15 hat gesagt.:


> du meinst aber glaube ich n! /n = (n-1)!


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.


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


----------



## Xyz1 (22. Jul 2016)

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



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.



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.


----------



## hos15 (22. Jul 2016)

Also habe dann die 2 so gelöst :


```
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;  
         }       
     }
    }
```


----------



## Xyz1 (22. Jul 2016)

Einfach mal folgende Methode implementieren:

```
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.


----------

