博弈游戏（2）-c#求解-英雄会在线编程题目

AB两个人玩一个取石子游戏，一共有n (n>=2)个石子，要求和规则如下：

（1）第一次由 A先取，至少取一个石子，至多取(n-1)个。

（2） 两个人轮流取石子，后面一个人取石子的数目至少为1，至多为上一个人石子数的2倍。

（3） 取到最后一颗石子的人为胜利者

（4） 两个人足够聪明。

问A是否有必胜策略？如果有的话，第一次他可以取多少个石子？如果有必胜策略，返回A第一次可以取得石子数可以保证必胜，并且如果有多个答案输出最小的。如果A无法必胜，输出-1。(2 <= n <= 100000000)

       这道题还是有点意思的，最开始的思路就是递归调用，然后缓存中间值，得到结果。先说说这个不成熟的思路吧。

递归函数很简单，传入参数为：还剩余多少个石子，当前谁来取，之前的人取了多少个，这样三个参数。

函数里面就循环以下，看看取多少个石子必胜。

       当把函数写完，测试调用，速度比较快，很快地出了答案，当把数据改为较大的时候，问题来了，报错，函数调用的次数太多，而且时间很长啊，看来此路不通啊，只能另想它法了。

       经过了前面的小数据测试，发现了一些规律，形成了一些新的思路。

规律1：当前取石子的人，如果不能取尽石子，那么他应该取得石子数不超过总数的1/3,否则后面一个人肯定可以取尽石子。

试想：如果当前取石子的人，在规律一的范围内，取走某一些石子，使剩下的石子，让后面的人不管怎么取，都必输，那她自然必胜了。

      有了前面的分析，现在一个问题是，最小可以取多少了？

为了说明此问题，我们先用一个数组来表示多少个石子，能否必胜，以及最少取多少。int[] array=new int[n+1],

array[1],表示只剩一个石子，则必然胜利。array[1]=1

array[2]，必输，array[2]=-1

array[3]，必输，array[3]=-1

array[4]，必胜，]array[4]=1，表示最少取一个，必然胜利

。。。。

后面的根据规律一，很容易得出答案，array[n]是不是必输（-1），

如果不是，可以根据规律一得到一个答案，即取到的石子数，但不一定是最小的哦。

这时候就要考虑第二个思路了：

规律二：我既然去了一个较大的数字后，剩下的，后取者必输，那么我能不能取一个较小的数，抢到必输数字的前一个数字，那么，后取者一定必输？这时候我们发现规律的，这不就是降次处理了嘛？

举例来说明：

array【1】=1