编程珠玑习题：咖啡罐问题

编程珠玑P40页

问题描述：

  给定一个成有一些黑色豆子和一些白色豆子的咖啡罐以及一大堆“额外”的黑色豆子，从罐子中随即选取两颗豆子，如果颜色相同，就将他们扔掉并却放入一个黑色的豆子；如果颜色不通，就将白色豆子放回罐子中，而将黑色的豆子扔掉。重复上述过程，直到罐子中只剩一颗豆子为止。

      证明该过程会终止，最后留在管子中的豆子的颜色和最初白色豆子和黑色豆子的数量有什么函数关系？

 

 

设罐中共有B个黑豆，W个白豆，总量S为B+W， 每个豆子记为b,w。

取出2个豆子

bb:
B=B-1
W=W
S=B-1 + W

ww:
B=B+1
W=W-2
S=B+1+W-2

bw:
B=B-1
W=W
S=B-1+W

综上所述，每次取出两颗豆子总量都会减少1，则最后罐子中只剩一个，该过程一定会终结。

取出bw时结果和取出bb相同。因此可认为只有取出bb和ww两种情况。
当W为2n时，
先取出全部白豆，剩下的黑豆B=B+n
再取出全部黑豆
最后剩下的为一颗黑豆。

当W为2n+1时
先取出全部白豆，剩下的黑豆B=B+n 剩下的白豆为1
再取出全部黑豆,剩下的黑豆1 剩下的白豆为1
最后剩下为一颗白豆。