黑白球

真言

学无止境，创新无止境，超越无止境。

引言

这是我在编程之美上找的题目，感觉自己有自己的想法，对于书上的解法目前还没有仔细看。

题目

思路

我一次看到这种题就是递归函数去解决这种考虑情况的问题，当然我不会用递归方式去写代码，我海是喜欢非递归的方式的，我酷爱栈，代替递归的方式，显示我的能力。后来发现，好多重叠子问题，这不是典型的DP么？OMG。。。。。 dp[i][j] 存放的是黑球数为j，白球数为（i+1-j）的条件下，最后剩下一个黑球的概率。

实验

黑球为10，白球为10，最后求得概率为1

若黑球和白球都为100，最后求得概率为 1.

代码

test.cpp

// problem is the black-white ball
#include
     
      
using namespace std;



// solution to the question
double white_black_ball( int w,int b );
// get two black possible
double Same_Black(int w,int b);
// get two white possible
double Same_White(int w,int b);
// get two different ball possible
double Different_ball(int w,int b);



// main function
int main()
{
	cout<
      
       = 2 ) dp[i][j] += double(Same_White(now_w,now_b) * ( dp[i-1][now_b+1])) ; if( now_b >= 2 ) dp[i][j] += double(Same_Black(now_w,now_b) * (dp[i-1][now_b-1])); if( now_w >= 1 && now_b >= 1 ) dp[i][j] += double(Different_ball(now_w,now_b) * (dp[i-1][now_b-1])); } for(int i = 0;i
       
        = 2) return double (b*(b-1)) / double((w+b)*(w+b-1)); else return 0; } // get two white possible double Same_White(int w,int b) { if( w < 0 || b < 0 ) return -1 ; if(w >= 2) return double ( w * (w-1) ) / double ( (w+b) * (w+b-1) ); else return 0; } // get two different ball double Different_ball(int w,int b) { if( w < 0 || b < 0 ) return -1 ; if( w>0 && b>0 ) return 2.0 * double ( b * w )/ double( (w+b) * (b+w-1) ); else return 0; }