Schrittproblem

Diskutiere Schrittproblem im Java Basics - Anfänger-Themen Bereich.
B

baker333

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?

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];
    }
 
A

abc66

Na gut, dabei gibt es auch einen Schreibe- und Lesekopf, der an einer bestimmten Position auf einem Band steht, sich nach links und rechts einen Schritt bewegen kann und dabei 0oder1 lesen oder schreiben kann.
 
B

baker333

Okay, aber warum erhalte ich dann trotzdem den o.g. Wert 11? Dies macht für mich nur Sinn, wenn man den ganzen strahl inkl. Negativer Werte (also -n) betrachtet?
 
A

abc66

Also der Code ist nicht vollständig und daher etwas schwer nachzuvollziehen... ;)
 
A

abc66

Was soll die Methode denn berechnen? Das Index"Gewusel" macht es nicht gerade einfacher zu lesen...
 
F

fhoffmann

Der Index eines Arrays kann nicht negativ sein. Die Zahlen -n bis n muss man also "nach rechts verschieben".
 
A

abc66

Sorry, die Wahrscheinlichkeit, dass sich die Spielfigur nach nach n Schritten auf Position x befindet.
Java:
	public static float wahrscheinlichkeit(int n, int x1, int x2) {
		int d = Math.abs(x1 - x2);
		if (d > n) {
			return 0;
		}
		double w = Math.pow(0.5, d);
		return (float) w;
	}

	public static int position(int n, int x1) {
		for (int i = 0; i < n; i++) {
			if (x1 == 0) {
				x1++; // linker Rand
			} else if (x1 == 20) {
				x1--; // rechter Rand
			} else if (Math.random() < 0.5) {
				x1++;
			} else {
				x1--;
			}
		}
		return x1;
	}

	public static void main(String[] args) {
		System.out.println(wahrscheinlichkeit(51, 5, 10));
		int x = 0;
		for (int i = 0; i < 100; i++) {
			int p = position(51, 5);
			if (p == 10) {
				x++;
			}
		}
		System.out.println(x / 100.0);
	}
Aber warte mal einen Moment, denn die Wahrscheinlichkeit stimmt noch nicht (wegen den Rändern ).
 
A

abc66

Also, wenn man davon absieht, dass es KEINE Ränder gibt, dann wäre die Wahrscheinlichkeit:
Java:
	public static float wahrscheinlichkeit(int n, int x1, int x2) {
		int d = Math.abs(x1 - x2);
		if (d > n) {
			return 0;
		}
		double w = Math.pow(0.5, d / 2.0) / 2.0;
		return (float) w;
	}
/e Quatsch, wenn man annimmt, es gebe/gäbe keine Ränder. :D
 
A

abc66

@baker333 Habe jetzt die korrekte Wahrscheinlichkeit... Angenommen, wir starten auf einem Zahlenstrahl von 0 bis 20 bei 5 und bewegen uns genau 11 Schritte. Wie hoch ist die Wahrscheinlichkeit, beim 11. Schritt bei 2 stehen zu bleiben? (0.18799... nach Adam Riese....)
Java:
	public static float wahrscheinlichkeit(int n, int x1, int x2) {
		if (n == 0)
			if (x1 == x2)
				return 1;
			else
				return 0;
		if (x1 == 0)
			return wahrscheinlichkeit(n - 1, x1 + 1, x2);
		if (x1 == 20)
			return wahrscheinlichkeit(n - 1, x1 - 1, x2);
		return (wahrscheinlichkeit(n - 1, x1 + 1, x2) + wahrscheinlichkeit(n - 1, x1 - 1, x2)) / 2f;
	}

	public static int position(int n, int x1) {
		for (int i = 0; i < n; i++) {
			if (x1 == 0) {
				x1++; // linker Rand
			} else if (x1 == 20) {
				x1--; // rechter Rand
			} else if (Math.random() < 0.5) {
				x1++;
			} else {
				x1--;
			}
		}
		return x1;
	}

	public static void main(String[] args) {
		System.out.println(wahrscheinlichkeit(11, 5, 2));
		int x = 0;
		for (int i = 0; i < 1_000_000; i++) {
			int p = position(11, 5);
			if (p == 2) {
				x++;
			}
		}
		System.out.println(x / 1_000_000.0);
	}
 
A

abc66

Vllt sind im Skript auch Fehler :D
Möglich, aber ich kann das durch bloßes Daraufschauen nicht verifizieren...

/e Wir können uns noch "Pruning" zunutze machen:
Java:
	public static float wahrscheinlichkeit(int n, int x1, int x2) {
		if (n == 0)
			if (x1 == x2)
				return 1;
			else
				return 0;
		if (Math.abs(x1 - x2) > n)
			return 0; // Pruning
		if (x1 == 0)
			return wahrscheinlichkeit(n - 1, x1 + 1, x2);
		if (x1 == 20)
			return wahrscheinlichkeit(n - 1, x1 - 1, x2);
		return (wahrscheinlichkeit(n - 1, x1 + 1, x2) + wahrscheinlichkeit(n - 1, x1 - 1, x2)) / 2f;
	}

	public static int position(int n, int x1) {
		for (int i = 0; i < n; i++) {
			if (x1 == 0) {
				x1++; // linker Rand
			} else if (x1 == 20) {
				x1--; // rechter Rand
			} else if (Math.random() < 0.5) {
				x1++;
			} else {
				x1--;
			}
		}
		return x1;
	}

	public static void main(String[] args) {
		System.out.println(wahrscheinlichkeit(21, 5, 2));
		int x = 0;
		for (int i = 0; i < 10_000; i++) {
			int p = position(21, 5);
			if (p == 2) {
				x++;
			}
		}
		System.out.println(x / 10_000.0);

		System.out.println(wahrscheinlichkeit(21, 5, 8));
		x = 0;
		for (int i = 0; i < 10_000; i++) {
			int p = position(21, 5);
			if (p == 8) {
				x++;
			}
		}
		System.out.println(x / 10_000.0);
	}
 
Zuletzt bearbeitet:
mihe7

mihe7

Angenommen, wir starten auf einem Zahlenstrahl von 0 bis 20 bei 5 und bewegen uns genau 11 Schritte. Wie hoch ist die Wahrscheinlichkeit, beim 11. Schritt bei 2 stehen zu bleiben?
Das kommt darauf an, mit welcher Wahrscheinlichkeit Du Dich bei jedem Schritt in eine bestimmte Richtung bewegst :)
 
A

abc66

@mihe7
Java:
	public static float wahrscheinlichkeit(int n, int x1, int x2, float toRightProbability) {
		if (n == 0)
			if (x1 == x2)
				return 1;
			else
				return 0;
		if (Math.abs(x1 - x2) > n)
			return 0; // Pruning
		if (x1 == 0)
			return wahrscheinlichkeit(n - 1, x1 + 1, x2, toRightProbability);
		if (x1 == 20)
			return wahrscheinlichkeit(n - 1, x1 - 1, x2, toRightProbability);
		return wahrscheinlichkeit(n - 1, x1 + 1, x2, toRightProbability) * toRightProbability
			 + wahrscheinlichkeit(n - 1, x1 - 1, x2, toRightProbability) * (1 - toRightProbability);
	}

	public static int position(int n, int x1, float toRightProbability) {
		for (int i = 0; i < n; i++) {
			if (x1 == 0) {
				x1++; // linker Rand
			} else if (x1 == 20) {
				x1--; // rechter Rand
			} else if (Math.random() < toRightProbability) {
				x1++;
			} else {
				x1--;
			}
		}
		return x1;
	}

	public static void main(String[] args) {
		float toRightProbability = 0.25f;
		int n = 10_000;

		System.out.println(wahrscheinlichkeit(21, 5, 2, toRightProbability));
		int x = 0;
		for (int i = 0; i < n; i++) {
			int p = position(21, 5, toRightProbability);
			if (p == 2) {
				x++;
			}
		}
		System.out.println(x / (double) n);

		System.out.println(wahrscheinlichkeit(21, 5, 8, toRightProbability));
		x = 0;
		for (int i = 0; i < n; i++) {
			int p = position(21, 5, toRightProbability);
			if (p == 8) {
				x++;
			}
		}
		System.out.println(x / (double) n);
	}
"Es" bewegt sich mit einer Wahrscheinlichkeit von 0.75 nach links. Wenn man bei 5 startet, ist es viel wahrscheinlicher, bei 2 stehen zu bleiben, als bei 8 stehen zu bleiben....
 
mihe7

mihe7

@abc66 jetzt noch als "iterative Bottom-Up Lösung" geschrieben, dann dürftest Du auf die Musterlösung kommen.
 
Thema: 

Schrittproblem

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben