一个算法题目求助

Question

算法游戏

Answer 1

你没办法保证你第一次拿多少就一定会赢，因为数量不一样是第一次拿的数量也不一样。
这个问题可以用状态树来考虑，每拿一次都要调整拿法。
可以用下面的算法找到能赢的各种拿法，然后拿的时候按照对应的状态调整拿法才能保证赢。如有7:3，那么第一次就会有很多中拿法，从1个到7个：第一次拿1个时
a: 左1
b: 右1
c: 左右都1第一次拿2个时
a: 左2
b: 右2
c: 左右都2第一次拿3个时
a: 左3
b: 右3
c: 左右都3第一次拿4个时
a: 左4
b: 右4(不能)
c: 左右都4(不能)...
一直到拿7个。每拿一次都判断一下状态，如果时 x:0, 0:x, x:x时，接下来拿的人就一定会赢。
每拿一次后就递归的开始按上面的算法拿。

Answer 2

参照<编程之美>1.13中的解法

Answer 3

大致的思路：
假设有两堆石头，数量分别为a和b，定义函数F(a,b)=true表示先拿者胜，F(a,b)=false表示先拿者负。
则有F(a,b)=F(b,a)，F(0,b) =true (b>0), F(a,a)=true (a>0), F(1,2)=false
然后，对于F(a,b)这样的函数，如果存在F(a-t, b-t)=false，或者存在F(a-t,b)=false，或者存在F(a,b-t)=false，则F(a,b)=true，否则F(a,b)=False。
====================================================================
具体的算法可以类似用筛数法求质数集合的方法int Result[aMax+1, bMax+1]={{0,...,0},{0,...,0}}; //0表示待求结果，1表示先拿者胜，-1表示先拿者负
for (int a=0; a<=aMax, a++) {
  for (int b=0; b<=bMax; b++) {
    if (a==0&&b==0) {
       continue;  //跳过没有石头的状态
    }
    int currentResult=Result[a,b];
    if (currentResult!=0) {
      continue;
    }
    if (a==b) {
      currentResult = 1;
    }
    if (a==0) || (b==0) {
      currentResult = 1;
    }
    if (currentResult==0) {
      currentResult=-1;
    }
    if (currentResult==-1) {
      //将可以一步走到当前状态的所有状态都设置为true
      for (int t=1; a+t<=aMax&&b+t<=bMax; t++){
        Result[a+t,b+t]=1;
        Result[b+t,a+t]=1;
      }
      for (int t=1; a+t<=aMax; t++){
        Result[a+t,b]=1;
        Result[b,a+t]=1;
      }
      for (int t=1; b+t<=bMax; t++){
        Result[a,b+t]=1;
        Result[b+t,a]=1;
      }
    }
    //设置当前状态变量
    Result[a,b]=currentResult;
    Result[b,a]=currentResult;
  }
}没有调试过，不过大致的思路应该没错

Answer 4

Sorry没仔细看题目，题目中的石头数范围太大，直接拿上面的算法存储空间根本不够，还要再想想

Answer 5

http://blog.csdn.net/linyunzju/article/details/7674596

Answer 6

这是我根据9楼总结出来的规律。
1:1,2
2:3,5
3:4,7
4:6,10
5:8,13
6:9,15
7:11,18
8:12,20
9:14,23
10:16,26赢的方法是：
如果 |a-b| = 4 
1、拿到只剩  a:6，b:10，如果开局就这样，那必输
1.1、如果乙拿了之后，|a-b|<4， 那甲从AB都拿，总能凑成1:1,2、2:3,5、3:4,7
1.2、如果乙拿了之后，|a-b|>=4，那甲只从一堆拿，总能凑成1:1,2、2:3,5、3:4,7
2、如果拿不到   a:6，b:10，如 a:1，b:5，那就只从一堆拿，总能凑成1:1,2、2:3,5、3:4,7 TreeSet<Integer> set = new TreeSet<Integer>();
for (int i = 1; i < 100; i++) {
set.add(i);
}
for (int i = 1;; i++) {
int a = set.first();
int b = a + i;
System.out.println(i + ":" + a + "," + b);
set.remove(a);
if (!set.remove(b)) {
break;
}
}

Answer 7

至少可以证明，对于石头堆(a，b)，的情况下，任意取a，必定存在一个b，b<=2a，使得石头堆(a，b)是先拿者必输。
理由如9L所示。
1. 任意一行中，最多只存在1种先拿者输掉的方法，设为(a0,b0)
2. 这种先拿者必输的方案，在另一行a1上只可能有2个先拿者胜的投影(a1, b0), (a0+(a1-a0), b0+(a1-a0))
3. 所以对于行a1而言，从行1到行a1-1最多只能有2*a1个先拿者胜的投影。
4.那么接下来的那一个元素自然是先拿者必输的。另外算了一下，在200*200的范围内，先拿者负的情况为（这里去掉了重复的情况，将数量较少的石堆放在前面）
1 , 2
3 , 5
4 , 7
6 , 10
8 , 13
9 , 15
11 , 18
12 , 20
14 , 23
16 , 26
17 , 28
19 , 31
21 , 34
22 , 36
24 , 39
25 , 41
27 , 44
29 , 47
30 , 49
32 , 52
33 , 54
35 , 57
37 , 60
38 , 62
40 , 65
42 , 68
43 , 70
45 , 73
46 , 75
48 , 78
50 , 81
51 , 83
53 , 86
55 , 89
56 , 91
58 , 94
59 , 96
61 , 99
63 , 102
64 , 104
66 , 107
67 , 109
69 , 112
71 , 115
72 , 117
74 , 120
76 , 123
77 , 125
79 , 128
80 , 130
82 , 133
84 , 136
85 , 138
87 , 141
88 , 143
90 , 146
92 , 149
93 , 151
95 , 154
97 , 157
98 , 159
100 , 162
101 , 164
103 , 167
105 , 170
106 , 172
108 , 175
110 , 178
111 , 180
113 , 183
114 , 185
116 , 188
118 , 191
119 , 193
121 , 196
122 , 198
==========================
仅仅从数字规律而言，可以看出前后两个石头数量之差为1,2,3...是一个等差数列，
而且从取数的规律而言，可以采用以下方式找到所有的先拿者输的情况（没有证明过，只是从规律上猜的）
a=1, b=2，先拿者负 set.put(2)
下一行
a=2，由于元素2已经在set中了，跳过，同时set.remove(2) -- 以后再也不可能查到第2行了，所以从set里删掉它
a=3，set中没有元素3，所以
a=3, b=a+2=5是一个新方案，set.put(5)
下一行
a=4,set中没有元素4，所以
a=4, b=a+3=7是一个新方案，set.put(7)
下一行
a=5，由于元素5已经在set中了，跳过，同时set.remove(5)
下一行
a=6,set中没有元素6，所以
a=6, b=a+4=10是一个新方案，set.put(10)
下一行
a=7，由于元素7已经在set中了，跳过，同时set.remove(7)
...
这样依次类推，一直到a, b超过所要求得范围为止，这样，至少不需要1Gx1G这么多的内存。