匣子游戏（湖南省第七届大学生计算机程序设计竞赛）

盒子游戏（湖南省第七届大学生计算机程序设计竞赛）
盒子游戏

有两个相同的盒子，其中一个装了n个球，另一个装了一个球。Alice和Bob发明了一个游戏，规则如下：Alice和Bob轮流操作，Alice先操作。每次操作时，游戏者先看看哪个盒子里的球的数目比较少，然后清空这个盒子（盒子里的球直接扔掉），然后把另一个盒子里的球拿一些到这个盒子中，使得两个盒子都至少有一个球。如果一个游戏者无法进行操作，他（她）就输了。下图是一个典型的游戏：

                                     

面对两个各装一个球的盒子，Bob无法继续操作，因此Alice获胜。你的任务是找出谁会获胜。假定两人都很聪明，总是采取最优策略。
输入
输入最多包含300组测试数据。每组数据仅一行，包含一个整数n（2<=n<=10^9）。输入结束标志为n=0。
输出
对于每组数据，输出胜者的名字。
样例输入
2
3
4

0

样例输出

Alice
Bob

Alice

分析：

首先想到的肯定是 博弈论

1）如果 n 是偶数，则可以平分，后面的人就无法操作了。因此Alice 和 Bob 操作后都不会留下偶数。

2）如果 n 是奇数，则可以一定可以分成一个 奇数 和 一个偶数， 如果偶数大一些，则接下来操作的人会把奇数扔掉，然后把偶数平分就赢了。

把分出来的数按1）和2）进行就能得出结果。

因为Alice 先操作，所以我们可以把Bob赢的情况算出来。

设 a[i]表示 n == a[i] 时，Bob赢。

则  a[0] = 3

     a[n]   = a[n-1] + (a[n-1]+1)   //因为  a[i] 都是奇数， 所以 a[i] + 1就是 偶数。

     把递推式化一下可以得出  a[n] = 2^(n+2) -1

     所以只要 给出的 n  = 2^k - 1(k为正整数)，则 Bob 赢，否则 Alice 赢。