锐客网

  1. 首页 > 睿知 > it技术 > >

火柴人大战java代码 火柴人程序代码

IT技术火柴

现有21根火柴，两人轮流?。?每人每次可取1到3根 。不可多取，也不能不?。?谁取最后一根火柴谁输 java 代码1、按照题目的游戏规则，先拿第一根的人（先手）必输无疑 。
把顺次取的每一根火柴都编上序号（1—21），因为21=（4+1）×4+1，而每次拿的火柴数是1—4根 ， 这样，计算机作为后手就能控制游戏进程：计算机根据刚才先手拿走的数目，凑成5，拿到第5根火柴且只拿到第5根为止，就逼迫先手去拿第6根 。6=5+1 。以此类推，后手总是最后拿第5k根（k是自然数），先手总是被逼先拿第5k+1根，以致第21根落在自己手中而失败 。
2、欲想获胜，只能修改游戏规则 。例如
①、人先拿 ， 每次1—4根，谁取最后一根谁输，但火柴总根数改作22根或27根 。这时先手一旦拿到第5k+1根立刻暂停，让机器去拿那第5k+2根 。
或者②、人先拿，每次1—5根 ， 谁取最后一根谁输，火柴总根数21不变 。这时，人的制胜方案是把2、8、14、20号火柴抢到手而把第3、9、15、21号火柴让给对方 。
现有21根火柴，两人轮流?。咳嗣看慰梢匀?到4根，不可多取 ， 也不能不取，谁取最后一根谁输 。这个道理和编程无关，每人最多取4根，
1+4=5
21=5*4+1
也就是说 ， 只要保证每轮两方之和是5，那么4轮后取走20根 ， 最后先取的人必定取最后一根 。
第二题：需要用递推的方式，计算所有必胜必输的状态，然后保证每次取火柴都让对方到达必输状态 。
所谓必输就是只剩最后一根，或者无论怎么取后的结果都是必胜 。
所谓必胜，就是可以对方到达必输状态的情况 。
程序如下：
import java.io.*;
public class Picker {
// 火柴堆的输赢状况
private final static int EMPTY=0; // 这种排列不可能出现，如108
private final static int UNKNOWN=1; // 尚未计算出
private final static int WIN=2; //必胜
private final static int LOSE=3; //必输（如果对方够聪明)
// 用数组，保存每种火柴堆排列的输赢状态，下标为排列，如357, 111, 001, 100等等
private int[] status;
public Picker() {
// 初始化状态数组，排除所有不可能出现的情况
status = new int[358]; // 0 - 357
int i,j,k;
for (i=0; i=3; i++) {
for (j=0; j=5; j++) {
for (k=0; k=7; k++) {
status[i*100+j*10+k] = UNKNOWN;
}
}
}
// 已知 100, 010, 001必输
status[1]=LOSE;
status[10]=LOSE;
status[100]=LOSE;
// 所有能使对方到达上述三个状态的排列都是必赢的
markWin(1);
markWin(10);
markWin(100);
// 递推计算，直至357的情况被计算出来
while (status[357] == UNKNOWN) {
//找到第一个没有计算的
int node=2;
for (node = 2; node357; node++) {
if (status[node] == UNKNOWN) break;
}
// 它的所有下个状态肯定都是必赢，不然以前就能算出 。
status[node] = LOSE;
// 所有能使对方到达这个状态的排列都是必赢的
markWin(node);
}
}
// 所有能使下个状态变必输的排列都是必赢的
private void markWin(int node) {
// 假设node为必输
// 每堆的数量分别为i,j,k
int i = node / 100;
int j = node / 10 % 10;
int k = node % 10;
// 先是第一堆，可能为i+1, i+2, ..., 3
for (int i1 = i+1; i1 = 3; i1++) {
status[i1*100+j*10+k] = WIN;
}
// 第二堆
for (int j1 = j+1; j1 = 5; j1++) {
status[i*100+j1*10+k] = WIN;
}
// 第三堆
for (int k1 = k+1; k1 = 7; k1++) {
status[i*100+j*10+k1] = WIN;
}
}
// 查找所有可能的一次取火柴后的排列，找出其中必输的状态，把这个作为自己的走法

推荐阅读


上一篇：python中以空格分割字符串，Python去除字符串首尾空格

下一篇：微信小程序拍视频加水印，微信小程序怎么给视频去水印