【转】《编程珠玑》咖啡豆问题

---

以下为转载内容     作者：Guo Jing  原文地址：http://www.jguoer.com/blog/index.php/archives/275

问题：

给定一个盛有一些黑色豆子和一些白色豆子的咖啡罐以及一大堆额外的黑色豆子，重复以下过程，直至罐中仅剩一颗豆子为止。

从罐中随机选取两颗豆子，如果颜色相同，就将它们都扔掉并且放入一个额外的黑色豆子，如果颜色不同，就将白色的豆子放回罐中，而将黑色的豆子扔掉。

证明该过程会终止。最后留在罐中的豆子颜色与最初的罐中的白色豆子和黑色豆子的数量有什么数学关系。

思考：留在后面。

抽象：

1.用链表，但是不适合随机查找，不适合用数组。（C#可以用List）

2.黑白豆子用0，1表示。

3.随机数，两次随机拿一个豆子，就是两次随机。

技巧：留在后面。

明确了问题和抽象之后，我们可以编写一下代码来实现这个咖啡豆问题。如果你懒得看代码直接看后面的思考和技巧。

//定义一个List泛型对象 
private static List<int> box;

static void Main(string[] args) 
{ 
    //初始化4个黑豆子和4个白豆子，找规律 
    TestMain(4, 4); 
     
    Console.ReadKey(); 
}

static void TestMain(int blackNumber,int whiteNumber) 
{ 
    //初始化“咖啡罐” 
    box = new List<int>(); 
    SetBox(blackNumber,whiteNumber); 
    //如果“咖啡罐”里面的咖啡豆不等于1 
    while (box.Count != 1) 
    { 
        //拿咖啡豆 
        GetCoffee(); 
    }

    Console.WriteLine(GetStyle(box[0])); 
    box = null; 
}

上面我们写一个主函数，这个代码比较简单，虚拟了拿咖啡豆的过程，如果咖啡豆的数量不等于1的话，我们就继续拿，这里用了SetBox方法初始化咖啡罐，代码如下。

//0 黑色咖啡豆 
//1 白色咖啡豆 
static void SetBox(int blackNumber, int whiteNumber) 
{ 
    Console.WriteLine("Black " + blackNumber + " White " + whiteNumber); 
    //添加黑色豆子 
    for (int i = 0; i < blackNumber; i++) 
    { 
        box.Add(0); 
    }

    //添加白色豆子 
    for (int i = 0; i < whiteNumber; i++) 
    { 
        box.Add(1); 
    } 
}

这里最主要的方法就在GetCoffee方法，这个是我们的核心方法，在明确了问题和抽象之后我们可以写如下代码，代码并不复杂。

static void GetCoffee() 
{ 
    //拿出的咖啡豆的颜色初始化 
    int fCoffee = 0; 
    int sCoffee = 0; 
     
    //随机数 
    Random random = new Random();

    //随机数的最大值 
    int max = 0; 
     
    //随机数的最大值等于咖啡罐中的咖啡豆的数量 
    max = box.Count;

    //随机生成两个index 
    int fIndex = random.Next(0,max); 
    int sIndex = random.Next(0,max);

    //如果不是同一个index 
    //这里如果是同一个再执行的话肯定是有错误的 
    if (fIndex != sIndex) 
    {

        //分别获取咖啡豆的颜色 
        fCoffee = box[fIndex]; 
        sCoffee = box[sIndex];

        //如果颜色相同 
        if (fCoffee == sCoffee) 
        { 
            //丢掉一个咖啡豆 
            box.RemoveAt(fIndex); 
            //这里链表或List的长度变短，要检查是否只剩一个了 
            if (box.Count != 1) 
            { 
                //如果还有，后面的索引减少一个 
                if(sIndex!=0) 
                { 
                    sIndex–; 
                } 
                //移除咖啡豆 
                box.RemoveAt(sIndex); 
                //添加一个黑色豆子 
                box.Add(0); 
            } 
            else 
            { 
                //添加黑色豆子 
                box[0] = 0; 
            } 
        } 
        else 
        { 
            //颜色不相同检查是否为白色 
            //如果不是白色的话就丢掉 
            if (!IsWhiteCoffee(box[fIndex])) 
            { 
                box.RemoveAt(fIndex); 
            }

            if (!IsWhiteCoffee(box[sIndex])) 
            { 
                box.RemoveAt(sIndex); 
            } 
        } 
    } 
}

嗯，上面的逻辑比较复杂，其实也比较简单了，注释都写在上面了，读者可以自行查看，这里IsWhiteCoffee函数很简单，代码如下。

static bool IsWhiteCoffee(int color) 
{ 
    return color==1; 
}

嗯，整个问题来说不难，不过这里有两个陷阱。

1. 两个相同颜色的咖啡豆。
2. 随机拿取。

两个相同颜色的咖啡豆这个地方，值得注意的是，如果你的“咖啡罐”中本来就只有2个白色豆子，那么你拿出来的就是2个相同颜色的豆子，那么如果你先Remove链表里的一个元素，那么第二个再Remove的话，那么索引就超出范围了，这就会有异常。而且题目也没说这个咖啡罐里面一定两种颜色都用，说不定都是白色的咖啡豆呢。

第二个随机拿取这里就比较有意思了，具体分析一下。

思考：

其实在做题的时候我们应该先思考，这也就是为什么这个题目还小有意思，大部分的人都会一上来就看题目然后写代码，最后看看结论比较的对不对，这不是一个好习惯。OK，我们来想想这个问题，恩，如果两个颜色不同，就丢掉黑色的，如果两个颜色相同，就都丢掉。仔细想想，仔细想想，恩，对，也就是说，无论我们怎么拿豆子，白色的豆子的取出的过程都是，2个，0个，2个，0个。

也就是说，白色的豆子为偶数个的时候，留下的一定是黑色，而白色豆子为奇数的时候，留下的一定是白色！所以，随机不随机根本没有必要，就算你从第0个开始，顺序的拿两个豆子又怎样了呢？一样是这个结果，所以根本不用随机拿取。

技巧：

嗯，思考了之后，这个问题就太简单了，根本就不用浪费那么多时间写代码了，我们可以把随机过程改成顺序过程，或者直接干脆判断白色豆子的奇偶性，如果白色豆子为奇数，返回白色，否则为黑色。恩，改成一行代码了，简单吗？

总结：

所以说，写代码的时候，应该先思考，再写，否则会浪费很多精力，就算我们的程序的每个函数的性能都是O(1)，还是不及一行代码来的快，毕竟程序，本来就是数学的程序。：）

---

以下为转载内容     作者：有所成就 原文地址

关于咖啡豆的数学问题

在Guo Jing的Blog上看到

给定一个盛有一些黑色豆子和一些白色豆子的咖啡罐以及一大堆额外的黑色豆子，重复以下过程，直至罐中仅剩一颗豆子为止。

从罐中随机选取两颗豆子，如果颜色相同，就将它们都扔掉并且放入一个额外的黑色豆子，如果颜色不同，就将白色的豆子放回罐中，而将黑色的豆子扔掉。

证明该过程会终止。最后留在罐中的豆子颜色与最初的罐中的白色豆子和黑色豆子的数量有什么数学关系。

()

用循环的算法写出代码后，他写到

也就是说，无论我们怎么拿豆子，白色的豆子的取出的过程都是，2个，0个，2个，0个。 也就是说，白色的豆子为偶数个的时候，留下的一定是黑色，而白色豆子为奇数的时候，留下的一定是白色！

 

道理是对的，但是证明过程似乎有点简略了。

于是我用数学过程推了一遍：

先假设有N个豆子，其中有b(B)个黑色和w(W)个白色的。这里b(B)+w(W)=N，于是：

• 根据题目要求，每次都是取出两个豆子再放回一个豆子，所以每取一次，N都会减少一个。所以循环终将以还剩一个豆子结束（第一个问题得证），并且操作的总次数是N-1。

然后，取豆子有三种情况：

• 1 两个黑色,那么结果是-2(B)+1(B)=-1(B),黑豆子减一个
• 2 两个白色,那么结果是-2(W)+1(B),白豆子少两个，黑豆子加一个
• 3 一黑一白,那么结果是-1(B)-1(W)+1(W)=-1(B),黑豆子减一个

于是再设这操作N-1次中，遇到第2种情况x次，遇到第1和第3种情况共y次，那么经过N-1次操作后，豆子的情况是：

• [b(B)+w(W)]-x(B)-y[2(W)-1(B)]=(w-2y)(W)+(b-x+y)(B)=1

这里就清楚了：

• 如果剩下的一个豆子是黑色，那么w-2y=0，所以w，也就是白色豆子的数量必须是偶数

• 如果剩下的一个豆子是白色，那么w-2y=1，所以w是奇数。

要严谨的证明这句话：“白色的豆子的取出的过程都是，2个，0个，2个，0个。也就是说，白色的豆子为偶数个的时候，留下的一定是黑色，而白色豆子为奇数的时候，留下的一定是白色！” ，也不容易啊！

另外，根据上面那个式子还能退往后再推很多东西，也能增加条件让题目变复杂，譬如说如果外围的准备发进去的豆子不是无穷多的，等等等等

想学对计算机程序设计相关的数学的东西，在这里推荐两本书：

• 一个是Concrete Mathematics，很生动很有可读性的书。

• 一个是The Art of Computer Programming，是一套书，乃经典中的经典

• 另外，和有不少美国好大学的课程，计算机和数学类的。另外这个网站上还有很多其他科目的课程，是很好的资源。