首页 > 代码库 > hdu5194 DZY Loves Balls 【概率论 or 搜索】
hdu5194 DZY Loves Balls 【概率论 or 搜索】
//yy:那天考完概率论，上网无聊搜个期望可加性就搜到这题，看到以后感觉特别亲和，挺有意思的。
hdu5194 DZY Loves Balls 【概率论 or 搜索】
题意：
一个盒子里有n个黑球和m个白球【n,m≤12】。每次随机从盒子里取走一个球，取了n+m次后，刚好取完。现在用一种方法生成了一个随机的01串S[1…(n+m)]，如果第i次取出的球是黑色的，那么S[i]=1，如果是白色的，那么S[i]=0。求‘01‘在S串中出现的期望次数。
题解：
求出在第i个位置上出现0，第i+1个位置上出现1的概率，这种情况设为Xi = 1，这就是二项分布啦，
根据期望的可加性，有E∑Xi = N * P。（期望的可加性不要求事件相互独立喔，方差要求
，所以可以这样做吖）
Xi = 1的概率 P = m / (n + m) * n / (n + m - 1)
由题意可知这里的 N = (n + m - 1)
化简一下答案就出来了: n * m / (n + m)
#include <cstdio>#include <algorithm>using namespace std;int gcd(int a, int b) {return b ? gcd(b, a%b) : a;}int main() { int m, n, x; while(~scanf("%d%d", &m, &n)) { x = gcd(m*n, m+n); printf("%d/%d\n", m*n/x, (m+n)/x); } return 0;}
还有个搜索方法，房教写的，膜拜ORZ
#include<bits/stdc++.h>using namespace std;typedef long long ll;long long dp[13][13];long long C[25][25];long long ans = 0;ll dfs(const int& x,const int& y,const int& st){ if(st==1&&dp[x][y]!=-1) return dp[x][y]; long long ans = 0; if(st==0){ if(x>0){ ans += C[x+y-1][y] + dfs(x-1,y,1); } if(y>0) { ans += dfs(x,y-1,0); } } if(st==1){ if(x>0){ ans += dfs(x-1,y,1); } if(y>0) { ans += dfs(x,y-1,0); } } if(st==1)dp[x][y] = ans; return ans;}void get_C(int maxn){ C[0][0] = 1; for(int i=1;i<=maxn;i++) { C[i][0] = 1; for(int j=1;j<=i;j++) C[i][j] = C[i-1][j]+C[i-1][j-1]; //C[i][j] = (C[i-1][j]+C[i-1][j-1])%MOD; }}int main(){ memset(dp,-1,sizeof(dp)); dp[0][0] = 0; get_C(24); int n,m; while(scanf("%d%d",&n,&m)==2) { ll b=C[n+m][n]; ll sum=dfs(n,m,1); ll a=__gcd(sum,b); printf("%lld/%lld\n",sum/a,b/a); } return 0;}
hdu5194 DZY Loves Balls 【概率论 or 搜索】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。