(算法)跳格子
算法 格子
2023-09-14 08:59:06 时间
题目:
有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<iostream> #include<stdlib.h> #include<time.h> #include<string.h> using namespace std; bool rndJump(double p){ double prob=rand()/(double)RAND_MAX; if(prob<=p) return true; else return false; } // MonteCarlo Simulation double ExpectedSteps(){ const int MAX_TRY=100000000; double expected=0; int total=0; int times=0; int steps=0; for(int i=0;i<MAX_TRY;i++){ times=0; steps=1; while(steps%4!=0){ if(rndJump(0.5)) steps+=1; else steps+=2; times++; } total+=times; } expected=(double)total/MAX_TRY; return expected; } // DynamicProgramming-like // f(1,4)=1+0.5*f(2,4)+0.5*f(3,4); // f(2,4)=1+0.5*f(3,4)+0.5*f(4,4); // f(3,4)=1+0.5*f(4,4)+0.5*f(1,4); // f(4,4)=0; double ExpectedSteps_DP(int n){ double A[n],B[n]; memset(A,0,n*sizeof(double)); memset(B,0,n*sizeof(double)); A[3]=0; B[3]=0; A[2]=1+0.5*A[3]; B[2]=0.5; A[1]=1+0.5*A[2]+0.5*A[3]; B[1]=0.5*B[2]+0.5*B[3]; A[0]=1+0.5*A[1]+0.5*A[2]; B[0]=0.5*B[1]+0.5*B[2]; return (double)A[0]/(1-B[0]); } int main(){ cout<< ExpectedSteps()<<endl; cout<< ExpectedSteps_DP(4)<<endl; return 0; }
相关文章
- 快速排序算法详细图解JAVA_实现快速排序
- Unity SKFramework框架(二十五)、RSA算法加密、签名工具 RSA Crypto
- 【算法竞赛 - 数据结构】Cube Stacking(并查集+树型前缀和)
- 【JavaScript——牛客网算法No.HJ2】计算一个字符串中含有某个字符的个数[通俗易懂]
- 路径匹配之单向距离OWD算法
- KMP算法详解
- React面试:谈谈虚拟DOM,Diff算法与Key机制5
- 数据结构和算法指南
- 算法练习之环形链表详解编程语言
- 美国西北大学联合AI创企Eko,推出心脏杂音AI筛查算法
- Oracle中玩转运算函数,轻松完成高效算法(oracle中运算函数)
- 深入理解PHP几个算法:PHP冒泡、PHP二分法、PHP求素数、PHP乘法表
- 关于PHP二进制流逐bit的低位在前算法(详解)