坛子最近流行出概率题...程序题不大好欢乐

jquery

Problem Statement
     Your friend Psycho Sid has challenged you to a game. He has a bag containing redCount red marbles and blueCount blue marbles. There will be an odd number of marbles in the bag, and you go first. On your turn, you reach into the bag and remove a random marble from the bag; each marble may be selected with equal probability. After your turn is over, Sid will reach into the bag and remove a blue marble; if there is no blue marble for Sid to remove, then he wins. If the final marble removed from the bag is blue, you will win. Otherwise, Sid wins.
Given the number of red and blue marbles in the bag, determine the probability that you win the game.

Definition
Class: MarblesInABag
Method: getProbability
Parameters: int, int
Returns: double
Method signature: double getProbability(int redCount, int blueCount)
(be sure your method is public)
  
Notes
- A return value with either an absolute or relative error of less than 1.0e-9 is considered correct.
  
Constraints
- redCount will be between 0 and 4000, inclusive.
- blueCount will be between 0 and 4000, inclusive.
- The sum of redCount and blueCount will be odd.
  
Examples
0)  

1
2

Returns: 0.3333333333333333

Here you have a 1/3 chance of pulling out the red marble on your first turn. If you pull a blue marble, Sid will remove the other blue marble and you lose.

1)  

2
3

Returns: 0.13333333333333333

Here you must remove both red marbles on consecutive pulls. This will happen 2/15 of the time.

2)  

2
5

Returns: 0.22857142857142856

3)  

11
6

Returns: 0.0

Here you can never win.

4)  

4
11

Returns: 0.12183372183372182


大意是一个袋子里面有奇数个球。其中红球有redCount 个，蓝球有blueCount个。你先开始随机拿一个球（拿任何一个球的概率相等），然后对手拿掉一个蓝球。然后你再拿一个 球，对手再拿掉一个蓝球，如此往复。如果到对手拿球的时候蓝球都被拿掉了，那么你输了。如果你拿的最后一个球是红球，你也输了。一定要你拿的最后一个球是蓝球，你才赢。

输入，redCount ,blueCount
输出，你赢的概率  


是到TopCoder上的千分题，程序题，想个解题思路也好^_^

thejinchao

我觉得用一个二叉树的遍历算法能解决这个问题，左分支是拿红球，右分支是拿蓝球，当分支中只剩下红球时算输，当分支中只剩下蓝球时算赢，然后把赢球的概率加起来即可，例如(2,3)这种情况
              (2,3)
            /       \  
    (1,2)[2/5]      (2,1)
       /     \       /   \  
(0,1)[1/3]  (1,0) (1,0)  (2,0)

赢的概率是(2/5)*(1/3)=2/15

不过我觉得这肯定不是一个好的算法...


-----------------
欢迎光临我的博客 http://www.thecodeway.com

kaikai

dp或者递推
初始条件：
getProbability(1,0)=0
getProbability(0,1)=1
后面的是：
getProbability(red,blue)=(getProbability(red-1,blue-1)*red+getProbability(red,blue-2)*blue)/(red+blue)