1-3-5-7游戏，应该都玩过吧。
有四堆棋子，分别有1，3，5，7个。
游戏规则是甲乙两人轮流取走棋子，每次可以在任意一堆里取走任意多个（>0）。
谁拿最后一个棋子谁输。

好了，有能力的可以写一个人机对弈的，嫌麻烦的，可以像我一样，列一张胜利图表。
比如：
0,0,0,1ost
0,0,0,2:-->0,0,0,1
0,0,0,3:-->0,0,0,1
0,0,0,4:-->0,0,0,1

前面列出当前状态，后面列出取胜的下一步，如果无法取胜，则显示Lost。

这个数学的决策问题吧，和下面道题差不多，都是考奇异局势的。结果是个黄金分割的比例，没有数学知识是做不出来的，这种题不能算Ruby题了，是纯数学题。
http://acm.pku.edu.cn/JudgeOnline/problem?id=1067

说是纯数学题，有点过。
从一定的方面考虑，这个是数学题。
但是从计算机的角度去想，这就是个算法题。因为我们有计算机，只要处理好模型，一些在数学上不被认可的繁复的操作，可以由计算机去完成。
特别是这里定下了1，3，5，7的上限，并不是要求进行一般化处理，针对有限局面，用程序处理是有前途的。

说下我的思路，构造一个胜局集合，把该集合中的局面留给对手那就是稳赢。
很明显，（0，0，0，1）是这个集合的第一个元素。
下面就是考虑所有小于（1，3，5，7）的情形，我们把这些情形从小到大排。
针对每一个情形，看能不能找到一个按照游戏方式取棋子后在胜局集合中出现的情形。
简单的说，就是看当前判断情形和胜局集合中，有没有2者，仅相差一个数字的。
如果找到，则就得出当前情形的下一步解决方案。
如果未找到，则说明当前情形应该列入胜局集合，并且，当前为Lost状态。

以前我用Java写过2个版本，一个是人机对弈的，一个是列出胜利状况的。现在换了工作，也换了机器，只找到了这样一个版本，而且看上去还是没优化过的。先列出来看看吧。有空了我把Ruby版本的写出来，不过Ruby处理人机交互还得去抄下别人的。

[Copy to clipboard] [ - ]

CODE:

import java.util.*;

class Pearls {
	int line1=0;
	int line2=0;
	int line3=0;
	int line4=0;
	String str="";
	public Pearls(int l1,int l2,int l3,int l4) {
		line1 = l1;
		line2 = l2;
		line3 = l3;
		line4 = l4;
		str = String.valueOf(l1) + "," +String.valueOf(l2) + "," + String.valueOf(l3) + ","+String.valueOf(l4);
	}
	public Pearls(String tmp) {
		str = tmp;
		line1 = Integer.valueOf(tmp.substring(0,tmp.indexOf(","))).intValue();
		tmp = tmp.substring(tmp.indexOf(",")+1);
		line2 = Integer.valueOf(tmp.substring(0,tmp.indexOf(","))).intValue();
		tmp = tmp.substring(tmp.indexOf(",")+1);
		line3 = Integer.valueOf(tmp.substring(0,tmp.indexOf(","))).intValue();
		tmp = tmp.substring(tmp.indexOf(",")+1);
		line4 = Integer.valueOf(tmp).intValue();
	}
	public boolean equal(Pearls p) {
		return this.str.equals(p.str);
	}
}

public class PearlSolution {

	protected ArrayList win;
	protected Pearls result;

	public PearlSolution() {
		win = new ArrayList();
		win.add(new Pearls("0,0,0,1"));
	}

	public boolean check(Pearls p) {
		boolean Ret = false;
		ArrayList li = new ArrayList();
		String z = p.str;
		this.result = new Pearls(0,0,0,0);
		for (int x= 0; x < win.size();x++) {
			Pearls t = (Pearls)win.get(x);
			if (t.str.equals(z)) {
				Ret = false;
				break;
			}
			li.clear();
			li.add(String.valueOf(t.line1));
			li.add(String.valueOf(t.line2));
			li.add(String.valueOf(t.line3));
			li.add(String.valueOf(t.line4));
			String tmp = String.valueOf(p.line1);
			for (int y=0; y<li.size(); y++) {
				if (tmp.equals((String)li.get(y))) {
					li.remove(y);
					break;
				}
			}
			tmp = String.valueOf(p.line2);
			for (int y=0; y<li.size(); y++) {
				if (tmp.equals((String)li.get(y))) {
					li.remove(y);
					break;
				}
			}
			tmp = String.valueOf(p.line3);
			for (int y=0; y<li.size(); y++) {
				if (tmp.equals((String)li.get(y))) {
					li.remove(y);
					break;
				}
			}
			tmp = String.valueOf(p.line4);
			for (int y=0; y<li.size(); y++) {
				if (tmp.equals((String)li.get(y))) {
					li.remove(y);
					break;
				}
			}
			if (li.size() == 1) {
				Ret = true;
				this.result = t;
				break;
			}
		}
		if (!Ret) {
			win.add(p);
		}
		return Ret;
	}

	public static void main(String[] args) {
		int i=0;
		int j;
		int k;
		int l;
		int n = 7;
		PearlSolution ps = new PearlSolution();
		while (i <= 1) {
			j = i;
			while (j <= 3) {
				k = j;
				while (k <= 5) {
					l = k;
					while (l <= 7) {
						Pearls tmp = new Pearls(i,j,k,l);
						if (!tmp.equal(new Pearls("0,0,0,0"))) {
							System.out.print(tmp.str + ":");
							if (ps.check(tmp)) {
								System.out.println("-->" + ps.result.str);
							}
							else {
								System.out.println("Lost");
							}
						}
						l++;
					}
					k++;
				}
				j++;
			}
			i++;
		}
	}
}

[ 本帖最后由 jmouse 于 2008-7-3 12:40 编辑 ]