數(shù)學題（概率基本知識+DP記憶化搜索實現(xiàn)）

題意：概率題：丟n個骰子，和大于等于x的概率是多少,用反面來求，1-小于x的概率

首先丟n個骰子，可以看做是依次丟的（獨立重復試驗），每次丟的點數(shù)記錄下來，比如3個篩子123和132是不同的，所以就是一個排列（而不是組合），那么總的可能為6^n，要用long long 保存。然后再找出有多少個排序和和是小于x的。這個找特殊排列的過程用DP來構(gòu)建才不能超時（我用的是記憶化搜索，當然遞推也是可以的，仿照記憶化搜索來寫的，個人更傾向于記憶化搜索，容易理解，而且應(yīng)該很多沒用的狀態(tài)不會去到，但是遞推會推出所有狀態(tài)）

記憶化搜索，開一個二維數(shù)組dp[i][j]，表示現(xiàn)在的點數(shù)是x-i點，還要丟n-j次骰子（其實就可以理解為，還有i點才會到0，已經(jīng)丟了j次骰子）

那么當前要丟骰子，骰子的點數(shù)要滿足i-k>0，最后才能使丟了n個骰子的和小于x

然后顯然dp[i][j]= dp[i-k][j+1]和累加和

?

#include <cstdio> #include <cstring> #define N 30 #define M 160 long long dp[M][N],tot;long long dfs(long long m , int c) //m是當前的點數(shù)，c是第幾個骰子 {if(dp[m][c]!=-1) return dp[m][c];dp[m][c]=0;for(int i=1; i<=6; i++)if(m-i>0)dp[m][c]+=dfs(m-i,c+1);return dp[m][c]; } long long gcd(long long a ,long long b) {return b==0?a:gcd(b,a%b); } int main() {long long n,m;long long de,nu,tmp; //分母和分子while(scanf("%lld%lld",&n,&m)!=EOF){if(!n && !m) break;de=1;for(int i=1; i<=n; i++)de*=6; //總狀態(tài)數(shù)tot=0; //記錄要多少種排列（個數(shù)一定為n）的總和小于等于mmemset(dp,-1,sizeof(dp));for(int i=0; i<=m; i++)dp[i][n]=1; //這個不要漏dp[m][0]=dfs(m,0);nu=de-dp[m][0];tmp=gcd(de , nu);//printf("dp結(jié)果=%lld\n",dp[m][0]);//printf("分子=%lld\n",nu);//printf("分母=%lld\n",de);//printf("gcd=%lld\n",tmp);if(nu/tmp==0)printf("0\n");else if(nu/tmp==de/tmp)printf("1\n");elseprintf("%lld/%lld\n",nu/tmp , de/tmp);}return 0; }

?

遞推版本

#include <cstdio> #include <cstring> #define N 30 #define M 160 long long dp[M][N]; long long n,m; long long de,nu,tmp; //分母和分子long long gcd(long long a ,long long b) {return b==0?a:gcd(b,a%b); } void DP() {de=1;for(int i=1; i<=n; i++) de*=6; //總狀態(tài)數(shù)memset(dp,0,sizeof(dp));for(int i=0; i<=m; i++) dp[i][n]=1;for(int i=n-1; i>=0; i--) for(int j=0; j<=m; j++)for(int k=1; k<=6; k++)if(j>k)dp[j][i]+=dp[j-k][i+1];//printf("%lld\n",dp[m][0]);nu=de-dp[m][0]; } int main() {while(scanf("%lld%lld",&n,&m)!=EOF){if(!n && !m) break;DP(); //遞推構(gòu)建tmp=gcd(de , nu);//printf("dp結(jié)果=%lld\n",dp[m][0]);//printf("分子=%lld\n",nu);//printf("分母=%lld\n",de);//printf("gcd=%lld\n",tmp);if(nu/tmp==0)printf("0\n");else if(nu/tmp==de/tmp)printf("1\n");elseprintf("%lld/%lld\n",nu/tmp , de/tmp);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的uva 10759 Dice Throwing的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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