Probabilistische Algorithmen SS11

Aus ProgrammingWiki

Archivierte Version vom 2011-05-07T16:02:58+00:00. Aktuelle Version

Numerische probabilistische Algorithmen

Algorithmen dieser Art produzieren eine Näherungslösung mit wählbarer Genauigkeit.

Ein Beispiel für diese Klasse von Algorithmen ist die Bestimmung einer Näherung für die Zahl \pi durch "Zufallsregen". Dabei werden n Regentropfen auf eine quadratische Fläche fallen gelassen, in der sich ein Kreis befindet. Anschließend werden die Regentropfen gezählt, die innerhalb des Kreises gefallen sind.

Es wird angenommen, dass jeder Punkt im Quadrat exakt dieselbe Wahrscheinlichkeit hat, von einem Tropfen getroffen zu werden. Ist der Radius des Kreises r, so ist seine Fläche \pi r^2, wobei die Fläche des Quadrats 4r^2 ist. Somit ist der durchschnittliche Anteil der Tropfen, die innerhalb des Kreises landen, \pi r^2 / 4r^2 = \pi / 4. Damit kann \pi mit \pi \approx 4 k / n geschätzt werden.

Codebeispiel eines Algorithmus, der mit "Zufallsregen" arbeitet. Je höher n gewählt wird umso genauer lässt sich \pi abschätzen.

public static float rain(int n){
	
	Random randomGenerator = new Random();
	float a = 0;
	int k = 0;
		
		for(int i = 0; i < n; i++){
			int x = randomGenerator.nextInt(2);
			int y = randomGenerator.nextInt(2);		
			
				if(x*x + y*y <= 1){
					k = k+ 1;					
				}
		}
		return a = 4*k/n;
}

rain(100);

Probabilistische Algorithmen SS11

Numerische probabilistische Algorithmen

Suche