首页 > 代码库 > 用蒙特卡罗方法计算五人传球问题
用蒙特卡罗方法计算五人传球问题
蒙特卡罗方法百度解释http://baike.baidu.com/link?url=XwVnK6P_gip61_P9RzC9u6T4KQP5hmoZIvx57XBM66hPBONRRl3-yAwldGr3orFe
问题描述：
有A B C D E 五个人，围成一圈，开始球在A的手上，然后由A向与自己相邻的两边的某一人传球，然后要求计算球被传十次，最后又回到A手中的概率。
如上图所示，A只能把球传给B或者E,其几率是相同的。
对每个人来说把球传给左边或者右边的人的几率都是相同的，且为1/2；
这样我们便可以用这样的公式来计算出最后的结果：
分母是指每轮传球每个人都有两种传球可能性
分子中的2是指可以通过传球沿着一个顺序转两圈的方式，使球到达A的手中；
后面的组合公式是指每轮传十次球，必须做到五次是传给右边的人，五次传给左边的人，才能最终到达A的手中。这样做出来的结果是254/1024=0.248;
然后回到我们的重点上来，如何能够用蒙特卡罗方法解决这个题目。
首先要建立模型，即要模仿真人传球的过程。
每一次传球的时候都看做是随机的，那么让机器产生一个随机数，根据随机数的大小来分配球传递的方向，这样便可以解决随机性问题，
然后在充分多的数量之后便可以根据能够到达A的次数总和L除以总数N,求出概率。这里的N 取1000000次就可以，对计算机来说，1000000次也是很快就做完的。
具体实现代码如下：
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<ctime> 5 //利用蒙特卡罗方法 6 //目的：计算 p=L/N; 7 //L: 球回到A手中的次数 8 //N: 充分多的次数，这里取值1000000 9 // A-B-C-D-E-A,从A开始 10 using namespace std;11 int factory(); //每轮传十次球的模仿过程 12 int main()13 {14 srand(time(NULL));//用时间做种子 15 int count=0;//记录回到A的数量 16 for(int i=0;i<1000000;i++)//循环1000000次 17 {18 count+=factory();19 }20 double rate=1.0*count/1000000.0;21 cout<<"rate= "<<rate<<endl;22 return 0;23 } 24 int factory()25 {26 //建立五元数组，模仿五个人，27 //每次让球所在的位置为1，其余为零 28 int test[5]={1,0,0,0,0};//test[0]代表A 29 int q=0;30 for(int i=0;i<10;i++)31 {32 q=rand()%10+1;//生成1-10的随机数33 //q<=5 go left34 //q>5 go right 35 for(int j=0;j<5;j++)36 {37 if(test[j]==1)//the ball current place 38 {39 if(q<=5)40 {41 if(j==0)test[4]=1,test[0]=0;42 else test[j]=0,test[j-1]=1;43 }44 else45 {46 if(j==4)test[0]=1,test[4]=0;47 else test[j]=0,test[j+1]=1;48 }49 break;50 }51 } 52 }53 if(test[0]==1)return 1;//最终回到A返回1 54 return 0; 55 }
通过代码实现，结果也约等于0.248，说明通过蒙特卡罗方法计算出来的数据为真。
在很多难以用简单公式计算的时候可以采用蒙特卡罗算法计算。
用蒙特卡罗方法计算五人传球问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。