首页 > 试题广场 >

红蓝球

[编程题]红蓝球

热度指数：197 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一个非常经典的概率问题，是一个袋子里面有若干个红球和若干个蓝球，两个人轮流取出一个球，谁先取到红球谁就赢了，当人的先后顺序和球的数量确定时，双方的胜率都可以由计算得到，这个问题显然是很简单的。

现在有一个进阶版的问题，同样是一个袋子里面有n个红球和m个蓝球，共有A，B，C三人参与游戏，三人按照A，B，C的顺序轮流操作，在每一回合中，A，B，C都会随机从袋子里面拿走一个球，然而真正分出胜负的只有A，B两个人，没错，C就是来捣乱的，他除了可以使得袋子里面减少一个球，没有其他任何意义，而A，B谁先拿到红球就可以获得胜利，但是由于C的存在，两人可能都拿不到红球，此时B获得胜利。

输入描述:

输入仅包含两个整数n和m,表示红球和蓝球的数量，中间用空格隔开。(0<=n,m<=1000)

输出描述:

请你输出A获胜的概率，结果保留5位小数。

示例1

输入

1 1

输出

0.50000

示例2

输入

3 4

输出

0.62857

算法知识视频讲解

这个昵称与你无缘

记忆化搜索，dp[i][j][k][t]代表当前有i个红球，j个篮球，第k个人应该摸球（0,1,2分别代表ABC三人），t胜利的可能性（0,1分别代表AB），状态转移比较好想，枚举当前抓的不同的球即可。

#include <bits/stdc++.h>

using namespace std;

#define ll long long int
#define angel 0x3f3f3f3f
#define maxn 1005
#define pb push_back

const ll mod=1000000007;
double dp[maxn][maxn][3][2];
double dfs(int n,int m,int people,int color)
{
    if(dp[n][m][people][color]!=-1)
        return dp[n][m][people][color];
    if(n==0)
    {
        if(color==0)
            return 0;
        return 1;
    }
    double p=0;
    if(n>0)
    {
        if(people==0||people==1)
        {
            if(people==color)
                p=p+(n*1.0/(n+m));
        }
        else
            p=p+(n*1.0/(n+m))*dfs(n-1,m,0,color);
    }
    if(m>0)
        p=p+(m*1.0/(n+m))*dfs(n,m-1,(people+1)%3,color);
    dp[n][m][people][color]=p;
    return p;

}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    //memset(dp,-1,sizeof(dp));
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=2;k++)
            {
                dp[i][j][k][0]=-1.0;
                dp[i][j][k][1]=-1.0;
            }
        }

    }
    printf("%.5lf\n",dfs(n,m,0,0));
    return 0;
}

发表于 2020-09-20 15:53:06 回复(0)

Java

繁华lta

import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner reader = new Scanner(System.in);
    while (reader.hasNext()) {
      System.out.printf("%.5f", new Main().solution(reader.nextInt(), reader.nextInt()));
    }
  }

  private double solution(int n, int m) {
    double[][] dp = new double[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
      dp[i][0] = 1.0;
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        dp[i][j] += (double) i / (i + j);
        if (j > 1) {
          dp[i][j] += (double) j / (i + j) * (j - 1) / (i + j - 1) * i / (i + j - 2) * dp[i - 1][j - 2];
        }
        if (j > 2) {
          dp[i][j] += (double) j / (i + j) * (j - 1) / (i + j - 1) * (j - 2) / (i + j - 2) * dp[i][j - 3];
        }
      }
    }
    return dp[n][m];
  }
}

发表于 2020-07-12 16:24:25 回复(0)

0朝花夕拾

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int n,m;
double dp[N][N];
/*
3中情况
    1.A直接取到红球
    2. ABC全部是篮球，然后下一轮，即n个红球，m-3个篮球
    3. AB篮球，C红球，下一轮即 n-1个红球，m-2个蓝球
    dp[i][j]代表i个红球和j个篮球时A获胜的概率即
    dp[i][j] = 情况1 + 情况2 + 情况3
*/
int main()
{
    cin >> n >> m;
    for(int i = 1; i < n + 1; i ++)
    {
        ///取到红球,则概率为1
        dp[i][0] = 1.0;
    }
    for(int i = 1; i < m + 1; i ++)
    {
        ///取不到红球,则概率为0
        dp[0][i] = 0.0;
    }
    for(int i =  1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            ///取红球
            double Ared = (i * 1.0)/(i + j);
            ///A蓝B蓝：概率P = p（A蓝） * p（B蓝）
            double ABblue = (1-Ared) * ((j-1) * 1.0 / (i + j-1));
            double Cred = 0,Cblue = 0;
            if(j >= 2)
            {
                ///A蓝***蓝色C红色
                Cred = ABblue * (i * 1.0) / (i + j - 2);
            }
            if(j >= 3)
            {
                ///A蓝***蓝色C蓝
                Cblue = ABblue * ((j-2) * 1.0) / (i + j - 2);

            }
            dp[i][j] = Ared + Cred * dp[i-1][j-2] + Cblue * dp[i][j-3];

        }

    }
    printf("%.5f\n",dp[n][m]);
    return 0;
}

发表于 2020-09-13 18:47:46 回复(0)