今天的一道逻辑面试题目，大家进来看看……

三月廿七

编程珠玑 里面有讲这个题目。。这位面试官大概看了这本书吧
前面几位也解释的很清楚了
davelv 发表于 2011-10-11 12:24

phoenixlwp

巧方法之前有人说了，红球每次要么少2个，要么不少，所以最后一定会有一个红球的，这样答案就是红球了

另一种方法，可以忽略个数的限制，初始状态为“奇红奇白”然后根据两种不同的取球方法画有限状态机，画好后由初始状态开始，找到结束状态就行了，这个方法百搭的
对于这个题，第二种方法的状态图就两种状态，灰常简单

zylthinking

回复  zylthinking


    但是没有原理，这个不能用来说服人啊
phoenixlwp 发表于 2011-10-11 13:27

还没有原理， 你还想要什么原理？？？

davelv

我算了一下，最终概率结果是：红色有0.25的概率一次减少2个，白色有0.5几率一次减少1个。

sudayly

回复 1# zheguzai


    先回帖在看贴！

每次试验红球/白球的变化数可能为：
红球 0 或 -2
白球 -1 或 +1
这意味着，每次试验，红球的数可能保持不变或者减少2个，而白球可能增加或减少一个。刚开始有99个红球和白球，最后留下的只能是红球。

写了个程序来模拟：

1. #include <iostream>
   
2. #include <ctime>
   
3. #include <cstdlib>
   
4. using namespace std;
   
5. 
   
6. class Game {
   
7. private:
   
8.         int a_; // No. of white ball
   
9.         int b_; // No. of red ball
   
10. public:
    
11.         Game(int a, int b) : a_(a), b_(b) {}
    
12.         void Run() {
    
13.                 while (!Stop()) {
    
14.                         Next();
    
15.                         cout << a_ << " " << b_ << endl;
    
16.                 }
    
17.         }
    
18. private:
    
19.         bool Stop() {
    
20.                 return a_+b_<=1;
    
21.         }
    
22.         void Trans1() {
    
23.                 a_ += 1;
    
24.                 b_ -= 2;
    
25.         }
    
26.         void Trans2() {
    
27.                 a_ -= 1;
    
28.         }
    
29.         void Next() {
    
30.                 if (a_ < 1) {
    
31.                         Trans1();
    
32.                         return;
    
33.                 }
    
34.                 if (b_ < 2) {
    
35.                         Trans2();
    
36.                         return;
    
37.                 }
    
38.                 if ((rand() * 1.0 / RAND_MAX) <= 0.5) {
    
39.                         Trans2();
    
40.                 } else {
    
41.                         Trans1();
    
42.                 }
    
43.         }
    
44. };
    
45. 
    
46. int main(int argc, char *argv[])
    
47. {
    
48.         srand(time(NULL));
    
49. 
    
50.         Game game(99, 99);
    
51.         game.Run();
    
52. 
    
53.         return 0;
    
54. }
    

复制代码

程序运行结果图示：


这个随机数生成器不给力！！！

damcool

第一次取出两个红球告诉我怎么放白球进去！

quake0day

回复 1# zheguzai




用面试时的快速思考方法去解。首先可以根据问题先猜测答案唯一。那么取法应该是不固定的，直接考虑极端取法。很快就能得到答案。