首页 > 代码库 > SGU495 Kids and Prizes 概率DP,期望公式

SGU495 Kids and Prizes 概率DP,期望公式

题目

这题目首先进去以后,没地方提交,第一次做SGU的题目,只能在HUSTOJ上提交了

有n个盒子,里面有礼物的,m个人,每个人拿,拿过以后 把礼物取出来 把盒子放回去,求选中礼物数的期望

其实一开始就假设方程 dp[i]为 第i个人获得礼物的概率,但是状态转移方程不知道该怎么办,想了很久都没有办法,

其实首先边界为dp[1] = 1 第一个上来选的人肯定必中

接下来一个人的 则由两部分组成,dp[i] = (1 - dp[i - 1]) * dp[i - 1] + .........,因为上一个人若没有选中,那么这一次选中的概率跟是上一个一样的,那么如果上一个人选中了呢,真的是想了好久好久啊,可是没有思路,,最后没办法,看了别的博客,那个人用了一个公式的方法做的,但是我觉得概率DP可以推的,看他介绍,一开始就强调了m个人选礼物是相互独立的事件,呃,这时候我有点开窍了,概率论学了很久了,有点忘了,每一次当一个礼物被选走的时候,人们选中礼物的概率都会减少1/n,这么说吧,我的理解是一开始选就是n个里面选一个,再后来少了一个礼物,那选中的概率就少了1/n,比如一开始有五个礼物,那么一开始选中的的概率为1,第二次按照我所想就是4/5,实际上确实 是只剩下四个礼物了,但是空盒子还是有一个的,所以一个人选中的概率为4/5,前面做多了,后来我一直以为是1/4,忘了总体,前面人选走礼物 对于这次 你的选择没有影响,因为你还是在那么多盒子里选,总得选得范围并没有发生变化,那么这样方程另一部分就出来了

dp[i] = (1 - dp[i - 1]) * dp[i - 1] + dp[i - 1] * (dp[i - 1] - 1/n)//对这个有点疑问的,题目没说n比m大,万一n比m小,一直减,会不会为负?

应该是我想多了,后面被拿完了礼物,那么一直都是0了,就算是负的乘以0也是一样的

那么这样m个人每个人 获得礼物的概率都求出来了,如何求期望呢?哈哈真的不会唉,概率忘光了...我当时的想法就是 每个人的概率乘以1然后累加,尝试了案例是对了,交了以后就过了。。。到底是为什么捏,看了别人博客都没有给出解释。。。百度了一会独立事件的期望,有个n * p的我都知道的方法,还发现了一个二项分布的计算方法,这个我是忘了,但是稍微画了一会,发现 跟这道题还是没有联系上,路过的巨巨 请给个解释,太晚了,明天自己再研究研究


int n,m;

double dp[100000 + 55];

void init() {

}

bool input() {
	while(cin>>n>>m) {

		return false;
	}
	return true;
}

void cal() {
	dp[1] = 1.00;
	for(int i=2;i<=m;i++)
		dp[i] = dp[i - 1] * (dp[i - 1] - 1.00/n*1.0) + dp[i - 1] * (1 - dp[i - 1]);
	double ans = 0.00;
	for(int i=1;i<=m;i++)
		ans += dp[i] * 1.00;
	printf("%.10lf\n",ans);
}

void output() {

}

int main() {
	while(true) {
		init();
		if(input())return 0;
		cal();
		output();
	}
	return 0;
}

而后对于公式的产生了兴趣,独立事件期望有种N * P的 一种,反过来想,从礼物考虑,每个礼物不被选中的概率为(n - 1)/n,那么n个礼物都不被选中的概率咱就不用多说了把

最后n个礼物都不被选中的期望为 n *( (n - 1)/n)^m,

那么选中礼物 的 期望为n -  n *( (n - 1)/n)^m,哈哈,跪了,啥好都不如数学好啊,想了那么久,人家一句话 简单概率期望公式 就解决了,呵呵


int n,m;

double dp[100000 + 55];

void init() {

}

bool input() {
	while(cin>>n>>m) {

		return false;
	}
	return true;
}

void cal() {
	double ans = n * 1.00;
	double tmp = 1.00;
	for(int i=1;i<=m;i++) {
		tmp *= (n - 1)*1.0/n*1.0;
	}
	ans = ans - n * tmp;
	printf("%.10lf\n",ans);
}

void output() {

}

int main() {
	while(true) {
		init();
		if(input())return 0;
		cal();
		output();
	}
	return 0;
}


SGU495 Kids and Prizes 概率DP,期望公式