[算法] 随机模拟问题

分钱问题

100个人，初始每人100块钱，每轮每人将1元随机分给另一个人，若干轮过后，100个人的财富分布情况会怎样
画布的原点在左上角，y轴向下

AlgoVisHelper.java

 1 import java.awt.EventQueue;
 2 import java.util.Arrays;
 3 
 4 public class AlgoVisualizer {
 5     
 6     private static int DELAY = 40;
 7     private int[] money;
 8     private AlgoFrame frame;
 9     
10     public AlgoVisualizer(int sceneWidth, int sceneHeight) {
11         
12         // 初始化数据
13         money = new int[100];
14         for(int i = 0 ; i < money.length ; i ++) {
15             money[i] = 100;
16         }
17         
18         // 初始化视图
19         EventQueue.invokeLater(()->{
20             frame = new AlgoFrame("Welcome",sceneWidth,sceneHeight);
21             new Thread(()->{
22                     run();
23             }).start();  
24         });
25     }
26     
27     private void run() {
28         while(true) {
29             Arrays.sort(money);
30             frame.render(money);
31             AlgoVisHelper.pause(DELAY);
32             
33             for(int k = 0 ; k < 50 ; k ++ ) {
34                 for(int i = 0 ; i < money.length ; i ++ ) {
35                         int j = (int)(Math.random() * money.length);
36                         money[i] -= 1;
37                         money[j] += 1;
38                 }
39             }
40         }
41     }
42     
43     public static void main(String[] args) {
44         
45         int sceneWidth = 1000;
46         int sceneHeight = 800;
47         
48         AlgoVisualizer visualizer = new AlgoVisualizer(sceneWidth, sceneHeight);
49         
50     }
51 }

View Code

AlgoVisualizer.java

 1 import java.awt.EventQueue;
 2 import java.util.Arrays;
 3 
 4 public class AlgoVisualizer {
 5     
 6     private static int DELAY = 40;
 7     private int[] money;
 8     private AlgoFrame frame;
 9     
10     public AlgoVisualizer(int sceneWidth, int sceneHeight) {
11         
12         // 初始化数据
13         money = new int[100];
14         for(int i = 0 ; i < money.length ; i ++) {
15             money[i] = 100;
16         }
17         
18         // 初始化视图
19         EventQueue.invokeLater(()->{
20             frame = new AlgoFrame("Welcome",sceneWidth,sceneHeight);
21             new Thread(()->{
22                     run();
23             }).start();  
24         });
25     }
26     
27     private void run() {
28         while(true) {
29             Arrays.sort(money);
30             frame.render(money);
31             AlgoVisHelper.pause(DELAY);
32             
33             for(int k = 0 ; k < 50 ; k ++ ) {
34                 for(int i = 0 ; i < money.length ; i ++ ) {
35                         int j = (int)(Math.random() * money.length);
36                         money[i] -= 1;
37                         money[j] += 1;
38                 }
39             }
40         }
41     }
42     
43     public static void main(String[] args) {
44         
45         int sceneWidth = 1000;
46         int sceneHeight = 800;
47         
48         AlgoVisualizer visualizer = new AlgoVisualizer(sceneWidth, sceneHeight);
49         
50     }
51 }

View Code

AlgoFrame.java

 1 import java.awt.Color;
 2 import java.awt.Dimension;
 3 import java.awt.Graphics;
 4 import java.awt.Graphics2D;
 5 import java.awt.RenderingHints;
 6 
 7 import javax.swing.JFrame;
 8 import javax.swing.JPanel;
 9 
10 public class AlgoFrame extends JFrame{
11     
12     private int canvasWidth;
13     private int canvasHeight;
14     
15     public AlgoFrame(String title, int canvasWidth, int canvasHeight) {
16         
17         super(title);
18         
19         this.canvasWidth = canvasWidth;
20         this.canvasHeight = canvasHeight;
21         
22         AlgoCanvas canvas = new AlgoCanvas();
23         setContentPane(canvas);
24         pack();
25         
26         setResizable(false);
27         setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
28         setVisible(true);
29     }
30     
31     public AlgoFrame(String title) {
32         this(title, 1024, 768);
33     }
34     
35     public int getCanvasWidth() {return canvasWidth;}
36     public int getCanvasHeight() {return canvasHeight;}
37 
38     private int[] money;
39     public void render(int[] money) {
40         this.money = money;
41         repaint();
42     }
43     
44     private class AlgoCanvas extends JPanel{
45         
46         public AlgoCanvas() {
47             super(true);
48         }
49         
50         @Override
51         public void paintComponent(Graphics g) {
52             
53             super.paintComponent(g);
54             
55             Graphics2D g2d = (Graphics2D)g;
56             
57             //抗锯齿
58             RenderingHints hints = new RenderingHints(
59                             RenderingHints.KEY_ANTIALIASING, 
60                             RenderingHints.VALUE_ANTIALIAS_ON);
61             g2d.addRenderingHints(hints);
62             
63             //具体绘制
64             int w = canvasWidth / money.length;
65             for(int i = 0 ; i < money.length ; i ++ ) {
66                 if(money[i] > 0) {
67                     AlgoVisHelper.setColor(g2d, AlgoVisHelper.Blue);
68                     AlgoVisHelper.fillRectangle(g2d, 
69                             i*w + 1, canvasHeight/2 - money[i], w-1, money[i]);
70                 }
71                 else if(money[i] < 0) {
72                     AlgoVisHelper.setColor(g2d, AlgoVisHelper.Red);
73                     AlgoVisHelper.fillRectangle(g2d,
74                             i*w + 1, canvasHeight/2, w-1, -money[i]);
75                 }
76             }
77         }
78         
79         @Override
80         public Dimension getPreferredSize() {
81             return new Dimension(canvasWidth, canvasHeight);
82         }
83     }
84 }

View Code

蒙特卡洛方法

为解决裂变物质的中子随机扩散问题而提出
通过大量随机样本，了解一个系统，进而得到所要计算的值
红色点的数量-->圆的面积；红色点+绿色点的数量-->方的面积
PI = 4 * 红色点数 / 总点数

AlgoFrame.java

 1 import java.awt.Color;
 2 import java.awt.Dimension;
 3 import java.awt.Graphics;
 4 import java.awt.Graphics2D;
 5 import java.awt.Point;
 6 import java.awt.RenderingHints;
 7 import java.util.LinkedList;
 8 
 9 import javax.swing.JFrame;
10 import javax.swing.JPanel;
11 
12 public class AlgoFrame extends JFrame{
13     private int canvasWidth;
14     private int canvasHeight;
15     
16     public AlgoFrame(String title, int canvasWidth, int canvasHeight) {
17         super(title);
18         
19         this.canvasWidth = canvasWidth;
20         this.canvasHeight = canvasHeight;
21         
22         AlgoCanvas canvas = new AlgoCanvas();
23         setContentPane(canvas);
24         pack();
25         
26         setResizable(false);
27         setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
28         setVisible(true);
29     }
30     
31     public AlgoFrame(String title) {
32         this(title, 1024, 768);
33     }
34     
35     public int getCanvasWidth() {return canvasWidth;}
36     public int getCanvasHeight() {return canvasHeight;}
37 
38     private MonteCarloPiaData data;
39     public void render(MonteCarloPiaData data) {
40         this.data = data;
41         repaint();
42     }
43     
44     private class AlgoCanvas extends JPanel{
45         
46         public AlgoCanvas() {
47             super(true);
48         }
49         
50         @Override
51         public void paintComponent(Graphics g) {
52             
53             super.paintComponent(g);
54             
55             Graphics2D g2d = (Graphics2D)g;
56             
57             //抗锯齿
58             RenderingHints hints = new RenderingHints(
59                                         RenderingHints.KEY_ANTIALIASING, 
60                                         RenderingHints.VALUE_ANTIALIAS_ON);
61             g2d.addRenderingHints(hints);
62             
63             //具体绘制
64             Circle circle = data.getCircle();
65             AlgoVisHelper.setStrokeWidth(g2d, 3);
66             AlgoVisHelper.setColor(g2d, AlgoVisHelper.Blue);
67             AlgoVisHelper.strokeCircle(g2d, circle.getX(), circle.getY(), circle.getR());
68             
69             for(int i = 0 ; i < data.getPointsNumber() ; i ++ ) {
70                 Point p = data.getPoint(i);
71                 if(circle.contain(p))
72                     AlgoVisHelper.setColor(g2d, AlgoVisHelper.Red);
73                 else
74                     AlgoVisHelper.setColor(g2d, AlgoVisHelper.Green);
75                 AlgoVisHelper.fillCircle(g2d, p.x, p.y, 3);
76             }
77         }
78         
79         @Override
80         public Dimension getPreferredSize() {
81             return new Dimension(canvasWidth, canvasHeight);
82         }
83     }
84 }

View Code

AlgoVisualizer.java

 1 import java.awt.EventQueue;
 2 import java.awt.Point;
 3 import java.util.LinkedList;
 4 
 5 public class AlgoVisualizer {
 6     
 7     private static int DELAY = 40;
 8     
 9     private MonteCarloPiaData data;
10     private AlgoFrame frame;
11     private int N;
12     
13     public AlgoVisualizer(int sceneWidth, int sceneHeight, int N) {
14         
15         if(sceneWidth != sceneHeight)
16             throw new IllegalArgumentException("This demo must be run in a square");
17         // 初始化数据
18         this.N = N;
19         Circle circle = new Circle(sceneWidth/2, sceneHeight/2, sceneWidth/2);
20         data = new MonteCarloPiaData(circle);
21         
22         // 初始化视图
23         EventQueue.invokeLater(()->{
24             frame = new AlgoFrame("Get Pi with Monte Carlo",sceneWidth,sceneHeight);
25             new Thread(()->{
26                     run();
27             }).start();  
28         });
29     }
30     
31     // 动画逻辑
32     private void run() {
33         for(int i = 0 ; i < N ; i ++ ) {
34             
35             if(i % 100 == 0) {
36                 frame.render(data);
37                 AlgoVisHelper.pause(DELAY);
38                 System.out.println(data.estimatePi());
39             }
40             
41             int x = (int)(Math.random() * frame.getCanvasWidth());
42             int y = (int)(Math.random() * frame.getCanvasHeight());
43             data.addPoint(new Point(x,y));
44         }
45     }
46     
47     public static void main(String[] args) {
48         
49         int sceneWidth = 800;
50         int sceneHeight = 800;
51         int N = 10000;
52         
53         AlgoVisualizer visualizer = new AlgoVisualizer(sceneWidth, sceneHeight, N);
54     }
55 }

View Code

AlgoVisHelper.java

 1 import java.awt.BasicStroke;
 2 import java.awt.Color;
 3 import java.awt.Graphics2D;
 4 import java.awt.geom.Ellipse2D;
 5 
 6 public class AlgoVisHelper {
 7     public AlgoVisHelper() {}
 8     
 9     public static final Color Red = new Color(0xF44336);
10     public static final Color Pink = new Color(0xE91E63);
11     public static final Color Purple = new Color(0x9C27B0);
12     public static final Color DeepPurple = new Color(0x673AB7);
13     public static final Color Indigo = new Color(0x3F51B5);
14     public static final Color Blue = new Color(0x2196F3);
15     public static final Color LightBlue = new Color(0x03A9F4);
16     public static final Color Cyan = new Color(0x00BCD4);
17     public static final Color Teal = new Color(0x009688);
18     public static final Color Green = new Color(0x4CAF50);
19     public static final Color LightGreen = new Color(0x8BC34A);
20     public static final Color Lime = new Color(0xCDDC39);
21     public static final Color Yellow = new Color(0xFFEB3B);
22     public static final Color Amber = new Color(0xFFC107);
23     public static final Color Orange = new Color(0xFF9800);
24     public static final Color DeepOrange = new Color(0xFF5722);
25     public static final Color Brown = new Color(0x795548);
26     public static final Color Grey = new Color(0x9E9E9E);
27     public static final Color BlueGrey = new Color(0x607D8B);
28     public static final Color Black = new Color(0x000000);
29     public static final Color White = new Color(0xFFFFFF);
30     
31     public static void setStrokeWidth(Graphics2D g2d, int w) {
32         int strokeWidth = w;
33         g2d.setStroke(new BasicStroke(strokeWidth, BasicStroke.CAP_ROUND,BasicStroke.JOIN_ROUND));
34     }
35     public static void setColor(Graphics2D g2d, Color color) {
36         g2d.setColor(color);
37     }
38     public static void strokeCircle(Graphics2D g2d, int x, int y, int r) {
39         Ellipse2D circle = new Ellipse2D.Double(x-r, y-r, 2*r, 2*r);
40         g2d.draw(circle);
41     }
42     public static void fillCircle(Graphics2D g2d, int x, int y, int r) {
43         Ellipse2D circle = new Ellipse2D.Double(x-r, y-r, 2*r, 2*r);
44         g2d.fill(circle);
45     }
46     public static void pause(int t) {
47         try {
48             Thread.sleep(t);
49         }
50         catch(InterruptedException e) {
51             System.out.println("Error in sleeping.");
52         }
53     }
54 }

View Code

Circle.java

 1 import java.awt.Point;
 2 
 3 public class Circle {
 4     
 5     public int x, y, r;
 6     
 7     public Circle(int x, int y, int r ) {
 8         this.x = x;
 9         this.y = y;
10         this.r = r;
11     }
12     
13     public int getX() { return x; }
14     public int getY() { return y; }
15     public int getR() { return r; }
16     
17     public boolean contain(Point p) {
18         return Math.pow(p.getX() - x, 2) + Math.pow(p.getY() - y, 2) <= r*r;
19     }
20 }

View Code

MonteCarloPiaData.java

 1 import java.awt.Point;
 2 import java.util.LinkedList;
 3 
 4 public class MonteCarloPiaData {
 5     
 6     private Circle circle;
 7     private int insideCircle = 0;
 8     private LinkedList<Point> points;
 9     
10     public MonteCarloPiaData(Circle circle) {
11         this.circle = circle;
12         points = new LinkedList<Point>();
13     }
14     
15     public Circle getCircle() {
16         return circle;
17     }
18     
19     public Point getPoint(int i) {
20         if(i < 0 || i >= points.size())
21             throw new IllegalArgumentException("out of bound in getPoint!");
22         return points.get(i);
23     }
24     
25     public int getPointsNumber() {
26         return points.size();
27     }
28     
29     public void addPoint(Point p) {
30         points.add(p);
31         if(circle.contain(p))
32             insideCircle ++;
33     }
34     
35     public double estimatePi() {
36         if(points.size() == 0)
37             return 0.0;
38         int circleArea = insideCircle;
39         int squareArea = points.size();
40         return (double)circleArea*4 / squareArea;
41     }
42 }

View Code

控制台演示

MonteCarloExperiment.java

 1 import java.awt.*;
 2 
 3 public class MonteCarloExperiment {
 4     
 5     private int squareSide;
 6     private int N;
 7     private int outputInterval = 100;
 8     
 9     public MonteCarloExperiment(int squareSide, int N) {
10         if(squareSide <= 0 || N <= 0)
11             throw new IllegalArgumentException("squareSide and N must larger than 0");
12         this.squareSide = squareSide;
13         this.N = N;
14     }
15     
16     public void setOutputInterval(int interval) {
17         if(interval <= 0)
18             throw new IllegalArgumentException("interval must be larger than 0");
19         this.outputInterval = interval;
20     }
21     
22     public void run() {
23         
24         Circle circle = new Circle(squareSide/2, squareSide/2, squareSide/2);
25         MonteCarloPiData data = new MonteCarloPiData(circle);
26         
27         for(int i = 0 ; i < N ; i ++) {
28             if( i % outputInterval == 0 )
29                 System.out.println(data.estimatePi());
30             int x = (int)(Math.random() * squareSide);
31             int y = (int)(Math.random() * squareSide);
32             data.addPoint(new Point(x,y));
33         }
34     }
35     
36     public static void main(String[] args) {
37         
38         int squareSide = 800;
39         int N = 1000000;
40         
41         MonteCarloExperiment exp = new MonteCarloExperiment(squareSide, N);
42         exp.setOutputInterval(10000);
43         exp.run();
44     }
45 }

View Code

三门问题

有三扇门，其中一扇门后面有汽车，两扇后面没东西
当参赛者选定一扇门但未开启时，主持人会开启剩下两扇门中的一扇，这扇门后面一定没有汽车
如果参赛者现在换另一个门，会不会提高中奖概率？
换门中奖率2/3，不换门中奖率1/3
在计算机中模拟，看最后收敛到的结果

ThreeGateExperiment.java

 1 public class ThreeGatesExperiment {
 2 
 3     private int N;
 4 
 5     public ThreeGatesExperiment(int N){
 6 
 7         if(N <= 0)
 8             throw new IllegalArgumentException("N must be larger than 0!");
 9 
10         this.N = N;
11     }
12 
13     public void run(boolean changeDoor){
14 
15         int wins = 0;
16         for(int i = 0 ; i < N ; i ++)
17             if(play(changeDoor))
18                 wins ++;
19 
20         System.out.println(changeDoor ? "Change" : "Not Change");
21         System.out.println("winning rate: " + (double)wins/N);
22     }
23 
24     private boolean play(boolean changeDoor){
25 
26         // Door 0, 1, 2
27         int prizeDoor = (int)(Math.random() * 3);
28         int playerChoice = (int)(Math.random() * 3);
29 
30         if( playerChoice == prizeDoor)
31             return changeDoor ? false : true;
32         else
33             return changeDoor ? true : false;
34     }
35 
36     public static void main(String[] args) {
37 
38         int N = 1000;
39         ThreeGatesExperiment exp = new ThreeGatesExperiment(N);
40 
41         exp.run(true);
42         System.out.println();
43         exp.run(false);
44     }
45 }

View Code

你会不会中奖

游戏中有一种宝箱，打开宝箱获得传奇武器的概率是20%
打开5个这样的宝箱，获得传奇武器的概率是多少？

WinningPrize.java

 1 public class WinningPrize {
 2 
 3     private double chance;
 4     private int playTime;
 5     private int N;
 6 
 7     public WinningPrize(double chance, int playTime, int N){
 8 
 9         if(chance < 0.0 || chance > 1.0)
10             throw new IllegalArgumentException("chance must be between 0 and 1!");
11 
12         if(playTime <= 0 || N <= 0)
13             throw new IllegalArgumentException("playTime or N must be larger than 0!");
14 
15         this.chance = chance;
16         this.playTime = playTime;
17         this.N = N;
18     }
19 
20     public void run(){
21 
22         int wins = 0;
23         for(int i = 0 ; i < N ; i ++)
24             if(play())
25                 wins ++;
26 
27         System.out.println("winning rate: " + (double)wins/N);
28     }
29 
30     private boolean play(){
31         for(int i = 0 ; i < playTime ; i ++)
32             if(Math.random() < chance)
33                 return true;
34         return false;
35     }
36 
37     public static void main(String[] args) {
38 
39         double chance = 0.2;
40         int playTime = 5;
41         int N = 1000000;
42 
43         WinningPrize exp = new WinningPrize(chance, playTime, N);
44         exp.run();
45     }
46 }

View Code