Description

給定一個(gè)數(shù)a0, 并給出定義:序列a1,a2,a3…

1.從閉區(qū)間[0,a0]中等概率隨機(jī)選擇一個(gè)整數(shù)k0,令a1=a0-k0

2.得到隨機(jī)數(shù)a1后，再?gòu)拈]區(qū)間[0,a1]中等概率隨機(jī)選擇一個(gè)整數(shù)k1,令a2=a1-k1

3.一般地，得到隨機(jī)數(shù)ai后，再?gòu)拈]區(qū)間[0,ai]中等概率隨機(jī)選擇一個(gè)整數(shù)ki,令a(i+1) = ai- ki

問經(jīng)過(guò)n步后，an==0的概率是多少呢？

Input
輸入兩個(gè)正整數(shù)n,a0

(1<=n,a0<=100)

Output
輸出概率，小數(shù)點(diǎn)后四舍五入保留5位小數(shù)

Sample Input 1

3 3
Sample Output 1

0.72049
思路：dp[x][y]代表第x層選擇y得到0的概率。然后記憶化就可以了。具體看代碼：
提交鏈接
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e2+10; double dp[maxx][maxx]; int n,m;inline double dfs(int x,int y) {if(dp[x][y]!=-1.0) return dp[x][y];if(x<0) return 0.0;if(y==0) return dp[x][y]=1.0;double sum=0.0;for(int i=0;i<=y;i++) {double num=dfs(x-1,y-i)/(double)(y+1);sum+=num;}return dp[x][y]=sum; } int main() {scanf("%d%d",&n,&m);for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) dp[i][j]=-1.0;printf("%.5lf\n",dfs(n,m));return 0; }

努力加油a啊，(^o)/~

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的一个数变成0的概率有多少？（记忆化搜索）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。