Servus,
es geht um das Schrittproblem: es gibt einen Zahlenstrahl von -n bis n. Eine Spielfigur wird auf die Position 0 gesetzt und die Figur kann sich genau n mal entweder um eine Position nach links oder rechts bewegen. Dies mit der Wahrscheinlichkeit nach links p und nach rechts 1-p.
Ich soll nun eine iterative Bottom-Up Lösung schreiben und die sieht laut Musterlösung wie folgt aus:
Ich kapiere allerdings gerade nicht die arrayIndex Methode, obwohl sie den korrekten Array-Index für die Position x auf dem Zahlenstrahl von -n bis n wiedergeben soll. Muss wieder so ein dummer Denkfehler sein, aber wenn ich Position x = 5 und sagen wir n = 5 habe: Wieso ist der Array Index für die Position x 11?
es geht um das Schrittproblem: es gibt einen Zahlenstrahl von -n bis n. Eine Spielfigur wird auf die Position 0 gesetzt und die Figur kann sich genau n mal entweder um eine Position nach links oder rechts bewegen. Dies mit der Wahrscheinlichkeit nach links p und nach rechts 1-p.
Ich soll nun eine iterative Bottom-Up Lösung schreiben und die sieht laut Musterlösung wie folgt aus:
Ich kapiere allerdings gerade nicht die arrayIndex Methode, obwohl sie den korrekten Array-Index für die Position x auf dem Zahlenstrahl von -n bis n wiedergeben soll. Muss wieder so ein dummer Denkfehler sein, aber wenn ich Position x = 5 und sagen wir n = 5 habe: Wieso ist der Array Index für die Position x 11?
Java:
private static int arrayIndex(int x, int n) {
return n+x+1;
}
public static double schrittproblem(int n, double p, int x) {
if (n < 0) {
throw new IllegalArgumentException("Ungültige Eingabe!");
}
if (n<x) {
return 0;
}
if (n < -x) {
return 0;
}
/*
* erster Index des Feldes: Position auf dem Zahlenstrahl
* zweiter Index des Feldes = Anzahl der Schritte
*/
double [] [] s = new double [2*(n+1)+2][n+1];
//Schritte
for (int i = 0; i <= n; ++i) {
//Positionen
for (int j = -i; j<= i; ++j) {
if (i==0) {
s[arrayIndex(j, n)] [i] = 1;
}
else {
s[arrayIndex(j,n)][i] =
//von links
s[arrayIndex(j-1,n)][i-1]*(1-p)+s[arrayIndex(j+1,n)][i-1]*p;
//von rechts
}
}
}
return s[arrayIndex(x,n)][n];
}