首页 > 试题广场 >

红蓝球

[编程题]红蓝球

热度指数：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

算法知识视频讲解

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)