读书人

关于递归求取球的概率有关问题答案和

发布时间: 2012-12-30 10:43:14 作者: rapoo

关于递归求取球的概率问题,答案和解释都有,我还是不懂,是不是没救了?
某个袋子中有红球m个,白球n个。现在要从中取出x个球。那么红球数目多于白球的概率是多少呢?
下面的代码解决了这个问题。其中的y表示红球至少出现的次数。
这与前文的问题是等价的。因为如果取30个球,要求红球数大于白球数,则等价于至少取出16个红球。请根据仅存的线索,判断程序逻辑,并补全缺少的代码。

/*
m: 袋中红球的数目
n: 袋中白球的数目
x: 需要取出的数目
y: 红球至少出现的次数
*/
#include<stdio.h>
double pro(int m, int n, int x, int y)
{ double p1,p2;
if(y>x) return 0;
if(y==0) return 1;
if(y>m) return 0;
if(x-n>y) return 1;
p1 = pro(m-1,n,x-1,y-1);
p2 = pro(m,n-1,x-1,y);
return (double)m/(m+n)*p1 + (double)n/(m+n)*p2;
}

main()
{
int m,n,x,y;
double g;
scanf("%d %d %d",&m,&n,&x);
y=x/2+1;
g=pro(m,n,x,y);
printf("%f\n",g);
}
return返回的值为袋中红球的数目为m、白球数目为n、需要取出x个球、红球至少出现y次时的概率。
此函数为递归函数,每进行一次函数调用代表从袋中取出一个球,可能是红球也可能是白球 (double)m/(m+n)*p1为取红球的概率 (double)n/(m+n)*p2为取白球的概率。

x 中至少 y 个红球等价于下面两个事件的和:
第一个是红球,之后 x-1 个球中到少 y-1 个红球。
或者第一个取的球为白球,之后取的 x - 1 个球中至少 y 个红球。
这两个事件不交,所以它们和的概率等于概率的和。

前面那个事件是:m/(m+n) * pro(m-1, n, x-1, y-1)
后面那个事件是: n/(m+n) * pro(m, n-1, x-1, y)

前面的解释懂。就是不懂为什么要乘m/(m+n) 和n/(m+n), 谁帮帮我解释下啊?
[解决办法]
不要从代码去推算法,先想出算法,然后看代码。显然题目的答案是:

C(1, n)*C(x-1, m) + C(2, n)*C(x-2, m) + ... + C((x-1)/2, n)*C((x+1)/2, m)
--------------------------------------
C(x, m+n)

读书人网 >软件架构设计

热点推荐