C++实现传教士与野人过河问题实验报告

//一个野人，一个传教士

if (lastcurrentState.boat == 1)

operation.push_back(\左岸->右岸\); operation.push_back(\右岸->左岸\); else

currentState.churchL = lastcurrentState.churchL - 1 * lastcurrentState.boat; currentState.wildL = lastcurrentState.wildL - 1 * lastcurrentState.boat; currentState.churchR = lastcurrentState.churchR + 1 * lastcurrentState.boat; currentState.wildR = lastcurrentState.wildR + 1 * lastcurrentState.boat; currentState.boat = -lastcurrentState.boat; lastParameters.push_back(currentState);

CvsWdfs(currentState, lastParameters,operation, 0); operation.pop_back(); lastParameters.pop_back(); //一个传教士过河

if (lastcurrentState.boat == 1)

operation.push_back(\左岸->右岸\); operation.push_back(\右岸->左岸\); else

currentState.churchL = lastcurrentState.churchL - 1 * lastcurrentState.boat; currentState.wildL = lastcurrentState.wildL;

currentState.churchR = lastcurrentState.churchR + 1 * lastcurrentState.boat; currentState.wildR = lastcurrentState.wildR; currentState.boat = -lastcurrentState.boat; lastParameters.push_back(currentState);

CvsWdfs(currentState, lastParameters, operation, 0); operation.pop_back(); lastParameters.pop_back(); //一个野人过河

if (lastcurrentState.boat == 1)

operation.push_back(\左岸->右岸\); operation.push_back(\右岸->左岸\); else

currentState.churchL = lastcurrentState.churchL;

currentState.wildL = lastcurrentState.wildL - 1 * lastcurrentState.boat; currentState.churchR = lastcurrentState.churchR;

currentState.wildR = lastcurrentState.wildR + 1 * lastcurrentState.boat; currentState.boat = -lastcurrentState.boat; lastParameters.push_back(currentState);

CvsWdfs(currentState, lastParameters, operation, 0); operation.pop_back(); lastParameters.pop_back();

}

return 0;

int main(){ }

system(\); return 0;

intchurchL = 3, wildL = 3, churchR = 0, wildR = 0;//分别用来计算左岸和右岸的传教士和vectorlastParameters;//保存每一步移动操作的两岸传教士、野人人数 vector operation;//保存当前操作的描述

//初始化左岸参数，可以认为是从右岸移动至左岸的操作 //boat=-1 表示船在左岸，boat=1表示船在右岸 riverSidescurrentState; currentState.churchL = 3; currentState.wildL = 3; currentState.churchR = 0; currentState.wildR = 0; currentState.boat = 1;

lastParameters.push_back(currentState);

CvsWdfs(currentState, lastParameters,operation, 0); lastParameters.pop_back(); 野人

4程序结果

最终得到如图2、3所示的四种过河方式。

图 2 过河方式1、2

图 3 过河方式3、4