更新中

分钱问题

分钱问题：一个房间里有100个人，每个人有100美元。每隔一定时间（比如1秒），每个有钱的人都会给随机选择的一个人一美元。经过一段时间的进展，这些钱将如何分配？

The post Counterintuitive problem: Everyone in a room keeps giving dollars to random others. You’ll never guess what happens next. appeared first on Decision Science News.

程序模拟结果：

模拟gif

核心代码：

1
2
3
4
5
6
7
8
9
10
//delay一定时间
//...
//数据处理
for(int i = 0 ; i < money.length; i ++){
    int j = (int)(Math.random() * money.length);
    money[i] -= 1;
    money[j] += 1;
}
//数据显示于屏幕
//...

这样一个混沌体系，随着时间增加，最终显示的状态是非常不稳定的。

蒙特卡洛算法暴力求PI值

蒙特卡罗算法并不是一种算法的名称，而是对一类随机算法的特性的概括。

这个名称只是概括了算法的特性。与之类似的称呼还有拉斯维加斯算法。

蒙特卡罗算法：采样越多，越近似最优解；
拉斯维加斯算法：采样越多，越有机会找到最优解；

这两类随机算法之间的选择，往往受到问题的局限。如果问题要求在有限采样内，必须给出一个解，但不要求是最优解，那就要用蒙特卡罗算法。反之，如果问题要求必须给出最优解，但对采样没有限制，那就要用拉斯维加斯算法。对于机器围棋程序而言，因为每一步棋的运算时间、堆栈空间都是有限的，而且不要求最优解，所以ZEN涉及的随机算法，肯定是蒙特卡罗式的。

核心思想：在边长为1的正方形方框内随机抛点，统计落在圆弧内的点所占比例。随着点数量的增加，这个比例越来越接近四分之一圆面积与正方形面积之比，即为PI/4。

核心代码：

一个圆类(Model)，并有计算点是否包含在其中的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.awt.*;
import javax.swing.*;

public class Circle {

    private int x, y, r;

    public Circle(int x, int y, int r){
        this.x = x;
        this.y = y;
        this.r = r;
    }

    public int getX(){ return x; }
    public int getY(){ return y; }
    public int getR(){ return r; }

    public boolean contain(Point p){
        return Math.pow(p.x - x, 2) + Math.pow(p.y - y, 2) <= r*r;
    }
}

一个另外的数据类（Model），用来记录点的相对位置，并能返回PI值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.LinkedList;
import java.awt.*;

public class MonteCarloPiData {

    private Circle circle;
    private LinkedList<Point> points;
    private int insideCircle = 0;

    public MonteCarloPiData(Circle circle){
        this.circle = circle;
        points = new LinkedList<Point>();
    }

    public Circle getCircle(){
        return circle;
    }

    public int getPointsNumber(){
        return points.size();
    }

    public Point getPoint(int i){
        if(i < 0 || i >= points.size())
            throw new IllegalArgumentException("out of bound in getPoint!");

        return points.get(i);
    }

    public void addPoint(Point p){
        points.add(p);
        if(circle.contain(p))
            insideCircle ++;
    }

    public double estimatePi(){

        if(points.size() == 0)
            return 0.0;

        int circleArea = insideCircle;
        int squareArea = points.size();
        return (double)circleArea * 4 / squareArea;
    }
}

一个可视化（View）相关类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import java.awt.*;
import java.util.LinkedList;
import javax.swing.*;

public class AlgoFrame extends JFrame{

    private int canvasWidth;
    private int canvasHeight;

    public AlgoFrame(String title, int canvasWidth, int canvasHeight){

        super(title);

        this.canvasWidth = canvasWidth;
        this.canvasHeight = canvasHeight;

        AlgoCanvas canvas = new AlgoCanvas();
        setContentPane(canvas);
        pack();

        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setResizable(false);

        setVisible(true);
    }

    public AlgoFrame(String title){

        this(title, 1024, 768);
    }

    public int getCanvasWidth(){return canvasWidth;}
    public int getCanvasHeight(){return canvasHeight;}

    // data
    private MonteCarloPiData data;
    public void render(MonteCarloPiData data){
        this.data = data;
        repaint();
    }

    private class AlgoCanvas extends JPanel{

        public AlgoCanvas(){
            // 双缓存
            super(true);
        }

        @Override
        public void paintComponent(Graphics g) {
            super.paintComponent(g);

            Graphics2D g2d = (Graphics2D)g;

            // 抗锯齿
            RenderingHints hints = new RenderingHints(
                    RenderingHints.KEY_ANTIALIASING,
                    RenderingHints.VALUE_ANTIALIAS_ON);
            hints.put(RenderingHints.KEY_RENDERING, RenderingHints.VALUE_RENDER_QUALITY);
            g2d.addRenderingHints(hints);

            // 具体绘制
            AlgoVisHelper.setStrokeWidth(g2d, 3);
            AlgoVisHelper.setColor(g2d, AlgoVisHelper.Blue);
            Circle circle = data.getCircle();
            AlgoVisHelper.strokeCircle(g2d, circle.getX(), circle.getY(), circle.getR());

            for(int i = 0 ; i < data.getPointsNumber() ; i ++){
                Point p = data.getPoint(i);
                if(circle.contain(p))
                    AlgoVisHelper.setColor(g2d, AlgoVisHelper.Red);
                else
                    AlgoVisHelper.setColor(g2d, AlgoVisHelper.Green);

                AlgoVisHelper.fillCircle(g2d, p.x, p.y, 3);
            }
        }

        @Override
        public Dimension getPreferredSize(){
            return new Dimension(canvasWidth, canvasHeight);
        }
    }
}

一个控制器（Controller）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.awt.*;
import java.util.LinkedList;
import javax.swing.*;

public class AlgoVisualizer {

    private static int DELAY = 40;

    private MonteCarloPiData data;
    private AlgoFrame frame;
    private int N;

    public AlgoVisualizer(int sceneWidth, int sceneHeight, int N){

        if(sceneWidth != sceneHeight)
            throw new IllegalArgumentException("This demo must be run in a square window!");

        this.N = N;
        Circle circle = new Circle(sceneWidth/2, sceneHeight/2, sceneWidth/2);
        data = new MonteCarloPiData(circle);

        // 初始化视图
        EventQueue.invokeLater(() -> {
            frame = new AlgoFrame("Monte Carlo", sceneWidth, sceneHeight);

            new Thread(() -> {
                run();
            }).start();
        });
    }

    public void run(){

        for(int i = 0 ; i < N ; i ++){

            if( i % 100 == 0) {
                frame.render(data);
                AlgoVisHelper.pause(DELAY);
                System.out.println(data.estimatePi());
            }

            int x = (int)(Math.random() * frame.getCanvasWidth());
            int y = (int)(Math.random() * frame.getCanvasHeight());
            data.addPoint(new Point(x, y));
        }

    }

    public static void main(String[] args) {

        int sceneWidth = 800;
        int sceneHeight = 800;
        int N = 20000;

        AlgoVisualizer vis = new AlgoVisualizer(sceneWidth, sceneHeight, N);
    }
}

照旧使用了MVC框架，以下是GIF演出。

模拟gif

可视化后，因为加入了刷新屏幕的流程，总体的运算速度会慢一些。（当然可以先记录数据再刷新屏幕，但那需要占用额外的空间）

Tips:

在循环中，判断i % step == 0，以 step作为输出步长（每step次输出一次）。

在屏幕刷新前，进行数据处理的时候，可以在前面加上for循环x次，使得数据处理x次后再刷新屏幕。可以加速数据的处理。

三门问题

“三门问题”也叫“蒙提霍尔问题”(Monty Hall Problem)，是一个有关于博弈论的趣味数学问题。

三门问题的主要内容表述如下：在这个电视节目中有三扇门，这三扇门的后面会被随机的放进去物品，物品分别是汽车和两只山羊，此时参赛者要随机选择一扇门，在参赛者选择了一扇门之后，主持人并不会立刻打开这扇门，为了制造节目紧张悬疑的气氛，支持人会从剩下的两扇门中打开一扇有山羊的那扇门，随后主持人会给竞猜者提供一次重新选择门的机会，此时竞猜者可以保持自己的第一选择不变，也可以更换自己的选择选择另外一扇门，那么参赛者到底是应该换门呢？还是不换门呢？怎么样做得到汽车大奖的概率大一些呢？

不错，我叛逃了java swing，以下结果由unity模拟：

unity模拟三门问题 - 白序的视频 - 知乎