rekursive folge verbessern

[student123]

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

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

 

[SlaterB]

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

 

[KI21]

Hallo student 123,

1. Klassennamen werden in Java immer großgeschrieben (Rekursion).
2. Eine Liste anlegen in der man die Werte zwischen speichert.

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.

public void run() {
}

5. Damit du deine Werte in ein Array packen kannst brauchst du eine Instanz der Klasse Rekursion. In der Funktion main.

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.

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.