商仆过河的C程序

《商仆过河的C程序》由会员分享，可在线阅读，更多相关《商仆过河的C程序（9页珍藏版）》请在装配图网上搜索。

1、商仆过河的C程序及运行截屏 #include using namespace std; struct Node { int nMer; int nSer; int length; }; class A { public: A(); ~A(); void Tspt(); //过河的动作 void doLeft(int nhead,int ntail,int nlength); private: bool islegal(int nm,int ns); //判断是否满足约束条件，满足为true Node *funTspt(

2、int nm,int ns,bool flag);//添加STEP[head]可以向后延伸的节点 bool noRepeat(int nm,int ns);//没有重复返回TRUE void funshow(int a[][2],int ntail); bool funLeft(Node nd,int b1,int b2,int n); void show(int s[],int p[][2],int &top,int &count,int a[]); int head; int tail; int n; //商仆的对数 int nB; //船最多的载人数目

3、 Node *STEP; }; A::~A() { free(STEP); } A::A() { cout<<"请输入商仆的对数S="; F: cin>>n; if(n==1) { nB=2; cout<<"船最多载人的数目K="<

5、dl; cout<<"请输入船最多载人的数目K="; cin>>nB; } else if(n>=5&&n<=100) { cout<<"船最多载人的数目可以取:"; for(int x=4;x<=2*n;x++) { cout<

6、重新输入商仆的对数S="; goto F; } STEP = (Node *)malloc(sizeof(Node)*10000); memset(STEP,0,sizeof(Node)*10000); head = tail = 0; STEP[0].nMer = STEP[0].nSer = n; } int main() { cout<<"问题描述： S个商人各带一个随从乘船过河，一只小船只能容纳K人，由他们自己划船。商人们窃听到随从们密谋，在河的任意一岸上，只要随从的人数比商人多，就杀掉商人。但是如何乘船渡河的决策权在商人手中，商人们如何安排渡

7、河计划确保自身安全？"<

8、 top--; if(top == -1) return ; C: s[top]--; if(STEP[(s[top])].length != top)//退过了 { s[top] = a[top]; goto B; } if(funLeft(STEP[(s[top])],p[top - 1][0],p[top - 1][1],top - 1) == false) goto C; p[top][0] = STEP[(s[top])].nMer; p[top][1] = STEP[(s[top])].nSer;

9、 show(s,p,top,count,a); return ; } //在中间加入节点STEP[(s[top + 1])] if(funLeft(STEP[(s[top + 1])],p[top][0],p[top][1],top) == true)//符合条件 { top++; p[top][0] = STEP[(s[top])].nMer; p[top][1] = STEP[(s[top])].nSer; show(s,p,top,count,a); return ; } else //不符合条件

10、 { E: s[top + 1]--; if(STEP[(s[top + 1])].length == top)//退过了，到了下一层 { s[top + 1] = a[top + 1]; D: s[top]--; if(STEP[(s[top])].length != top)//退过了，到了下一层 { for(int i = top; i <= STEP[head].length; i++) s[i] = a[i]; top--; if(top == -1) return ; go

11、to D; } if(top == 0) return ; if(funLeft(STEP[(s[top])],p[top - 1][0],p[top - 1][1],top - 1) == false) goto D; p[top][0] = STEP[(s[top])].nMer; p[top][1] = STEP[(s[top])].nSer; show(s,p,top,count,a); return ; } if(funLeft(STEP[(s[top + 1])],p[top][0]

12、,p[top][1],top) == false) goto E; top++; p[top][0] = STEP[(s[top])].nMer; p[top][1] = STEP[(s[top])].nSer; show(s,p,top,count,a); } } void A::doLeft(int nhead,int ntail,int nlength) { int a[1000]; int a1[1000]; int sp[1000][2]; bool flag = false; memset(a,0xff,

13、4000); memset(a1,0xff,4000); memset(sp,0xff,8000); if(STEP[head].length%2 == 0) flag = true; while(STEP[head].length == nlength - 1) { funTspt(STEP[head].nMer,STEP[head].nSer,flag); head++; } for(int i = 0; i < head + 1; i++) { a[(STEP[i].length)] = i; a1[(S

14、TEP[i].length)] = i; } sp[0][0] = sp[0][1] = n; STEP[head].nMer = STEP[head].nSer = 0; int top = 0; int count = 0; show(a1,sp,top,count,a); } bool A::funLeft(Node nd,int b1,int b2,int n) { bool flag = abs(nd.nMer - b1) + abs(nd.nSer - b2) < nB + 1 && abs(nd.nMer - b1) + a

15、bs(nd.nSer - b2) > 0; if(flag == false) return false; if(n%2 == 0 && b1 >= nd.nMer && b2 >= nd.nSer) return true; if(n%2 == 1 && b1 <= nd.nMer && b2 <= nd.nSer) return true; return false; } void A::Tspt() { Node *temp = new Node; temp = NULL; bool flag = false; w

16、hile(head <= tail) { if(STEP[head].length%2 == 0) flag = true; else flag = false; temp = funTspt(STEP[head].nMer,STEP[head].nSer,flag); if(NULL != temp) break; head++; } if(head > tail) { cout<<"此问题无解!"<

17、mp->nMer,temp->nSer,temp->length);//temp->nMer表示head delete temp; } Node* A::funTspt(int nm,int ns,bool flag) {//flag == true 向对岸运输 Node *nd = NULL; int temp = 1; int tM = STEP[head].nMer; //可供运输的商人数 int tS = STEP[head].nSer; //可供运输的仆人数 if(flag == false) //向此岸运输 { tM =

18、n - STEP[head].nMer; tS = n - STEP[head].nSer; temp = -1; } for(int i = 0; i < tM + 1 && i < nB + 1; i++)//i表示运输的商人数 { for(int j = 0; j < tS + 1 && j < nB - i + 1; j++)//j表示运输的仆人数 { if(i + j == 0) continue; int p = STEP[head].nMer - temp*i; int q = STEP[head].nS

19、er - temp*j; if(islegal(p,q) == true && noRepeat(p,q) == true) { if(p == 0 && q == 0) { tail++; STEP[tail].length = STEP[head].length + 1; STEP[tail].nMer = p; STEP[tail].nSer = q; nd = (Node*)malloc(sizeof(Node)); nd->length = STEP[head].

20、length + 1; nd->nMer = head; nd->nSer = tail; return nd; } tail++; STEP[tail].length = STEP[head].length + 1; STEP[tail].nMer = p; STEP[tail].nSer = q; } } } return nd; } bool A::noRepeat(int nm,int ns) { int j1 = 0; if(STEP[he

21、ad].length%2 == 0) j1 = 1; for(int i = j1; i < tail + 1; i++) { if(STEP[i].length%2 == j1 && nm == STEP[i].nMer && ns == STEP[i].nSer) return false; } return true; } bool A::islegal(int nm,int ns) { //商人数少于仆人数或者商人数为0 if((nm == 0) || (nm == n) || (nm == ns)) return tr

22、ue; return false; } void A::funshow(int a[][2],int ntail) { cout< ("<