今日面试题:谁多谁少

盒子A有10个红球,盒子B有十个绿球。进行如下的操作:

随机从A中拿三个球放入B中;

随机从B中拿三个球放入A中

问题是,在哪一个盒子中,会出现一个颜色的球比另一个颜色的球更多?该如何分析?

死亡小岛分析:

原题

一个小岛,表示为一个N×N的方格,从(0,0)到(N-1, N-1),一个人站在岛上,位置(x, y),他可以上下左右走,一步一个格子,他选择上下左右的可能性是一样的。当他走出小岛,就意味着死亡。假设他要走n步,请问他死亡的概率有多大?请写出求解代码。

分析

遇到这样的问题,就试着走几步好了。当一个人在(x,y)的时候,假设他此时,死亡的概率为p(x,y,n),然后,他有四种选择,而且是可能性相同,就是说,选择上下左右的概率都是1/4:

选择上边,死亡的概率是多少呢?此时位置为(x, y-1),剩余的步数为n-1,则概率为p(x, y - 1, n - 1)

选择下边同理:概率为p(x, y + 1, n - 1)

选择左边同理:概率为p(x - 1, y, n - 1)

选择右边同理:概率为p(x + 1, y, n - 1)

则,p(x,y,n)=(p(x, y - 1, n - 1) + p(x, y + 1, n - 1) + p(x - 1, y, n - 1) + p(x + 1, y, n - 1))/4,可以表达出递归的形式。

这个题目,看似比较复杂,但是尝试走一步,之后,写出递归表达式了,就比较简单了。递归终止的条件,只要x或者y,满足了小于0或者大于n-1的时候,p=1。

代码如下:

enter image description here

本文来自微信:待字闺中,2013-07-27发布,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”。