Dymnamische Programmieren.

[japa]

Ich schreibe am Montag meine Prüfung und ich kämpfe gerade mit solchen Aufgaben, ich brauche daher dringend eine Hilfe von euch.
Diese Gleichung soll ich mit und ohne Rekursiv programmieren.

public class Re {

	/**
	 * @param args
	 */
	public int f (int n, int k){
		if(n==k || k==0){
			return 1;
		} else if(0<=k && k<n){
			return f(n-1,k-1)+f(n-2,k-1)+f(n-1,k);
		}
		return 0;
	}

}

public class It {
	public int f (int n,int k){
		int summe = 0;

		if(n==k || k==0){
			return 1;
		}else if(0<=k && k<n){
			for(int u=0;k>u;u++){ // Teil1 der Gleichung
				for(int v=n;v!=k;v--){ //Teil2 der Gleichung
					for(int w=n ; w!=k;w-- ){ // Teil3 der Gleichung
						summe++;
					}
				}
			}
		}//ende else

		return summe;
	}
}

Ich schaffe es jedoch nicht ohne rekrusiv zu machen, ich versuche schon seit gestern, ich komme mit 2 Variablen einfach nicht klar, ich hoffe sehr auf eure Hilfe
Kann mir niemanden weiterhelfen?.:rtfm:

 

[Marco13]

Wie sieht denn die Aufgabenstellung für den iterativen Teil aus? Soll das (wie der Titel suggeriert) mit dynamsicher Programmierung gelöst werden? (Alles andere wäre ziemlich fummelig...). In der Klausur würde ich dann auch noch fragen, ob das "," denn nun UND oder ODER bedeuten soll noe.

 

[japa]

Aufgabe lautet
e) (30 Punkte)
Implementieren Sie f als statische Java-Methode ohne Rekursion inklusive aller benötigten
Variablen und deren Initialisierungen. Wenden Sie dazu die Technik des Dynamischen
Programmierens an.

Rekursiv programmieren war Aufgabe a, es wäre sehr nett, wenn du eine lösung für mich hättest.
mfg

 

[Marco13]

OK, die Lösung hinschreiben werde ich jetzt nicht, aber... OHNE GEWÄHR auf Richtigkeit würde ich sagen, dass man da einen 2D-Array der Größe [n][k] anlegt, und befüllt, und am Ende das Element rechts unten zurückgibt.

Bildlich gesprochen werden ja, wenn man das Element X berechnen will, die drei Elemente A,B und C addiert...:

    --> n
 |  +---+---+---+
 v  | B | A |   |
 k  +---+---+---+
    |   | C | X |
    +---+---+---+

 

[japa]

Hab mir eine tabelle gemacht und nach deinem tipp gemacht, es hat nach 2 stunden geklappt, danke.

public class It {
	public int f (int n,int k){
		
	if(n==k || k==0){
		return 1;
	} else if (n-k==1 ||k==1){
		return n*2-1;
	}
	
	int [][] a= new int [n+1][k+1];
	for(int i = 0;i<=n;i++){
		a[i][0]=1;
		if(i<=k){
			a[i][i]=1;
		}
	}
	int spalte = 1;
	int zeile = 2;
	
	while (spalte <=k){
		a[zeile][spalte] = a[zeile-1][spalte-1] + a[zeile-2][spalte-1] + a[zeile-1][spalte];
		zeile++;
		if (zeile > n){
			spalte++;
			zeile = spalte+1;
		}
	}
	return a[n][k];
	}
}