n 个传教士和 n 个野人渡河情况，可以输出所有可能的方式： #include #include #include using namespace std; int r; int y; int n; int z; typedef struct _State { int m; int c; int b; // 表示传教士在河左岸的人数 // 表示野人在河左岸的人数 // b=1，表示船在左岸，b=0，表示船在右岸 }State; typedef struct _Rule { int m; int c; }Rule; Rule rule[1000]; class MoveGroup { public: // 规则集 //算符集 Rule move[500]; MoveGroup() { //利用构造器求算符集 int m, c; for (m = 0; m <= y; m++) for (c = 0; c <= y; c++) { if (c==0 && m!=0) { move[n].m=m; move[n].c=0; n++; } else if (m==0 && c!=0) { move[n].m=0; move[n].c=c; n++; } else if (m!=0&&c!=0&&m+c<=y&& m>=c) 

move[n].m = m; move[n].c = c; n++; { } } } endl; }; void OutResult(const vector& ruleSet, const vector< State >& StateSet, const int index) { cout <<" cout << " " << "初始状态" << " " << "(" << r << "," << r << ")"; " << "(" << 0 << "," << 0 << ")" << " " << "left" << for(int i = 0; i <= index; i ++) { cout << i +1 << " if( i % 2 == 0 ) "; cout << "L-to-R" << "(" << rule[ ruleSet[i] ].m << "," << rule[ ruleSet[i] ].c << ")"; cout << "R-to-L" << "(" << rule[ ruleSet[i] ].m << "," << rule[ ruleSet[i] ].c << ")"; cout << " cout << " if( StateSet[i].b == 1 ) (" << StateSet[i].m << "," << StateSet[i].c << ")"; (" << r-StateSet[i].m << "," << r-StateSet[i].c << ")"; cout << " " << "left " << endl; cout << " " << "right " << endl; else else } z++; } bool IsExist(const vector< State >& StateSet, const State& state, const int index) { if( state.m == r && state.c == r && state.b == 1) return true; for(int i = 0; i <= index; i ++) if(StateSet[i].m == state.m && StateSet[i].c == state.c && StateSet[i].b == state.b) return true; return false; } bool SearchRule(vector& ruleSet, vector< State >& StateSet, int index, 

State NowState) if(NowState.b == 0 && NowState.c == 0 && NowState.m == 0) // 达到最终状 { 态 { } OutResult(ruleSet, StateSet, index); return true; int iSize = ruleSet.size(); if( iSize <= index ) { cout << "full" << endl; return false; } State state; for(int i = 0; i < n; i ++) { state = NowState; if( NowState.b == 1 ) // 船在左岸 { state.m -= rule[i].m; state.c -= rule[i].c; if( state.m < 0 || state.c < 0 ) continue; // state 为安全状态 if( state.m == state.c || { state.m == r || state.m == 0 ) state.b = 0; if( IsExist(StateSet, state, index) ) continue; ruleSet[ index + 1 ] = i; StateSet[ index + 1 ] = state; SearchRule(ruleSet, StateSet, index+1, state); } // 在右岸 state.m += rule[i].m; state.c += rule[i].c; } else { if( state.m > r || state.c > r ) continue; if( state.m == state.c || { state.m == r || state.m == 0 ) 

state.b = 1; if( IsExist(StateSet, state, index) ) continue; ruleSet[ index + 1 ] = i; StateSet[ index + 1 ] = state; SearchRule(ruleSet, StateSet, index+1, state); } } } return false; } int main() { cout<<"请输入传教士和野人的数目:"; cin>>r; cout<>y; MoveGroup p; for(int i=0;i ruleSet; vector< State > StateSet; ruleSet.resize( 10000 ); StateSet.resize( 10000 ); cout << "假设初始状态，野人、传教士和船都在左岸" << endl; cout << " 摆渡规则" << " " << "左岸(m,c)" << " // 存放状态 " << "右岸 (m,c)" } << " " << "船的状态" << endl; SearchRule(ruleSet, StateSet, -1, InitState); cout<<"总共有"<