2008-07-01 Ruby 测试题(00021)

1-3-5-7php?name=%D3%CE%CF%B7" onclick="tagshow(event)" class="t_tag">游戏，应该都玩过吧。
有四堆棋子，分别有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处理人机交互还得去抄下别人的。