首页 > 代码库 > 一个算法习题学习的好去处-有不同语言的实现
一个算法习题学习的好去处-有不同语言的实现
这不是个人传销,而是在学习过程中发现的一个比较好的地方,因此向大家推荐一下,希望能有所帮助~
虽然只有一个链接,但是这个链接的重量就在那里,不知道能发向首页不??
为了凑字数,下面给出了一篇在上述网站中的一个题目解析:
------------------------------
链接地址:http://openhome.cc/Gossip/AlgorithmGossip/MathPI.htm
From Gossip@Openhome
Algorithm Gossip: 蒙地卡羅法求 PI
說明
蒙地卡羅為摩洛哥王國之首都,該國位於法國與義大利國境,以賭博聞名。蒙地卡羅的基本原理為以亂數配合面積公式來進行解題,這 種以機率來解題的方式帶有賭博的意味,雖然在精確度上有所疑慮,但其解題的思考方向卻是個值得學習的方式。
解法
蒙地卡羅的解法適用於與面積有關的題目,例如求PI值或橢圓面積,這邊介紹如何求PI值;假設有一個圓半徑為1,所以四分之一 圓面積就為PI,而包括此四分之一圓的正方形面積就為1,如下圖所示:
如果隨意的在正方形中投射飛標(點)好了,則這些飛標(點)有些會落於四分之一圓內,假設所投射的飛標(點)有n點,在圓內的 飛標(點)有c點,則依比例來算,就會得到上圖中最後的公式。
至於如何判斷所產生的點落於圓內,很簡單,令亂數產生X與Y兩個數值,如果X^2+Y^2小於1就是落在圓內。
實作:C Java Python Scala Ruby JavaScript Haskell
- C
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 50001
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 - 1));
return 0;
}
- Java
import static java.lang.Math.*;
public class MonteCarlo {
public static void main(String[] args) {
final int N = 50001;
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 - 1));
}
}
- Python
from random import random
N = 50001
print("PI =", 4 * len([1 for i in range(1, N)
if random() ** 2 + random() ** 2 < 1]) / (N - 1))
- Scala
import java.lang.Math._
val N = 50000
printf("PI = %f%n", 4.0 * (for(i <- 1 to N
if(pow(random(), 2) + pow(random(), 2) < 1)) yield 1).size / N)
- Ruby
N = 50000
print "PI = ", 4.0 * (1...N).map {
rand ** 2 + rand ** 2 < 1 ? 1 : 0 }.reduce(:+) / N
- JavaScript
Array.prototype.reduce = function(init, f) {
var value = http://www.mamicode.com/init;
for(var i = 0; i < this.length; i++) {
value = http://www.mamicode.com/f(value, this[i]);
}
return value;
};
function range(n) {
var r = [];
for(var i = 0; i < n; i++) {
r[i] = i;
}
return r;
}
var n = 50000;
print(4 * range(n).map(function() {
var x = Math.random();
var y = Math.random();
return x * x + y * y < 1 ? 1 : 0;
}).reduce(0, function(ac, elem) {
return ac + elem;
}) / n);
- Haskell
import System.Random
rand gen n= take n $ randomRs (0.0, 1.0) gen::[Float]
main = do
gen1 <- getStdGen
gen2 <- newStdGen
let n = 50000
ic = length [1 | (x, y) <-
zip (rand gen1 n) (rand gen2 n), (x ** 2 + y ** 2) < 1]
print (4 * fromIntegral ic / fromIntegral n)
一个算法习题学习的好去处-有不同语言的实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。