取石子游戏问题
yzniu.hong
石子游戏
描述
现有4堆石子,两个人轮流取石子,他们有n种可能的取法,取法表示从第1堆取A1个石子,从第2堆中取B1个,第3堆取C1个,第4堆取D1个.如果取
的时候某一堆的石子数比所要取的石子数要少,则这种取法是不可行的.取到最后没有可行取法的人就算输了.
现给出4堆石子的石子数目以及n种取法,请问如果两个人都采用最优取法,先取的人是赢还是输.
关于输入
第一行是4个数,表示每堆石子的数目(石子数目小于等于30).
第二行是一个正整数n(n<=10),表示取法种数
接下来n行,每行4个数,表示这种取法会在每一堆石子中取多少个
关于输出
如果先手可以取胜,输出"win",否则输出"lose"
例子输入
5 5 5 5
3
1 1 1 1
1 0 1 0
0 1 0 1
例子输出
win
我的思路是这样的:
现在对于初始状态来说,甲占有主动权,那么他将在n中选择方案中挑选一种并最终可能会获得胜利,由于大家都是聪明人,那么留给乙的石子必然会满足:
不管乙选择哪种方案,乙最终都得面对失败的局面,所以,我的程序是这么写的:
请各位评定(在校计算机系学生,编程素养并不高,请各位轻拍~~~^_^)
#include <iostream>
using namespace std;
#define max 11
int S[max][4];
int n;
bool Win(int a,int b,int c,int d)
{
int count=0,A,B,C,D;
//留给甲的本身就是烂摊子,那甲肯定就输了....
for(int i=0;i<n;i++)
{
if(S[i][0]>a || S[i][1]>b || S[i][2]>c || S[i][3]>d)
count++;
}
if(count==n)return false;
count=0;
//如果甲可以做出第一步选择而不会马上让游戏over的话,那么这种选择导致的结果是:乙在甲剩下的石子中不论哪种方案,乙都会
输....
for(int i=0;i<n;i++)
{
A=a-S[i][0];
B=b-S[i][1];
C=c-S[i][2];
D=d-S[i][3];
for(int j=0;j<n;j++)
{
if(Win(A-S[j][0],b-S[j][1],c-S[j][2],d-S[j][3])==false)count++;
}
if(count==n){return true;}//乙每种方案都试过了但还是没有一种会赢
}
return false;
}
int main()
{
int a,b,c,d;
cin>>a>>b>>c>>d;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>S[i][0]>>S[i][1]>>S[i][2]>>S[i][3];
}
if(Win(a,b,c,d)==true)cout<<"win\n";
else cout<<"lose\n";
return 0;
}
yzniu.hong
如果思路对,那程序哪里出了问题才导致不能得到正确结果呢???
> }- 隐藏被引用文字 -
>
> - 显示引用的文字 -
pongba
2. 讨论欢迎，但这里不代做作业哦:)
3. 算法问题，贴上一堆代码往往是添乱。逻辑上能够证明正确、能够Q.E.D是最关键的，代码只是表达而已（与本身就是编码问题不同）。硬要表达的话伪码更清晰。
4. 思路描述==0。要别人从你代码中逆向工程？
5. 算法问题有没有先试着证明？证明不出来再来问，以下友情提供询问模板：
我有一个heuristics，直觉上是正确的，以下是其直观描述，但我无法严格证明其正确性。
--
刘未鹏(pongba)
Blog | Mind Hacks
http://mindhacks.cn
TopLanguage
http://groups.google.com/group/pongba
yzniu.hong
好吧,其实我们原来老师有个群也是让大家相互讨论的,
我也只是看到这里有很多的很有经验的高手,所以就希望大家能够给我一些启发......
我下次会注意的了,谢谢pangba提醒~~!!!
还有就是我真是感觉我思路是没有问题的,但是结果就是不对,学生嘛,都有追求正确答案的倾向,所以
希望可以在群上通过大家的讨论帮我解决这个问题,顺便如果可以给我的代码风格提出一些改进意见就更好了....
呵呵~~
On 3月23日, 下午5时20分, pongba <pon...@gmail.com> wrote:
> 1. 发帖标题不加tag（详见首页）。
> 2. 讨论欢迎，但这里不代做作业哦:)
> 3.
> 算法问题，贴上一堆代码往往是添乱。逻辑上能够证明正确、能够Q.E.D是最关键的，代码只是表达而已（与本身就是编码问题不同）。硬要表达的话伪码更清晰。
> 4. 思路描述==0。要别人从你代码中逆向工程？
> 5. 算法问题有没有先试着证明？证明不出来再来问，以下友情提供询问模板：
> 我有一个heuristics，直觉上是正确的，以下是其直观描述，但我无法严格证明其正确性。
>
> 2009/3/23 yzniu.hong <hongyz...@126.com>
pongba
还有就是我真是感觉我思路是没有问题的,但是结果就是不对,学生嘛,都有追求正确答案的倾向,所以
既然你觉得没问题，就去试着证明看。
yzniu.hong
我曾经也稍微翻看过一些关于算法正确性的证明的内容,
有些是通过循环不变量,终止性证明,等等
但是,我依然无法做到一个对我自己这个算法很清晰的证明过程,即使我写出来了,那种纯逻辑的东西我想,还是会遭到这里很多高手的质疑,哪怕它是显而易见
的:)我个人感觉这种自顶向下的分析方法并不好证明,因为这种策略的选择正是符合我们的选择习惯,很直观很自然:
那么如果真的有什么可说的话,那么我可以给出另外一种想法:
就是逆着这个过程进行分析:
假设最后留下的石子并不多的话,现在在游戏快终止的时候,肯定是乙面对很多的情况的选择时候它都会很无奈地发现,所有情况下都不能给它提供充足的石子,
就这样它，输了。....
那么我们再往前看一步的话,那么这个时候离游戏终止甲还有一次选择的机会,那么甲面对n中方案的时候,它会做出什么选择,它会给乙留下后路吗?
肯定不会,要那样的话,甲就不是最聪明的了.......
所以再往前推,如果乙每次都可以改变局势的话,他肯定不会留下死局放到最后搬起石头砸自己的脚,那么他只能被迫接受甲因为某一步阴险的策略而导致无路可
走,所以
在甲有选择的情况下,甲的一个选择,必然的结果肯定是:乙面对所有选择,最终乙都会输,
我可能罗嗦了点,但是我是这么看的,
如果pongba愿意看我这么混乱的逻辑的话,欢迎挑刺..恩~~~ 再次感谢pongba没有封帖,给我说话的机会...
On 3月23日, 下午5时30分, pongba <pon...@gmail.com> wrote:
> 2009/3/23 yzniu.hong <hongyz...@126.com>
nebuladream
> }- Hide quoted text -
>
> - Show quoted text -
Yingjie XU
#include <iostream>
using namespace std;
#define max 11
int S[max][4];
int n;
bool Win(int a,int b,int c,int d)
{
int count=0,A,B,C,D;
//留给甲的本身就是烂摊子,那甲肯定就输了....
for(int i=0;i<n;i++)
{
if(S[i][0]>a || S[i][1]>b || S[i][2]>c || S[i][3]>d)
count++;
}
if(count==n)return false;
count=0;
//如果甲可以做出第一步选择而不会马上让游戏over的话,那么这种选择导致的结果是:乙在甲剩下的石子中不论哪种方案,乙都会
输....
for(int i=0;i<n;i++)
{
A=a-S[i][0];
B=b-S[i][1];
C=c-S[i][2];
D=d-S[i][3];
for(int j=0;j<n;j++)
{
if(Win(A-S[j][0],b-S[j][1],c-S[j][2],d-S[j][3])==false)count++;
}
if(count==n){return true;}//乙每种方案都试过了但还是没有一种会赢
}
for (int i = 0; i < n; i++)
{
if (Win(a-S[j][0], ... , d-S[j][3]) == false) count++
}
also remember to record all exist status to avoid duplicated computation.
return false;
}
int main()
{
int a,b,c,d;
cin>>a>>b>>c>>d;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>S[i][0]>>S[i][1]>>S[i][2]>>S[i][3];
}
if(Win(a,b,c,d)==true)cout<<"win\n";
else cout<<"lose\n";
return 0;
}
--
"If you received this communication by mistake, please don't forward it to anyone else (it may contain confidential or privileged information), please erase all copies of it, including all attachments, and please let the sender know it went to the wrong person. Thanks."
Yingjie XU
这个应该是博弈论的Nim撒...异或一下OK
上网搜一下吧，Game Theory
2009/3/23 Yingjie XU <jdkl...@gmail.com>:
--
张酉夫
Email:zhang...@gmail.com
QQ:315209075
dragon
On 3月23日, 下午5时14分, "yzniu.hong" <hongyz...@126.com> wrote:
> }- 隐藏被引用文字 -
>
> - 显示引用的文字 -
bool Win(int a,int b,int c,int d)
{
int i;
//留给甲的本身就是烂摊子,那甲肯定就输了....
for(i=0;i<n;i++)
{
if(S[i][0]<=a || S[i][1]<=b || S[i][2]<=c || S[i][3]
<=d)
break;
}
if(i==n)return false;
//如果甲可以做出第一步选择而不会马上让游戏over的话,那么这种选择导致的结果是:乙在甲剩下的石子中不论哪种方案,乙都会
输....
for(i=0;i<n;i++)
{
if(Win(a-S[i][0],b-S[i][1],c-S[i][2],d-S[i][3])
==false)
return true;
}
return false;
}