(算法)宝石升级问题
算法 升级 问题 宝石
2023-09-14 09:00:36 时间
题目:
有一块宝石,1级升2级成功率100%,2级升3级成功率80%,3级升4级成功率60%,4级升5级成功率40%,每次升级失败时降回到1级。请问一块1级宝石升到5级平均要多少次?
思路:
问题:求一块1级宝石升级到5级的期望次数
1、蒙特卡洛模拟试验
考虑一下期望的定义,所有的可能的次数*出现该次数的概率之和。出现的次数可能为无穷大,但当次数达到一定数量时,期望就收敛了,因此可以通过概率的模拟试验来实现。
2、有限状态机的概率转移思想
假设dp(i,j)为1级升到5级的平均次数,则有以下递推式:
dp(1,5) = 1.0 * dp(2,5) + 0.0 * dp(1,5)+1
dp(2,5) = 0.8 * dp(3,5) + 0.2 * dp(1,5)+1
dp(3,5) = 0.6 * dp(4,5)+ 0.4 * dp(1,5)+1
dp(4,5) = 0.4 * dp(5,5) + 0.6 * dp(1,5)+1
其中dp(5,5)=0;
求解上述方程组,得到dp(1,5)即为答案,答案为17.0833.
代码:
1、蒙特卡洛模拟试验
#include <iostream> #include <time.h> #include <stdlib.h> #include <iomanip> using namespace std; bool isUpgrade(double p){ double prob=rand()/(double)(RAND_MAX); if(prob<=p) return true; else return false; } double ExpectedUpgradeTimes(double *P,int n){ const int TIMES=100000000; int grade=0; int times=0; int total=0; double expect=0; for(int i=0;i<TIMES;i++){ grade=0; times=0; while(grade!=n-1){ if(isUpgrade(P[grade])) grade++; else grade=0; times++; } total+=times; } expect=(double)total/TIMES; return expect; } int main(){ srand((unsigned int)time(NULL)); double P[]={1.0,0.8,0.6,0.4}; int len=sizeof(P)/sizeof(P[0]); double exp=ExpectedUpgradeTimes(P,len+1); cout<<fixed<<exp<<endl; cout << setprecision(2) << exp << endl; return 0; }
2、动态规划
#include <iostream> #include <time.h> #include <stdlib.h> #include <iomanip> using namespace std; double ExpectedUpgradeTimes_DP(double *P,int n){ double A[n],B[n]; double p[n]; p[1] = 1.0;p[2] = 0.8;p[3]=0.6;p[4] =0.4; for(int i=4;i>=1;i--){ A[i] = 1+A[i+1]*p[i]; B[i] = p[i]*B[i+1]+1-p[i]; cout<<A[i]<<" "<<B[i]<<endl; } double t = A[1]/(1-B[1]); return t; } int main(){ srand((unsigned int)time(NULL)); double P[]={1.0,0.8,0.6,0.4}; int len=sizeof(P)/sizeof(P[0]); double exp=ExpectedUpgradeTimes_DP(P,len+1); cout<<fixed<<exp<<endl; cout << setprecision(2) << exp << endl; return 0; }
相关文章
- 文本分类常用算法比较
- Java数组常用算法
- 怎么算图中有多少个三角形_贪心算法经典例题
- 利用高精度拼接算法实现长柱形物体检测
- 图像去色算法_matlab去雾算法
- 算法初学者的第一个数据结构,数组和vector
- 算法错题本
- 数据结构与算法
- 想抓住 AI 绘画风口?绝不能错过的重大算法库升级!
- 使用python的随机森林算法处理遥感数据
- 134个预训练模型、精度高达85.1%,百度视觉算法最强基石PaddleClas全新升级
- 算法-把字符串转换成整数详解编程语言
- Python 算法(2) 哈夫曼编码 Huffman Encoding详解编程语言
- 零钱兑换算法详解编程语言
- 深入浅出:Redis 集群算法(redis集群算法)
- C++实现查找中位数的O(N)算法和Kmin算法