jmouse 2008-7-1 10:26
2008-07-01 Ruby 测试题(00021)
1-3-5-7游戏，应该都玩过吧。
有四堆棋子，分别有1，3，5，7个。
游戏规则是甲乙两人轮流取走棋子，每次可以在任意一堆里取走任意多个（>0）。
谁拿最后一个棋子谁输。
好了，有能力的可以写一个人机对弈的，嫌麻烦的，可以像我一样，列一张胜利图表。
比如：
0,0,0,1:Lost
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。
maninred 2008-7-1 15:12
这个数学的决策问题吧，和下面道题差不多，都是考奇异局势的。结果是个黄金分割的比例，没有数学知识是做不出来的，这种题不能算Ruby题了，是纯数学题。
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1067[/url]
jmouse 2008-7-3 12:38
说是纯数学题，有点过。
从一定的方面考虑，这个是数学题。
但是从计算机的角度去想，这就是个算法题。因为我们有计算机，只要处理好模型，一些在数学上不被认可的繁复的操作，可以由计算机去完成。
特别是这里定下了1，3，5，7的上限，并不是要求进行一般化处理，针对有限局面，用程序处理是有前途的。
说下我的思路，构造一个胜局集合，把该集合中的局面留给对手那就是稳赢。
很明显，（0，0，0，1）是这个集合的第一个元素。
下面就是考虑所有小于（1，3，5，7）的情形，我们把这些情形从小到大排。
针对每一个情形，看能不能找到一个按照游戏方式取棋子后在胜局集合中出现的情形。
简单的说，就是看当前判断情形和胜局集合中，有没有2者，仅相差一个数字的。
如果找到，则就得出当前情形的下一步解决方案。
如果未找到，则说明当前情形应该列入胜局集合，并且，当前为Lost状态。
以前我用Java写过2个版本，一个是人机对弈的，一个是列出胜利状况的。现在换了工作，也换了机器，只找到了这样一个版本，而且看上去还是没优化过的。先列出来看看吧。有空了我把Ruby版本的写出来，不过Ruby处理人机交互还得去抄下别人的。[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++;
}
}
}[/code]
[[i] 本帖最后由 jmouse 于 2008-7-3 12:40 编辑 [/i]]