随机模拟问题
2019-06-15 本文已影响0人
茶还是咖啡
该如何面对这个残酷的世界？
房间里有100个人，每个人都有100块钱，他们在玩一个游戏，每轮游戏中，每个人都要拿出一元钱给另一个人，最后这100个人的财富分布是怎样的？
数据控制
public class AssignController extends BaseAlgoVisualizer<Money> {
public AssignController(AlgoFrame frame) {
super(frame);
}
@Override
public void update(Money money) {
//每次在'给钱'之前，先对之前的数据进行排序，使得更加直观的观察结果
Arrays.sort(money.money);
//最外层for循环只是为了加速程序的运行，跟快的看到程序的执行结果
for(int k=0;k<50;k++) {
//模拟随机给钱过程
//遍历数组中的每个元素减少1元，并随机生成一个下标，对该下标下的数字加100
for (int i = 0; i < money.money.length; i++) {
if (money.money[i] > 0) {
int j = (int) (Math.random() * money.money.length);
money.money[i] -= 1;
money.money[j] += 1;
}
}
}
}
@Override
public Money initData() {
//初始化数据
Money money = new Money();
money.money=new int[100];
for(int i=0;i<100;i++){
money.money[i]=100;
}
return money;
}
}
视图层
public class AssignMoney {
public static void main(String[] args) {
//定义生成的窗口大小
int canvasWidth = 1000;
int canvasHeight = 800;
AlgoFrame assignMoney = new AlgoFrame("assign money",canvasWidth,canvasHeight);
assignMoney.paint((Consumer<Money>) (g, money) -> {
AlgoVisHelper.setColor(g,AlgoVisHelper.Blue);
int[] moneyArr = money.money;
int w = canvasWidth/moneyArr.length;
for(int i=0;i<moneyArr.length;i++){
AlgoVisHelper.fillRectangle(g,
i*w+1,
canvasHeight-moneyArr[i],
w-1,moneyArr[i]
);
}
});
AssignController assignController = new AssignController(assignMoney);
}
}
结果展示
image.png
结论
最终的结果是有的人钱很少，有的人钱很多，趋于一个幂指数曲线的样子，而不是每个人的财富都差不多。
其实出现这种结果的原因是改题目相当于将100*100=10000元随机分配给100个人，最终的结果只是所有情况中的一种。
蒙特卡洛算法
蒙特卡洛算法模拟是二战期间，为解决原子弹研制工作中，裂变物质的中子随机扩散问题，美国数学家冯诺依曼和乌拉姆等人提出的一种统计方法，代号：蒙特卡洛
[蒙特卡洛在摩洛哥，是当时特别著名的一个赌城。]
蒙特卡洛原理：通过大量随机样本，去了解一个系统，进而得到所要计算的值。
蒙特卡洛求π值
假设圆的半径为R，正方形边长为2*R
- 圆的面积 = πRR
2.正方形面积 = (2R)*(2R) = 4 *R *R
化简：
π = 4 * 圆面积/正方形面积
是这样，我们是来求π的，所以，现在我们并不知道π是多少，圆的面积自然计算不出来，所以我们可以这样做，
在正方形中打入很多很多的小点我们规定落在圆里面的点是红色的点，落在圆外面的点是绿色的点。，当数量足够多的时候，这些小点便可以覆盖整个正方形，充当正方形的面积。相应的π计算可以转换为点数的计算，即：
π = 4 * 红色点 / 总点数
- 定义圆
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.getX()-x,2)+Math.pow(p.getY()-y,2)<=r*r;
}
}
- Container
public class Contain {
private Circle circle;
private ArrayList<Point> pointList;
public Circle getCircle() {
return circle;
}
public void setCircle(Circle circle) {
this.circle = circle;
}
public ArrayList<Point> getPointList() {
return pointList;
}
public void setPointList(ArrayList<Point> pointList) {
this.pointList = pointList;
}
}
- 数据控制层
public class ComputePiController extends BaseAlgoVisualizer<Contain> {
private int N;
public void setN(int n) {
N = n;
}
public ComputePiController(AlgoFrame frame) {
super(frame);
}
@Override
public void update(Contain contain) {
ArrayList<Point> points = new ArrayList<>();
contain.setPointList(points);
int circleArea = 0;
for(int i=0;i<N;i++){
int x = (int) (Math.random() * getFrame().getCanvasWidth());
int y = (int) (Math.random() * getFrame().getCanvasWidth());
Point point = new Point(x, y);
contain.getPointList().add(point);
AlgoVisHelper.pause(20);
getFrame().render(contain);
int squareArea = points.size();
if(contain.getCircle().contain(point)){
circleArea++;
}
double pi = 4*(double)circleArea/squareArea;
System.out.println(pi);
}
}
@Override
public Contain initData() {
Contain contain = new Contain();
int width = super.getFrame().getCanvasWidth();
Circle circle = new Circle(width / 2, width / 2, width / 2);
contain.setCircle(circle);
return contain;
}
}
- 视图层
public class MtklView {
public static void main(String[] args) {
AlgoFrame<Contain> pi = new AlgoFrame<>("Pi", 500, 500);
pi.paint((g, contain) -> {
AlgoVisHelper.setStrokeWidth(g,3);
AlgoVisHelper.setColor(g,AlgoVisHelper.Blue);
AlgoVisHelper.strokeCircle(g,contain.getCircle().getX(),contain.getCircle().getY(),contain.getCircle().getR());
ArrayList<Point> pointList = contain.getPointList();
for(int i = 0 ; i < pointList.size() ; i ++){
Point p = pointList.get(i);
if(contain.getCircle().contain(p)){
AlgoVisHelper.setColor(g,AlgoVisHelper.Red);
}else{
AlgoVisHelper.setColor(g,AlgoVisHelper.Green);
}
AlgoVisHelper.fillCircle(g,p.x,p.y,3);
}
});
ComputePiController piController = new ComputePiController(pi);
piController.setN(10000);
piController.setAlways(false);
}
}
演示效果：
image.png
控制台计算的π值：
3.1253555850559454
3.1247629882442167
3.124170616113744
3.1243366186504926
3.1245025582717454
三门问题
参赛者会看见三扇关闭了的门，其中一扇后面有一辆汽车，选中后面有车的门就可以赢得该汽车，而另外两扇门后面则什么也没有，当参赛者选定一扇门，但是开启的时候，节目主持人会先开启剩下两扇门中的一扇，这扇门后面肯定没有汽车，主持人会问参赛者要不要更换另一扇门。
问题是：换另外一扇门是否会增加参赛者的获奖概率？
public class ThreeGatesExperiment {
private int N;
public ThreeGatesExperiment(int N){
if(N<=0){
throw new IllegalArgumentException("N must be large than 0!");
}
this.N = N;
}
/**
* 计算完N次的胜率
* @param changeDoor 参赛者的选择true不换
*/
public void run(boolean changeDoor){
int wins = 0;
for(int i = 0;i<N;i++){
if(play(changeDoor)){
wins++;
}
}
System.out.println(changeDoor?"change":"not Change");
System.out.println("wins rate:"+(double)wins/N);
}
/**
* 玩一次的结果
* @param changeDoor 参赛者的选择true不换
* @return 赢了true
*/
private boolean play(boolean changeDoor){
// Door 0,1,2
int prizeDoor = (int)(Math.random()*3);
int playerChoice = (int)(Math.random()*3);
if(playerChoice==prizeDoor){
return !changeDoor;
}else {
return changeDoor;
}
}
public static void main(String[] args){
ThreeGatesExperiment threeGatesExperiment = new ThreeGatesExperiment(10000000);
//换门
threeGatesExperiment.run(true);
// 不换门
threeGatesExperiment.run(false);
}
}
打印结果：
change
wins rate:0.6667866
not Change
wins rate:0.3331784
咋回事呢？解释一哈~
假设三扇门编号分别为1,2,3
- 最初情况下三扇门的中奖概率都是1/3
- 假设参赛者选择1号门，则一号门的中奖概率为1/3,2号门+3号门合起来中奖概率为2/3
- 假设主持人开启了2号门，那么2号门的中奖概率为0，所以3号门的中奖概率为2/3
代码已托管到github传送门
