2010年IEEE算法设计比赛中关于数论的一道题

Question

对于任意整数n， 有甲乙两个人，每个人可以从n中取出6的次方个数，比如1，6，36，216。，比赛规则为：甲先取，谁最后将数取到0便为胜者。注： 假设甲乙都都以最优化方式取数。问： 给定任意整数n，设计算法计算出谁会是最后的胜者

Answer 1

这个题估计是以前看过某题的升级版，
某题大意是这样的：
一堆石头，两个人轮流取，每次可取1　2　3　4　5中的某一个数块，
不能不取，也不能多取，
取到最后一堆者为赢
给定石头数n,问先取者有无必须策略
答案为如果石头数为6的整数倍，
则后取者必赢（先取者取k个，则后取者取6-k个就可以保证赢）
如果石头数为非6的整数倍，
则先取者必赢（先取k个石头使石头数变为6的整数倍，转化为后取者必赢的局面）
这个转化的思想比较重要，
对于这个问题，估计数论专家会有理论上的解答
这里用程序的递推＋转化的思想可以解决某一整数范围内的问题，
但对于必胜的局面，没有给出具体的取法
具体的做法是从1开始，依次分析。记(k，赢)为整数为k时，先取者必赢
则前几个的结果为
(1,赢）,(2,输),(3,赢),(4,输),(5,赢),(6,赢),(7,输),(8,赢)
以这几个结果向后递推，
方法如下：
对于某整数n，从1到n-1的结果已经给出，
下面做法如下：
先找出最大的6的k次方小于n的数k,
然后从m属于{1,6,...,6^k}检查，
看n-m的结果是先取者必赢还是必输，
如果有一个结果是先取者必输，
那么对于整数n的结果就是先取者必赢，否则必输，
依次类推就行了，
不说了，上代码，
最后结果为true表示先取者必赢，false表示先取者必输，
不清楚这个结果正确不
上代码：
需要1.4以上的jdk支持
public class Test {
/**
 * 判断n是否在array中
 * @param array
 * @param n
 * @return
 */
public static boolean isInArray(int[]array,int n) {
for(int i=0;i<array.length;i++) {
if(array[i] == n) {
return true;
}
}
return false;
}
/**
 * 得到n在array中的范围
 * array[i]<n<array[i+1]返回i
 * @param array
 * @param n
 * @return
 */
public static int getIndex(int[]array,int n) {
for(int i=array.length-1;i>=0;i--) {
if(n > array[i]) {
return i;
}
}
return 0;
}
public static void main(String[]args) throws Exception {
final int max = 1000;
final int n = (int)Math.pow(10, 1.0/6.0*Math.log10(max));
int [] array = new int[n+1];
for(int i=0;i<array.length;i++) {
array[i] = (int)Math.pow(6, i);
}
BitSet result = new BitSet(max);
int temp = 2;
result.set(1, true);
for(int i=2;i<=max;i++) {
int tempN = Test.getIndex(array, i);
if(Test.isInArray(array, i)) {
//6的次方必赢
result.set(i, true);
}else {
boolean flag = true;
//查找以前的某状态是否为false　如果是　则必赢
for(int k=0;k<=tempN;k++) {
if(!result.get(i-array[k])) {
result.set(i,true);
flag = false;
break;
}
}
if(flag) {
//否则输
result.set(i, false);
}
}
}
for(int i=1;i<=max;i++) {
System.out.print(i+""+result.get(i)+" ");
if(i%100 == 0) {
System.out.println();
}
}
}
}

Answer 2

12　13　19　20都是先取者必胜局面引用 8 楼 keeya0416 的回复:
不知是我理解错了还是怎么
我咋觉得这个题相当简单呢
就是把这个数 转成 6 进制数
然后把各位数以十进制相加
最后得到的数是 奇数 先取者胜
偶数 后取者胜那可能就是我理解错了
12 和 19 是怎么个取法让先取者胜的

Answer 3

是不是按照n%6来算啊，余数的话没几个，要是余数是偶数，先取的人第一次取N/6个数，剩下的只能一个个拿，是先拿的人赢，要是余数是奇数，就去n/6-6个数这样