rekursive folge verbessern

S

student123

Mitglied
guten abend zusammen,

ich soll im rahmen meiner programmier-uniübung eine rekursive folgenberechnung so verbessern, dass die benötigte zeit für die berechnung der ersten 30 glieder reduziert wird (als vergleich wird die gleiche folge auch iterativ berechnet). In der angabe steht, ich soll einfach die zwischenergebnisse in einem array speichern, und diese, sofern sie bekannt sind, zur berechnung verwenden, um rekursionen einzusparen.

mein problem dabei: ich kann das array ja nicht innerhalb der funktion definieren, da es sonst mit jedem rekursiven aufruf der funktion neu initialisiert wird (und damit der speichervorgang der zwischenergebnisse für die katz ist), oder täusche ich da?

andererseits kann ich das array auch schlecht in meiner main umgebung initialisieren, da ich aus der funktion heraus nicht auf die dort gespeicherten zwischenergebnisse zugreifen kann.

wo ist der fehler in meinem gedankengang? oder verstehe ich die anweisung einfach falsch?
danke schonmal

Java:
public class rekursion {

        public static int f(int n) {

        int wert1 = 0;
        int wert0 = 0;
        int wert2 = 1;
        
        if (n == 0)
            return wert0;
        else if (n == 1)
            return wert1;
        else if (n == 2)
            return wert2;
        else 
            return (f(n - 1) + 101 * f(n - 2) + 503 * f(n - 3) + n * n ) % 997;
        }
        
    public static void main(String[] args) {

        double zeit1 = System.nanoTime();
        int a = 30;  
      
        for (int i = 0 ; i < 30; i++){
                System.out.println(i + "\t" + f(i));           
        }
        
        double zeit2 = System.nanoTime();
           
       // ab hier beginnt iterative Berechnung
            int rek0=0;
            int rek1=0;
            int rek2=1;            
            System.out.println("0\t"+rek0);
            System.out.println("1\t"+rek1);
            System.out.println("2\t"+rek2);
            
        for(int q=3;q<=a;q++){

            int rek3=(rek2+101*rek1+503*rek0+q*q)%997;
            System.out.println(q+"\t"+rek3);
            rek0=rek1;                                                             
            rek1=rek2;
            rek2=rek3;
            
            
        }
            double zeit3=System.nanoTime();
            double rekzeit=zeit2-zeit1;
            double forzeit=zeit3-zeit2;
            System.out.println("Benötigte Zeit der for-Schleife: "+forzeit);
            System.out.println("Benötigte Zeit der Rekursion: "+rekzeit);
    }
 
S

SlaterB

Gast
wie sollen Fremde, die die Anweisung nicht kennen, das beurteilen?
im geposteten Text steht jedenfalls keine Einschränkung,
du kannst das Array statisch verwenden, als Instanzattribut (ok, weniger bei statischer Methode) oder Methodenparameter,
die goldenen drei zu jeder Informationsübergabe,
und dass du eine Übergabe brauchst hast du selber erkannt, nur innerhalb einer Methode kommst du nicht weit,

halb begrenzt würde Rückgabewert reichen, nur die Informationen aus unteren Ebenen sammeln,
aber dem Rückgabewert zu erweitern wäre ja noch drastischer als ein Parameter
 
Zuletzt bearbeitet von einem Moderator:
K

KI21

Neues Mitglied
Hallo student 123,

1. Klassennamen werden in Java immer großgeschrieben (Rekursion).
2. Eine Liste anlegen in der man die Werte zwischen speichert.
Java:
private List<Integer> zwischenspeicher = new ArrayList<Integer>();

3. Man brauch eine Methode (z.B. run) die man aufrufen kann wenn man eine Instanz von der Klasse Rekursion instanziiert hat.
Java:
public void run() {
}

5. Damit du deine Werte in ein Array packen kannst brauchst du eine Instanz der Klasse Rekursion. In der Funktion main.
Java:
public static void main(String[] args) {
		new Rekursion().run();//Direkter aufruf der Methode run()
	}

6. Mit zwischenspeicher.add(/*ein zwischenergebnis*/); kannst du ein Zwischenergebnis hinzufügen.

So sieht mein Ergebnis aus. Ich wusste nur nicht wo du deine Zwischenergebnisse abspeichern willst.



Java:
import java.util.ArrayList;
import java.util.List;

public class Rekursion {
	private List<Integer> zwischenspeicher = new ArrayList<Integer>();

	public void run() {
		double zeit1 = System.nanoTime();
		int a = 30;

		for (int i = 0; i < 30; i++) {
			System.out.println(i + "\t" + f(i));
		}

		double zeit2 = System.nanoTime();

		// ab hier beginnt iterative Berechnung
		int rek0 = 0;
		int rek1 = 0;
		int rek2 = 1;
		System.out.println("0\t" + rek0);
		System.out.println("1\t" + rek1);
		System.out.println("2\t" + rek2);

		for (int q = 3; q <= a; q++) {

			int rek3 = (rek2 + 101 * rek1 + 503 * rek0 + q * q) % 997;
			System.out.println(q + "\t" + rek3);
			rek0 = rek1;
			rek1 = rek2;
			rek2 = rek3;

		}
		double zeit3 = System.nanoTime();
		double rekzeit = zeit2 - zeit1;
		double forzeit = zeit3 - zeit2;
		System.out.println("Benötigte Zeit der for-Schleife: " + forzeit);
		System.out.println("Benötigte Zeit der Rekursion: " + rekzeit);
	}

	public int f(int n) {

		int wert1 = 0;
		int wert0 = 0;
		int wert2 = 1;

		if (n == 0)
			return wert0;
		else if (n == 1)
			return wert1;
		else if (n == 2)
			return wert2;
		else
			return (f(n - 1) + 101 * f(n - 2) + 503 * f(n - 3) + n * n) % 997;
	}

	public static void main(String[] args) {
		new Rekursion().run();
	}
}

Ich hoffe ich bin dir eine große Hilfe gewesen.
 
Zuletzt bearbeitet:
Ähnliche Java Themen
  Titel Forum Antworten Datum
G Harmonische Rekursive Folge Java Basics - Anfänger-Themen 3
L iterative und rekursive Folge Java Basics - Anfänger-Themen 20
E Rekursive definierten Folge Java Basics - Anfänger-Themen 10
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
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
shiroX OOP Rekursive und Iterative Definition Java Basics - Anfänger-Themen 2
B Methoden Rekursive Methoden Java Basics - Anfänger-Themen 2
T Iterative Pi Berechnung in Rekursive 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
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
A Rekursive Methode in Iterative umwandeln Java Basics - Anfänger-Themen 6
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
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 u iterative Methode Java Basics - Anfänger-Themen 8
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
J Byte Folge erkennen Java Basics - Anfänger-Themen 5
A Gerade Terme der Fibonacci-Folge aufsummieren Java Basics - Anfänger-Themen 12
R Roboter - Helmich Folge 6 Java Basics - Anfänger-Themen 32
H JOptionPane YES Option mit Folge? Java Basics - Anfänger-Themen 2
P Collatz-Folge mittels indirekter Rekursion Java Basics - Anfänger-Themen 5
X Problem mit Ducci-Folge Java Basics - Anfänger-Themen 7

Ähnliche Java Themen

Anzeige


Oben