黑白球

· · 个人记录

黑白球

题目描述

一个箱子里面有n个黑球m个白球。你每小时都随机从箱子里面抽出两个小球，然后把这两个球都染成黑球，然后再放回去。问需要多少小时才能把所有小球变成黑色小球？输出期望值。

输入格式

多组测试数据。

第一行，一个整数G，表示有G组测试数据。1<=G<=10

每组测试数据格式如下:

一行，两个整数，n和m。1 <=n,m<=47。

输出格式

共G行，每行一个实数。误差不能超过0.00001。

输入样例

5
1 1
2 1
1 2
4 7
1 3

输出样例

1.0
1.5
2.0
13.831068977298521
3.4

解题思路

题目大意：有黑白两种球，求将全部球染成黑球的操作次数期望值。

经过一段时间的思考，我们可以发现本题用动态规划解决是比较方便的，可以用二维的动态规划；因为题目中只有两种颜色的球，所以这里采用较方便的一维。

我们设f[i]表示盒子里有i个黑球，还要多少小时才能变成n+m个黑球。很显然，白球数量就是n+m-i个。

根据题意，我们要从最开始的n个黑球f[n]推到全部变为黑球f[n+m]。

那么f[i]是怎么推来的呢？抽球的概率又怎么计算呢？

首先，我们分类讨论：

对于第i次操作：

  1. 抽到两个黑球
  2. 抽到两个白球
  3. 先抽到黑球，再抽到白球
  4. 先抽到白球，再抽到黑球

对于以上四种情况，我们有以下四条概率计算式：

  1. 抽到两个黑球的概率是： \frac{i}{n+m}\times\frac{i-1}{n+m-1}
  2. 抽到两个白球的概率是： \frac{n+m-i}{n+m}\times\frac{n+m-i-1}{n+m-1}
  3. 先抽到黑球，再抽到白球的概率是： \frac{i}{n+m}\times\frac{n+m-(i-1)}{n+m-1}
  4. 先抽到白球，再抽到黑球的概率是： \frac{n+m-i}{n+m}\times\frac{i}{n+m-1}

那么，对于第i次操作，我们运用倒推的方法就可以将式子推出来了。

f[i]=1+f[i]\times\frac{i}{n+m}\times\frac{i-1}{n+m-1}+f[i-2]\times\frac{n+m-i}{n+m}\times\frac{n+m-i-1}{n+m-1}+f[i-1]\times\frac{i}{n+m}\times\frac{n+m-(i-1)}{n+m-1}+f[i-1]\times\frac{n+m-i}{n+m}\times\frac{i}{n+m-1}

到了这一步，不知大家发现一个问题没有，f[i]在运算过程中，乘了一遍它自己，那么怎么解决这个问题呢？

利用数学知识：等式两边加一个相同的数，等式仍成立

我们不妨将f[i]\times\frac{i}{n+m}\times\frac{i-1}{n+m-1}这一项移到左边去。

f[i]-f[i]\times\frac{i}{n+m}\times\frac{i-1}{n+m-1}=1+f[i-2]\times\frac{n+m-i}{n+m}\times\frac{n+m-i-1}{n+m-1}+f[i-1]\times\frac{i}{n+m}\times\frac{n+m-(i-1)}{n+m-1}+f[i-1]\times\frac{n+m-i}{n+m}\times\frac{i}{n+m-1} (1-\frac{i}{n+m}\times\frac{i-1}{n+m-1})\times f[i]=1+f[i-2]\times\frac{n+m-i}{n+m}\times\frac{n+m-i-1}{n+m-1}+f[i-1]\times\frac{i}{n+m}\times\frac{n+m-(i-1)}{n+m-1}+f[i-1]\times\frac{n+m-i}{n+m}\times\frac{i}{n+m-1}

至此，再将(1-\frac{i}{n+m}\times\frac{i-1}{n+m-1})移回右边。

f[i]=\frac{1+f[i-2]\times\frac{n+m-i}{n+m}\times\frac{n+m-i-1}{n+m-1}+f[i-1]\times\frac{i}{n+m}\times\frac{n+m-(i-1)}{n+m-1}+f[i-1]\times\frac{n+m-i}{n+m}\times\frac{i}{n+m-1}}{(1-\frac{i}{n+m}\times\frac{i-1}{n+m-1})}

这就是最终的动态规划式子了

代码：

#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstdio>

using namespace std;
int n,m,G;
double f[255],p1,p2,p3;

int main()
{
    freopen("2829.in","r",stdin);
    freopen("2829.out","w",stdout);
     cin>>G;
     for(int gr=1;gr<=G;gr++)
     {
         cin>>n>>m;
         f[n+m+1]=f[n+m]=0.0;
         for(int i=n+m-1;i>=n;i--)//倒推
         {
             //f[i]:当前有i个黑球，还要多少个小时才能变成n+m个黑球
             //操作一次得到三种情况，转移到相应的子问题
             p1=(double(i)/double(n+m))*(double(i-1)/double(n+m-1));//两个黑球
             p2=(double(n+m-i)/double(n+m))*(double(n+m-1-i)/double(n+m-1));//两个白球
             p3=(double(i)/double(n+m))*(double(n+m-i)/double(n+m-1));//先摸到黑球后摸到白球
             p3+=(double(n+m-i)/double(n+m))*(double(i)/double(n+m-1));//先摸到白球后摸到黑球
             f[i]=(p2*f[i+2]+p3*f[i+1]+1.00)/(1.00-p1);
         }
         printf("%.6lf\n",f[n]);
     }
    return 0;
}