Vorschlag für Aufgabe 6 (Dynamische Programmierung) Altklausur SS15

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Vorschlag für Aufgabe 6 (Dynamische Programmierung) Altklausur SS15

public class DynProg {

	private static int[] a;

	public DynProg(int max) {
		this.a = new int[max];
	}

	static int f(int n) {
		return n < 3 ? 1 : f(n - 2 * f(n - f(n - 1))) + 1;
	}

	static int fDP(int n) { // Dynamische Programmierung
		int fn = 1; // Basisfall n < 3 trivial
		// fn schon einmal berechnet?
		if (n > 3 && n < a.length && a[n] != 0) {
			return a[n];
		} else if (n >= 3) {
			int temp = fDP(n - 2 * fDP(n - fDP(n - 1))) + 1; // fn muss noch
																// berechnet
																// werden
			if (n < a.length) {
				a[n] = temp;
				return a[n];
			}
			return temp;
		}
		return fn;
	}

	static int fIter(int n) { // Iterativ
		int k = 1; // Zaehler
		int fk = 1;
		for (k = 1; k <= n; k++) { //one may write instead: for(; k<=n; k++) {
			for (int i = 1; i <= (1 + k) * k; i++) {
				if (i == n) {
					return fk;
				}
			}
			fk++;
		}

		return fk;

	}

	public static void main(String[] args) {

		for (int i = 1; i <= 20; i++) { // Test f
			System.out.print(f(i) + " ");
		}
		System.out.println();

		int max = 10;
		int n = 20;
		int result = new DynProg(max).fDP(n); // Test fDP
		for (int i = 0; i < max; i++) { // a[0], a[1] are the trivial cases,
										// that fDP handles itself (read
										// exercise description)
			System.out.print(a[i] + " ");
		}
		System.out.println();
		System.out.println(result);

		for (int i = 1; i <= 20; i++) { // Test fIter
			System.out.print(fIter(i) + " ");
		}
	}
}
3

Wie kommst du auf (1+k)*k in for (int i = 1; i <= (1 + k) * k; i++)?

Ich habe das so gelöst:

[code=java]public static int fIter(int n) {
int k = 1;
int fk = 1;

int offset = 0;
while (k < n) {
	k++;
	if (k > offset + 2*fk) {
		offset += 2 * fk;
		fk++;
	}
}

return fk;

}[/code]

4

Ich zähle hier einfach stupide die Zahl der Terme, Gauß’sche Summenformel. Viel Magie ist da nicht dabei, das war auch das erste was mir hierzu eingefallen ist. Ich finde deine Lsg. daher auch schöner, da du (denke ich) die ganzen Terme weglässt, die ich bei mir mehrmals zähle.

5

Ich hätte das so gelöst:

public static int fIter(int n){
	int k = 1;
	int fk = 1; // Den Codebereich darf man in der Klausur leider nicht löschen.
	fk = 0;
	while(fk < n){
		fk += 2 * k;
		k++;
	}
	return k - 1;
}
6

Wieso brauche ich bei der Abfrage “if (n > 3 && n < a.length && a[n] != 0)” den Teil mit n < a.length? :cry:

7

Sollte das Array a nicht n-viele Stellen haben, dann kannst du auch nicht prüfen, ob ein größerer Wert berechnet wurde oder nicht. Beispiel:

int [] a = new int[5];
int n = 6;
if( a[n] != 0 ){
  ...
}

Das wird definitiv einen ArrayIndexOutOfBounds-Fehler verursachen, weil es die gefragte Position (also das n) gar nicht im Array a gibt.

1 „Gefällt mir“
8

Danke