楽しいアルゴリズム

今日新浪微博の中で宝を洗う文初大師の発起に注目しました:#一日一技術の分かち合い#今日林信良のよくあるアルゴリズムのノートを分かち合って、1つの“モンテカルロ法はPIを求めます”のアルゴリズムを見てとても面白いと感じて、問題を解く構想は本当に鬼斧神工ですね、思考の発散と開発、乱数確率の方法で問題を解きます「精度には疑問があるが、問題を解く方向は学ぶべき方法だ」と原文にある.
 
 
Algorithm Gossip:モンテカルロ法PIを求める
モンテカルロはモロッコ王国の首都で、フランスと義大利の国境に位置し、賭博で有名だと説明した.モンテカルロの基本原理は乱数配合面積公式で解題することであり,確率的に解題する方式は賭博の意味を持ち,精度に疑問があるが,その解題の思考方向は学習に値する方式である.解法モンテカルロの解法は面積に関する問題に適用され、例えばPI値や楕円面積を求める.ここではPI値を求める方法を紹介する.1つの円半径が1であると仮定すると、4分の1の円面積はPI/4であり、この4分の1の円を含む正方形面積は1であり、下図に示すように:
正方形に任意に飛標(点)を投射すれば、これらの飛標(点)は4分の1円内に落ちるものがあり、投射された飛標(点)にn点があり、円内の飛標(点)にc点があると比例して計算すると、上図中の最後の公式が得られる.発生した点が円内に落ちるとどう判断するかは簡単で、乱数にXとYの2つの数値を発生させ、X^2+Y^2が1未満であれば円内に落ちる.実作:C Java Python Scale

C

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

#define N 50000 

int main(void) { 
 srand(time(NULL)); 
    
 int sum = 0;
    
 int i;
 for(i = 1; i < N; i++) { 
 double x = (double) rand() / RAND_MAX; 
 double y = (double) rand() / RAND_MAX; 
 if((x * x + y * y) < 1) 
 sum++; 
 } 

 printf("PI = %f/n", (double) 4 * sum / N); 

 return 0; 
} 

Java

import static java.lang.Math.*;
public class Main {
 public static void main(String[] args) {
 final int N = 50000;
 int sum = 0; 
 for(int i = 1; i < N; i++) 
 if((pow(random(), 2) + pow(random(), 2)) < 1) 
 sum++; 
 System.out.printf("PI = %f%n", 4.0 * sum / N); 
 }
}

Python

import random

N = 50000
sum = 0
for i in range(1, N):
 if (random.random() ** 2 + random.random() ** 2) < 1:
 sum += 1
print("PI = ", 4 * sum / N)

Scala

import java.lang.Math._

val N = 50000

var sum = 0
for(
 i <- 1 until N
 if (pow(random(), 2) + pow(random(), 2)) < 1
) sum += 1

printf("PI = %f%n", 4.0 * sum / N);

     ：     ：http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/AlgorithmGossip.htm