问题出自:
http://topic.csdn.net/u/20090518/21/8b96f19a-af92-4eb8-8021-2977c29f27d2.html#replyachor
http://topic.csdn.net/u/20090524/15/485d92e2-759e-496c-8725-fab7862ab5d2.html
但在这里对题目作了修改,增加了些难度。
--
r个红球和b个蓝球。
A,B轮流取球:A每次从箱子里随机取出一个球,B每次从箱子里取出一个蓝球。
当如下两种情况之一发生时A胜:
(1),最后一个取出的球是蓝球。
(2),剩余的红球比蓝球恰多两个。
否则B胜。
问:若给定r,b值及A,B谁先取,求A获胜的概率。
解:(matlab代码)
(一)递归解法:
function rs=g(r,b,guy)
%计算“有r个红球,b个蓝球,guy先取”时A获胜的概率 if guy=='A' if r-2==b rs=1; return; end if r==0&&b==0 rs=0; return; end if r==0&&b>=1 rs=1; return; end if r>=1&&b==0 rs=0; return; end if r>=1&&b>=1 rs=g(r-1,b,'B').*r./(r+b)+g(r,b-1,'B').*b./(r+b); return; end elseif guy=='B' if r-2==b rs=1; return; end if r==0&&b==0 rs=0; return; end if r==0&&b>=1 rs=1; return; end if r>=1&&b==0 rs=0; return; end if b>=1&&r>=1 rs=g(r, b-1,'A'); return; end end end |
例:
>> g(3,10,'A')
ans =
0.4386
(二)动态规划解法:
将A,B轮流取球的过程看作离散随机过程(马尔可夫链)。
function rsp=f(r,b,guy) %计算“有r个红球,b个蓝球,guy先取”时A获胜的概率 %最初状态空间p只有(i_(r),j_(b))格有概率值(为1),其余格均为0 |
其中用到两个辅助函数,作用是将下标从1开始(matlab特性)变换为下标从0开始:
function newivalu=i_(ivalu)
newivalu=ivalu+1; end function newivalu=j_(ivalu) newivalu=ivalu+1; end |
例:
>> f(3,10,'A')
ans =
0.4386
(三),模拟解法:
function rs=f(Nr,Nb,firstguy,rep) %模拟计算“有Nr个红球,Nb个蓝球,firstguy先取”时A获胜的概率,rep为实验次数 %如果输入为特殊情况,则直接得出结果,无需模拟 if Nr==0&&Nb==0 rs=0; return; end if Nr-2==Nb rs=1; return; end if Nr==0&&Nb>0 rs=1; return; end if Nr>0&&Nb==0&&~(Nr-2==Nb) rs=0; return; end %进行模拟 NAwin=0;%A胜次数 for i=1:rep%重复游戏rep次 %游戏初始状态 r=Nr; b=Nb; guy=firstguy; %A,B轮流取球 while(1) if guy=='A'%轮到A取球 k=floor(rand()*(r+b))+1;%随机数k用于选球 if k>r%取蓝球 b=b-1; if r==0&&b==0%如果A刚取的这个蓝球为最后一个球,游戏结束,A胜。 NAwin=NAwin+1; break; end else%取红球 r=r-1; if r==0&&b==0%如果A刚取的这个红球为最后一个球,游戏结束,B胜。 break; end end if r-2==b%如果满足条件(2),游戏结束,A胜。 NAwin=NAwin+1; break; end guy='B';%换人 elseif guy=='B'%轮到B取球 b=b-1;%B只取蓝球 if r==0&&b==0%如果B刚取的这个蓝球为最后一个球,游戏结束,A胜。 NAwin=NAwin+1; break; end if r-2==b%如果满足条件(2),游戏结束,A胜。 NAwin=NAwin+1; break; end guy='A';%换人 end end end rs=NAwin./rep;%得到概率 end |
例:
>> f(3,10,'A',100000)
ans =
0.4383