抓石子争单双博弈题

lulijie

用f(a,b,c)表示A堆为a，B堆为b，C堆为c时，先行方取石子最后能取得的结果。
f(a,b,c)=0    表示先行方必得到偶数结果
f(a,b,c)=1    表示先行方必得到奇数结果
f(a,b,c)=2    表示奇偶结果由先行方决定
f(a,b,c)=3    表示奇偶结果由后行方决定
-------------------------------------------------------------
电脑编程（我用的是VB6.0，楼主要的话可以向我索取），f(27,27,27)之内的所有结果见附件。
下面摘取其中的部分结果。
f(4,5,6)=2
f(4,6,7)=2
f(7,7,7)=2
说明楼主后来举的三个简单些的题目，无论最后是偶数胜还是奇数胜，都是先行方胜。
而f(27,27,27)=0    即先行方必得偶数。
说明偶数胜，则先行方胜，奇数胜则先行方败。

答案.rar (16.48 KB, 下载次数: 6)

2011-9-11 22:37:13 上传

下载次数: 6

lulijie

f(27,24,27)=1，说明先行方必得奇数。
所以若结果偶数胜，那么 (27,27,27)---->（27,24,27）就能胜利。
而(27,27,27)所能演变的所有其他结果f(a,b,c)都等于2，所以其他取法都不能取得胜利。
而若结果为奇数胜，那么后行方必得到奇数结果，所以先行方必败。

lulijie

f(6,3,4)=3
说明无论是奇数胜还是偶数胜，先行方必败。

lulijie

f(a,b,c)=0    表示先行方必得到偶数结果
f(a,b,c)=1    表示先行方必得到奇数结果
f(a,b,c)=2    表示奇偶结果由先行方决定
f(a,b,c)=3    表示奇偶结果由后行方决定
-----------------------------------
递推方法的思路：
f(0,0,0)=0
(a,b,c)---->(x,y,z)
若所有能演变的(x,y,z)中，f()值都等于0或2(至少有一个值为0),那么f(a,b,c)=(a+b+c) mod 2   
若所有能演变的(x,y,z)中，f()值都等于1或2(至少有一个值为1),那么f(a,b,c)=(a+b+c-1) mod 2
若所有能演变的(x,y,z)中，f()值至少有一个为0，且至少有1个为1),那么f(a,b,c)=2
若所有能演变的(x,y,z)中，f()值至少有一个为3，那么f(a,b,c)=2
若所有能演变的(x,y,z)中，f()值都等于2，那么f(a,b,c)=3

lulijie

比如初始，(0,0,0)
那么先行方只能拿到0个，即必拿到偶数，所以f(0,0,0)=0
------------------------------------------------------------------------------
1: 下面递推f(1,0,0)
(1,0,0)只能变为(0,0,0)
面临(0,0,0)局面的是对方，它只能拿到偶数，所以面临(1,0,0)的先行方必拿到奇数。    （1+0+0） mod 2=1
所以f(1,0,0)=1
同理 f(0,1,0)=1;f(0,0,1)=1
------------------------------------------------------------
2:下面递推f(2,0,0)
(2,0,0)可变为(1,0,0)，（0,0,0）
因为f(1,0,0)=1,f(0,0,0)=0
所以先行方即可以使对手面临必奇局面(1,0,0),也可以让对手面临必偶局面(0,0,0),
也就是说自己拿奇数还是偶数由自己决定，所以f(2,0,0)=2
--------------------------------------------------------------------------------
3:下面递推f(3,0,0)
(3,0,0)可变为(2,0,0)，(1,0,0),（0,0,0）
因为f(2,0,0)=2,f(1,0,0)=1,f(0,0,0)=0,所以f(3,0,0)=2
   如果结果偶数胜，那么先行方需---->(1,0,0)才能胜，
   如果结果奇数胜，那么---->(0,0,0)才能胜。
   无论哪种情况都不能---->(2,0,0)，因为这样取奇取偶由对方决定了。
-------------------------------------------------------------------------------------------
4.下面递推f(4,0,0)
(4,0,0)可变为(3,0,0),(2,0,0),(1,0,0)，变不了(0,0,0）,因为m=3.
因为f(3,0,0)=2,f(2,0,0)=2，f(1,0,0)=1
所有先行方只有---->(1,0,0)一条路，即对手必奇，那么自己也必奇。   (4+0+0-1) mod 2=1
不能---->(3,0,0)或(2,0,0)，否则奇偶由对手决定了。
---------------------------------------------------------------------
依此类推......
(1,1,0)
因为f(0,1,0)=1,f(1,0,0)=1
所以，f(1,1,0)=((1+1+0-1) mod 2)=1
------
(2,1,0)
因为f(1,1,0)=1,f(0,1,0)=1,f(2,0,0)=2
所以，f(2,1,0)=((2+1+0-1) mod 2)=0
........

lulijie

只要把递推的思路编程，递推过程交给电脑就万事大吉了，不过要把结果记录下来，否则白干。

lulijie

楼主把题目改成了没有确切数值的一般情况，电脑编程最怕这个情况。
解决这种题目的方法：
1. 先让电脑计算出一大堆结果来，然后人脑去分析出规律。
2. 直接用人脑，寻找规律。（电脑在这方面不如人脑）