Folgenglieder

[Nirvana]

Bereche die Folgenglieder:
f(n) = f(n-1) + 101 * f(n-2) + 503*f(n-3) + n^2 (mod 997)
Anfangswert f(0)=f(1)=0 und f(2)=1
Programmiere die Folge sowohl interativ als auch rekursiv.
Berechne die ersten 30 Zahlen.

rekursiv habe ich so versucht:

double fn (int n){
       if (n==0||n==1){
           return 0;}
       if (n==2)
           return 1;
       else
           return (fn(n-1)+101*fn (n-2)+503*fn (n-3)+n*n)%997;}

Ist das korrekt?

interativ schaffe ich nicht ganz.
Ich weiß interativ ist mittels einer Schleife,ohne die Funktion selbst aufzurufen.
Beginne ich den interativen teil genauso wie den rekursiven? Oder definiere ich fn(0),fn(1),fn(2) in der schleife? Definiere ich genauso wie oben eine Funktion double fn (int n) am anfang?

 

[Fant]

Für eine iterative Lösung merkst du dir die drei aktuellen Zahlen und berechnest die nächst-Folgende. Dann nimmst du die alte zweite Zahl als erste, die dritte als zweite und die neue als dritte und gehst in den nächsten Schleifendurchlauf.

Gruß Fant

 

[Nirvana]

danke dir, ich hab es geschafft.
Nun: Teste diese rekursive Methode im Vergleich zum interativen ANsatz in einem Benchmark (um auf aussagekräftige Zahlen zu kommen, sollte dieselbe berechnung genügend oft wiederholt werden)

Hab gesurft und gefunden:

long start = System.currentTimeMillis();
// Berechnung
long stop = System.currentTimeMillis();
System.out.println("Die Berechnung hat " + stop-start + "ms gedauert");

Aber wo ich das auch hintuhe bei dem rekursiven Teil kommt ein Fehler raus.
Also stimmt das oben zu berechnung der Zeit und wo tuhe ich das in meinem Teil (im ersten beitrag gepostet) hin?

 

[Firephoenix]

Das Stück nicht in der Methode selber sondern um den ersten Methodenaufruf packen (vermutlich in deiner main-Methode).

z.b. so:

public static void main(String[] args){
long start = System.currentTimeMillis();
fn(400);
long stop = System.currentTimeMillis();
System.out.println("Die Berechnung hat " + stop-start + "ms gedauert");
}

(geht nur wenn fn auch static ist, ansonsten erzeug dir eine instanz der klasse und ruf darauf fn auf)

Gruß

 

[Nirvana]

Danke,

Mich verwirrt nur noch das im Angabetext steht: um auf aussagekräftige Zahlen zu kommen, sollte dieselbe Berechnung genügend oft wiederholt werden
Das heißt doch eigentlich nicht, dass man ein hohes n nehmen soll, sondern dass das Programm dasselbe paarmal rechnen soll oder?
Also in der main eine Schleife noch herum.

for(int q = 0; q < 100; q++){
fn(10);}

Hab ich das richtig verstanden?

 

[Nirvana]

Nun ist noch eine Aufgabe, die unmittelbar mit dieser zu tun hat:
Verbessere die rekursive Berechnung der Folgenglieder derart, dass Zwischenergebnisse für f(i) in einem Array zwischengespeichert werden. Ist das Zwischenergebnis bekannt, gib es zurück - wenn nicht, führe die Berechnung aus und speicher das Ergebnis.

Aufgabenstellung ist soweit klar. Wenn das Zwischenergebnis schon einmal ausgerechnet worden ist, soll er es nicht neu berechnen sonden direkt zurückgeben vom gespeicherten Platz.
In der Aufgabe steht der Hinweis mit Array, der anfang zur initalisierung wäre also:

static int fn (int n){
    int[] fn = new int[n+1];
    fn [0] = 0;
    fn [1] = 1;
    fn [2] = 1;

Wie krieg ich nun hin dass er die zwischenergebnisse jeweils in einen Array speichert und dann auf diese, wenn sie vorhanden sind zugreift?

 

[Fant]

Danke,
Mich verwirrt nur noch das im Angabetext steht: um auf aussagekräftige Zahlen zu kommen, sollte dieselbe Berechnung genügend oft wiederholt werden
Das heißt doch eigentlich nicht, dass man ein hohes n nehmen soll, sondern dass das Programm dasselbe paarmal rechnen soll oder?
Hab ich das richtig verstanden?

Ja, genau so ist das gemeint.


Für den anderen Aufgabenteil musst du beachten, dass du das Hilfsarray schon außerhalb der Methode, die sich rekursiv aufrufen soll, definierst. Wenn du bei jedem Aufruf ein neues Array verwendest, dann gehen deine gemerkten Zwischenergebnis ja wieder verloren.

Gruß Fant

 

[timbeau]

Du speicherst das Ergebnis von f(100) bei array[100] ab.

Guckst jedes mal ob das gesuchte Ergebnis schon im Array steht (array[n] != 0) und wenn nicht schreibst du es rein.

Das Array kann dabei als globale Variable stehen, außerhalb der Main.

 

[Nirvana]

Dazu ein paar Frage.
Ich habe nun das array außerhalb main und der Rekursion definiert.

Soll ich die Anfangsarray-werte in der Main oder in der Rekursion definieren? Überall kommt eine fehlermeldung.
Genauso stellt sich die Frage wo ich die Länge des Array definiere, weil wenn ich sie in der Main definiere, weiß mein Programm nicht was n ist.

 

[Fant]

Hab leider meine Glaskugel verliehen...

 

[Nirvana]

Hat sich erledigt, danke