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

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处理人机交互还得去抄下别人的。

[Copy to clipboard] [ - ]