题目：

有1,2,3,......无穷个格子，你从1号格子出发，每次1/2概率向前跳一格，1/2概率向前跳两格，走到格子编号为4的倍数时结束，结束时期望走的步数为____。

思路：

1、MonteCarlo模拟实验

参考代码

2、有限状态机的概率转移思想

跳一格跳两格都算一步；

dp(i,j)表示从格子i到格子j的期望步数：

dp(1,4)=1+0.5*dp(2,4)+0.5*dp(3,4)；

dp(2,4)=1+0.5*dp(3,4)+0.5*dp(4,4);

dp(3,4)=1+0.5*dp(4,4)+0.5*dp(1,4);

dp(4,4)=0;

求解上述方程得到dp(1,4)=18/5;

代码：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;bool rndJump(double p){	double prob=rand()/(double)RAND_MAX;	if(prob<=p)		return true;	else		return false;}// MonteCarlo Simulationdouble ExpectedSteps(){	const int MAX_TRY=100000000;	double expected=0;	int total=0;	int times=0;	int steps=0;	for(int i=0;i