题目 某寺庙里7个和尚:轮流挑水,为了和其他任务不能冲突,各人将有空天数列出如下表: 和尚1: 星期二,四; 和尚2: 星期一,六; 和尚3: 星期三,日; 和尚4: 星期五; 和尚5: 星期一,四,六; 和尚6: 星期二,五; 和尚7: 星期三,六,日; 请将所有合理的挑水时间安排表 思路 回朔法求解 回朔法即每进行一步,都试图在当前部分解的基础上扩大该部分解。扩大时,首先检查扩大后是否违反了约束条件,,若不违反,则扩大之,然后继续在此基础上按照类似的方法进行,直至成为完整解;若违反,则放弃该步以及它所能生成的部分解,然后按照类似的方法尝试其他可能的扩大方式,直到尝试了所有的扩大方式。
请输入和尚1的空闲时间:0 1 0 1 0 0 0 请输入和尚2的空闲时间:1 0 0 0 0 1 0 请输入和尚3的空闲时间:0 0 1 0 0 0 1 请输入和尚4的空闲时间:0 0 0 0 1 0 0 请输入和尚5的空闲时间:1 0 0 1 0 1 0 请输入和尚6的空闲时间:0 1 0 0 1 0 0 请输入和尚7的空闲时间:0 0 1 0 0 1 1
这就是八皇后问题的简化版本
将八皇后的回溯递归函数,简化为
void queue(int num){for(int i=0;i<7;++i){if(table[num][i]==’1′) //add this code{time[num]=i;if(test(time,num)){//cout<<num<<endl;if(num==6){q_print();}elsequeue(num+1);}}}}
完成代码为
;int time[7];vector <string> table;int cnt;bool test(int time[],int num ){if(num == 0)return true;for(int i=0;i<num;++i){if(time[i]==time[num])return false;}return true;}void q_print(){cout<<endl;for(int i=0;i<7;++i)cout<<time[i]+1<<” “;cout<<endl;cnt++;}void queue(int num){for(int i=0;i<7;++i){if(table[num][i]==’1′){time[num]=i;if(test(time,num)){//cout<<num<<endl;if(num==6){q_print();}elsequeue(num+1);}}}}int main(){string buff;cnt=0;freopen(“test.txt”,”r”,stdin);for(int i=0;i<8;++i){getline(cin,buff);table.push_back(buff);}queue(0);return 0;}
不要再以任何人说你,因为你不是为任何人而活,你只为自己而活,