异想天开

What's the true meaning of light, Could you tell me why

猜数字

日期:2014-05-07 17:26:01
  
最后更新日期:2014-05-08 13:57:17
题目见杭电1172
解:
这题还是去年看到的,当时感觉可以用回溯法,不想用暴力搜索,网上很多都是暴力搜索的。回溯法没写出代码,后来导致因为这点导致a题计划搁浅了,汗一下。前阵子,感到做题也是一种乐趣,所以又在上面做题了。现在还不想动手写代码,先记一下思路。
定义一个记录状态的结构,如下所示: [code lang="cpp"]
struct state{
int seq;//当前的条件序列号
char oldguess[4];//上一层的猜测值
char right_index[4];//猜对了值得位置index
char pos_index[4];//猜对了,同时位置正确的index
guess(){...}//当前状态猜测值
next(){...}//下一状态
check(){...}//检测当前状态是否吻合
};
[/code]
若数字猜对的个数为3,位置正确为1,那么next()函数,首先假定某一值猜对的right_index数组,比如134,然后枚举一个值对了,位置正确的pos_index数组,例如1或3或4。
check函数通过比较当前的猜测与上一猜测是否矛盾,矛盾则返回false,否则返回true。在不矛盾的情况下,guess()函数可以得出当前状态的猜测。
算法过程:
[code lang="cpp"]
sovle(){
count=0;//表示解的个数
state.seq=0;
stack.push(state);
while(!stack.empty()){
cur_state=stack.pop();
while(cur_state.next()){
if(cur_state.check()){
if(cur_state.seq==LAST_SEQ_NUM){
count++;
if(count>=2){
return false;
}
}else{
new_state.guess = cur_state.guess();
new_state.seq = cur_state.seq+1;
stack.push(cur_state);
stack.push(new_state);
}
break;
}
}
}
return (count==1);
}
[/code]
若有更好的解法,欢迎留言。