iterative und rekursive Folge

L

Lila2010

Gast
Ich soll diese Folge iterativ und rekursiv programmieren f(n) = f(n-1) - f(n-2) + n
Ich habe das so gemacht, bin mir aber nicht sicher, da ich nicht wirklich weiß, wie eine iterativ programmierte Folge aussehen soll..
Java:
 import java.util.Scanner;
public class Beispiel18 {
	
	public static int f(int n, int a, int b){
		if(n==0){
			return a;
		}
		else if(n==1){
			return b;
		}
		else {
			return f(n-1, a , b)-f(n-2, a , b)+n;
		}
		
	}

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		System.out.println("a0 = ");
		int a = s.nextInt();
		System.out.println("a1 = ");
		int b = s.nextInt();
		System.out.println("Welches Folgeglied ak soll berechnet werden? ");
		int k = s.nextInt();
		
System.out.println(f(k, a, b));
		
		int an = 0;
		for(int i = 2; i <= k; i ++ ){
			an = b - a + i;
			a = b;
			b = an;
		}
		System.out.println(an);
	}
}

Jetzt soll ich folgendes weiter machen:
Teste diese rekursive Methode im Vergleich zum iterativen Ansatz in einem Benchmark(um auf aussagekräftige Zahlen zu kommen, sollte dieselbe Berechnung genügend oft wiederholt werden; siehe Glossar)
Hinweis: Verwende den Typ long und berechne die ersten 40 Zahlen.

Das verstehe ich leider nicht.. Was ist denn ein Benchmark?? Was will man hier von mir??

Bitte um Hilfe!
Lg
 
0din

0din

Bekanntes Mitglied
Benchmark
um da nen gescheiten bench zu machn würd ich die zeit messen die das ganze zum errechnen braucht.
System.getCurrentTimeMillies oder so ähnlich gibt dir die ms ... einfach am anfang / ende messen, abziehn un du weißt wie lang das ganze zum errechnen braucht...

un der code den du da gemacht hast is nicht(!) iterativ sondern recursiv...
recursiv = sich selbst aufrufend
iterativ = das ganze mit schleifen o.ä. lösen, ohne die methode selbst aufzurufen
 
Final_Striker

Final_Striker

Top Contributor
Für den iterativen Ansatz:

Du kennst das Ergebnis von f(0) und f(1). Damit kannst du mit deiner Formel ganz einfach f(2) berechnen und dann f(3) usw. Das in eine Schleife gepackt, ergibt den iterativen Algorithmus. ;-)

Edit:

Für den Benchmark wie oben schon gesagt. In einer Schleife x-Mal f(40) berechnen lassen und die dafür benötigte Zeit messen. Das Ergebnis durch x geteilt ergibt dann die durchschnittliche Zeit, die der Algorithmus für die Berechnung gebraucht hat.

Und in deinen Algorithmen int durch long ersetzen. ;-)
 
Zuletzt bearbeitet:
L

Lila2010

Gast
Oke, danke, dann werde ich mal wohl besser noch bisschen länger mit Benchmark beschäftigen, bevor ich wieder dazu was poste.. Aber wegen der Iteration... Warum meint ihr, dass das nicht stimmt? :

Java:
int an = 0;
        for(int i = 2; i <= k; i ++ ){
            an = b - a + i;
            a = b;
            b = an;
        }
        System.out.println(an);
    }

ich beginne doch hier mit den anfangswerten und berechne dann mittels einer schleife den Wert.. das ist doch genau das was ich tun soll.. oder nicht?

Danke,
lg
 
0din

0din

Bekanntes Mitglied
ach der zweite teil soll dat selbe machn?
dann isses n mischmasch... ich hat die f-methode gesehn... mein fehler, ignorier was ich sagte...

un so schwer is son bench au net...
zeit messen, speicher
rekursion abjuckeln lassen
zeit messen, woanders speichern
(zweite zeit - erste zeit) / anzahl elemente = bench für rekursion

zeit speichern,
iterieren lassen,
zeit2 speichern,
un wieder: (zweite - erste) / anzahl elemente = bench für iteration
 
L

Lila2010

Gast
Oke, danke, mein Problem daran ist eig, dass ich den Befehl für Zeit messen im internet einfach nicht herausfinden kann =/
was muss ich da eingeben bei meiner schleife von vorhin z.b. ??
 
Landei

Landei

Top Contributor
Java:
long time = System.currentTimeMillis();
//eine lange Berechnung
System.out.println("Die Berechnung hat " + 
   (System.currentTimeMillis() - time) + "ms gedauert");
 
C

crackm

Mitglied
Zuletzt bearbeitet:
L

Lila2010

Gast
Danke!
Wegen dem 2. post --> das war keine absicht, hab anscheinend zu schnell auf senden geklickt und dann wurde es doppelt gepostet =/

also ich hab jetzt versucht das ganze auf meine schleife anzuwenden.. aber irgendwas stimmt da ganz und gar nicht, weil es kommt immer 0 ms heraus ...

Java:
		int an = 0;
		long j = 0;
		long time = System.currentTimeMillis();
		while(j < 1000000000){
		for(int i = 2; i <= k; i ++ ){
			an = b - a + i;
			a = b;
			b = an;
		}
		j++;
		}
		long endtime = System.currentTimeMillis();
		System.out.println("Die Berechnung hat " + 
		   ((endtime - time)/1000000000) + " ms gedauert");
		System.out.println(an);
	}

Was stimmt denn daran jetzt wieder nicht??
 
Final_Striker

Final_Striker

Top Contributor
Bei der Division von ganzen Zahlen kommt immer 0 raus wenn der Nenner größer ist als der Zähler ist.
Bsp.: 3 / 6 = 0 und nicht 0,5

edit:

Ein Tipp. Lagere deinen Code in zwei Methoden aus. z.B. berecheRenursiv(long n) und berecheIterativ(long n). Dann wird das ganze auch gleich viel übersichtlicher ;-)

Java:
long start = System.currentTimeMillis();

for(int i = 0; i < 1000000; i++){

   berechneIterative(40);
}

long stop = System.currentTimeMillis();
 
Zuletzt bearbeitet:
L

Lila2010

Gast
Danke..
hmhmhm also bei mir schaut das jetzt so aus:

Java:
		long start = System.currentTimeMillis();
		
			for(int j = 0; j < 1000000; j++){

				for(int k = 2; k <= 40; k++){
					for(int i = 2; i <= k; i ++ ){
						an = b - a + i;
						a = b;
						b = an;
					}
				}
			}
			long stop = System.currentTimeMillis();
}
}

Wie kann ich mir denn das ganze jetzt ausgeben lassen, sodass der Zähler nicht kleiner als der Nenner ist?? =/
Ist das jetzt nicht genau dasselbe wie vorher nur mit einer For, statt einer While schleife??
 
Final_Striker

Final_Striker

Top Contributor
Ach ja, hatte ich vergessen.^^

Muss die long Zahlen in ein double casten. ((double)(stop- start)/(double)1000000000) + " ms gedauert");
 
L

Lila2010

Gast
Super, vielen dank jetzt funktionierts :)

Jetzt soll ich noch folgendes machen:
Verbessere die rekursive Berechnung der Folgenglieder der Art, dass Zwischenergebnisse in einem Array zwischengespeichert werden. Ist das Zwischenergebnis bekannt, gib es zurück - wenn nicht, führe die Berechnung aus und speicher das Ergebnis.

???
Wie speichere ich denn Funktionswerte in einem Array??
 
L

Lila2010

Gast
achja, danke.
Nur was heißt:
Ist das Zwischenergebnis bekannt, gib es zurück - wenn nicht, führe die Berechnung aus und speicher das Ergebnis.
??
Die Zwischenergebnis sind doch immer bekannt, sonst würde ich sie ja nicht speichern =/
Und muss ich das ganze in die Funktionendefinition vom Anfang schreiben oder in das public static void .... ?
 
S

SlaterB

Gast
Ist das Zwischenergebnis schon mal ausgerechnet worden, gib es direkt zurück ohne es neu zu berechnen (5ns)
- wenn nicht, führe die Berechnung aus (50000ns) und speicher das Ergebnis und gib es dann zurück.
 
Final_Striker

Final_Striker

Top Contributor
Na, bring man euch in der Schule oder wofür auch immer du das machst nichts mehr bei? ;-)

Wenn du am Anfang deiner f-Methode
System.out.println("f("+ n +")");
einbaust und ausführst, wird dir auffallen, dass f(n) mehrmals für gleiche n-Werte ausgeführt wird.

z.B: f(4) führt zu folgenden Aufrufen:

f(4)
f(3)
f(2)
f(1)
f(0)
f(1)
f(2)
f(1)
f(0)

a und b hab ich jetzt einfacher halber weggelassen.

Das Ergebnis von f(2) wird nicht gespeichert sondern nur verwendet um f(3) auszurechnen und danach "weggeworfen". Wenn rekursionsbedingt wieder f(2) gebraucht wird, muss es wieder aus f(1) - f(2) + n berechnen werden.

Wenn du aber das Ergebnis des ersten Aufrufs von f(2) speicherst, kannst du es beim zweiten mal einfach verwenden anstatt f(2) wieder zu berechen.

Als Tipp:
Bei der Berechnung von f(x) hast du x-1 Zwischenergebnisse. Um diese einfacher zu verwalten, speichert man die am besten in einem Array unter dem Aufruf-Index. Also im Feld array[5] speicherst du das Ergebnis von f(5).

Du musst jetzt deine Methode f abändern, dass die Berechnung so aussieht:

f(5) = [Ergebnis 4 bekannt dann array[4] sonst f(4)] - [Ergebnis 3 bekannt dann array[3] sonst f(3)] + [ 5 ]

Hoffe mal das es einigermaßen verständlich war.^^
 
S

SlaterB

Gast
die Abfrage nach dem Array sollte aber nicht zweimal kodiert werden, aus
> f(5) = [Ergebnis 4 bekannt dann array[4] sonst f(4)] - [Ergebnis 3 bekannt dann array[3] sonst f(3)] + [ 5 ]
wird
f(5) bekannt? dann zurückgeben, sonst normal berechnen
;)
 
C

crackm

Mitglied
Ich hacke mal nach
Java:
public int g(int num){
   int num_e[] = new int[num];
   
   for(int i=0; i<num; i++){
     if(i==0 || i==1){
       num_e[i]=1;
     } else {
       num_e[i]= num_e[i-2]+num_e[i-1];
     }
   }
   return num_e[num-1];
 }
Zeigt eigentlich das "abspeichern" und einen iterativen Ansatz, denn man eher verweden würden...
 
B

blubb_blubb

Gast
Ich hab auch eine Frage zu dem Beispiel. So wie es hier programmiert ist, gibt ja eigentlich nur einen (den letzten) Wert der Folge aus. Wie muss man den Befehl fürs Rekursive umschreiben, damit es alle Folgenglieder ausgibt?
 
S

SlaterB

Gast
z.B. eine for-Schleife über alle Werte von 0 bis k, wenn du dich auf das erste Posting beziehst,
da wird dann vieles doppelt gerechnet, aber nur einmal ausgegeben,
n der Rekursion ist die Ausgabe nicht so toll da dort jeder Wert zweimal ausgegeben wird (ausprobieren),
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
shiroX OOP Rekursive und Iterative Definition Java Basics - Anfänger-Themen 2
T Iterative Pi Berechnung in Rekursive Java Basics - Anfänger-Themen 2
A Rekursive Methode in Iterative umwandeln Java Basics - Anfänger-Themen 6
G rekursive u iterative Methode Java Basics - Anfänger-Themen 8
F Erste Schritte Hausaufgaben-Prob. - Iterative Prog. Zahlen aufsummieren, wenn durch k>0 teilbar. Java Basics - Anfänger-Themen 5
C Lineare Rekursion -> iterative Schleife Java Basics - Anfänger-Themen 3
T Iterative Berechnung einer Satellitenbahn Java Basics - Anfänger-Themen 20
P iterative Berechnung Java Basics - Anfänger-Themen 9
R Differenz Iterative Java Basics - Anfänger-Themen 14
R Summe Iterative Java Basics - Anfänger-Themen 6
veryck Methoden Rekursive Methoden mit Rückgabeparameter Java Basics - Anfänger-Themen 9
macle Rekursive String Methode, Gerade Zahlen rausfiltern Java Basics - Anfänger-Themen 10
M Rekursive Prüfung ob ein Array sortiert ist... Java Basics - Anfänger-Themen 4
J Rekursive swapArray Methode Java Basics - Anfänger-Themen 69
D Rekursive Methode Java Basics - Anfänger-Themen 8
R Methoden rekursive Methoden Java Basics - Anfänger-Themen 6
O Quersumme rekursive Methode Java Basics - Anfänger-Themen 3
B Treetable (rekursive Funktion) aufbauen von Datenbank Java Basics - Anfänger-Themen 4
M Rekursive Methode Programmieren Java Basics - Anfänger-Themen 3
J rekursive Methode Java Basics - Anfänger-Themen 26
M rekursive division/0 mit exception Java Basics - Anfänger-Themen 18
J Rekursive Methode - Ziffern einer Zahl ausgeben Java Basics - Anfänger-Themen 2
M Rekursive Dateiliste erstellen mit Dateiendung(en) ?? Java Basics - Anfänger-Themen 4
S Rekursive Methode Java Basics - Anfänger-Themen 8
O Rekursive Methode Java Basics - Anfänger-Themen 4
V Methoden Rekursive Methode mit String als Rückgabe Java Basics - Anfänger-Themen 7
K Rekursive Methode Java Basics - Anfänger-Themen 1
K Rekursive Methode für Fakultät mit BigInteger Java Basics - Anfänger-Themen 10
L Rekursive Methode a * b berechnen Java Basics - Anfänger-Themen 2
L Rekursive Methode zur Berechnung der Potenz q hoch p Java Basics - Anfänger-Themen 17
J Methoden Rekursive Return Methode Java Basics - Anfänger-Themen 2
G Harmonische Rekursive Folge Java Basics - Anfänger-Themen 3
T Stack Overflow - Rekursive Fibonacci Java Basics - Anfänger-Themen 10
B Datentypen Suchbaum - Rekursive Ausgabe Java Basics - Anfänger-Themen 1
P Methoden Rekursive Methode für Potenzen Java Basics - Anfänger-Themen 2
M Methoden Binäre Suche als rekursive Variante Java Basics - Anfänger-Themen 5
B Rekursive Algorithmus schreiben Java Basics - Anfänger-Themen 8
S Eine rekursive Lösung Java Basics - Anfänger-Themen 4
S Int zu Hexadezimal - Rekursive Methode Java Basics - Anfänger-Themen 2
M Rekursive Suche in einem Feld Java Basics - Anfänger-Themen 11
N Rekursive Addition mit Scanner Java Basics - Anfänger-Themen 12
B Methoden Rekursive Methoden Java Basics - Anfänger-Themen 2
C rekursive methode Java Basics - Anfänger-Themen 2
D Methoden Rekursive Methoden Java Basics - Anfänger-Themen 13
R rekursive Methode funktioniert nicht Java Basics - Anfänger-Themen 4
M Stürzen alle Rekursive Methoden irgendwann ab? Java Basics - Anfänger-Themen 11
D Primzahlen und Rekursive Liste Java Basics - Anfänger-Themen 29
R Rekursive Methode, Files finden Java Basics - Anfänger-Themen 2
S rekursive folge verbessern Java Basics - Anfänger-Themen 2
C rekursive Methode verstehe nicht! Java Basics - Anfänger-Themen 3
S Methoden rekursive Methode funktioniert nicht Java Basics - Anfänger-Themen 4
E Rekursive Methode Java Basics - Anfänger-Themen 3
N Methoden Rekursive Fibonaccizahlen mit Array Java Basics - Anfänger-Themen 2
R Rekursive Ausgabe eines Binärbaums Java Basics - Anfänger-Themen 4
J Methoden Rekursive Potenz ohne Math.Pow() Java Basics - Anfänger-Themen 9
S Labyrith Rekursive Wegsuche Java Basics - Anfänger-Themen 4
C Rekursive Methode - Ziffern in Zahl Java Basics - Anfänger-Themen 33
U Dezimal zu Hexadezimal rekursive Funktion Java Basics - Anfänger-Themen 8
M rekursive Funktion zur Berechnung der Spiegelzahl Java Basics - Anfänger-Themen 7
G Rekursive Methode Java Basics - Anfänger-Themen 3
A rekursive Listen in Java? Java Basics - Anfänger-Themen 5
B OOP Einfach verkettete Liste - rekursive Methoden Java Basics - Anfänger-Themen 1
E Rekursive Methode mit Zufallsarray Java Basics - Anfänger-Themen 6
E Rekursive Methode Java Basics - Anfänger-Themen 18
U Rekursive lösung von pascal dreieck Java Basics - Anfänger-Themen 11
M Rekursive Methode - wo ist der Fehler? Java Basics - Anfänger-Themen 4
J rekursive methode Java Basics - Anfänger-Themen 6
H ScrollBar inaktiv / Rekursive Methode Java Basics - Anfänger-Themen 4
J Rekursive Methode Java Basics - Anfänger-Themen 11
G Rekursive Methode Java Basics - Anfänger-Themen 5
N Rekursive Berechnung der Höhe eines binären Baumes Java Basics - Anfänger-Themen 4
K Rekursive Methoden Java Basics - Anfänger-Themen 15
K Rekursive Funktion (Verständnissfrage) Java Basics - Anfänger-Themen 5
S Rekursive Bruch potenzierung Java Basics - Anfänger-Themen 2
D rekursive Summenberechnung Java Basics - Anfänger-Themen 8
J Rekursive Methode: Fakultaet berechnen Java Basics - Anfänger-Themen 5
E Rekursive definierten Folge Java Basics - Anfänger-Themen 10
A HILFE! Rekursive Funktion Java Basics - Anfänger-Themen 20
kulturfenster rekursive Binaere Suche Java Basics - Anfänger-Themen 12
F Rekursive Aufrufe, Parameterübergabe, call by reference Java Basics - Anfänger-Themen 3
G Rekursive Berechnung von n über k schlägt fehl Java Basics - Anfänger-Themen 5
B Rekursive & schreiben im ArrayList Java Basics - Anfänger-Themen 2
J Rekursive Fkt. Java Basics - Anfänger-Themen 2
A Rekursive Dateisuche Java Basics - Anfänger-Themen 12
K rekursive Funktion mit mehreren Parametern Java Basics - Anfänger-Themen 5
G rekursive Methode Java Basics - Anfänger-Themen 3
N rekursive Beispiele Java Basics - Anfänger-Themen 3
G Rekursive Methode Java Basics - Anfänger-Themen 7
ven000m Rekursive Funktionen - Frage Java Basics - Anfänger-Themen 16
D rekursive ausgabe einer zahl Java Basics - Anfänger-Themen 14
S Rekursive Funktionen in imperative Funktionen umwandeln Java Basics - Anfänger-Themen 2
M Rekursive Binärsuche Java Basics - Anfänger-Themen 6
S rekursive methoden Java Basics - Anfänger-Themen 5
D Hofstäter Q Folge Java Basics - Anfänger-Themen 3
V Fibonacci Folge Java Basics - Anfänger-Themen 4
M Methoden Fibonacci-Folge Java Basics - Anfänger-Themen 6
J Fibonacci -Folge rekursiv berechnen Java Basics - Anfänger-Themen 18
S Negafibonacci Folge berechnen Java Basics - Anfänger-Themen 24
T Algortihmus: Kürzeste Folge zu einer Zahl Java Basics - Anfänger-Themen 40
M Fibonacci-Folge mit while-Schleife Java Basics - Anfänger-Themen 4

Ähnliche Java Themen

Anzeige

Neue Themen


Oben