商人过河的数学模型及编程解决

1、摘要：M对商仆过河，一只船最多载N人，船上和岸上的仆人数都不能多于商人数，否则商人有危险。安排合理的渡河方案，保证商人能安全渡河。（可利用向量，矩阵，图解等方法）一 问题提出：有M对商仆乘船过河，一只船最多载N人，由商人和仆人自己划船渡河，在河的任意一岸，一旦仆人数多于商人数，仆人就可将商人杀死，谋取利益，但是乘船渡河的主动权掌握在商人们手中，商人们如何安排渡河方案，才能安全渡河？二 假设：商人和仆人都会划船，天气很好，无大风大浪，船的质量很好，船桨足够很多次的运载商人和仆人。三 参数：1 设（x，y）是状态向量，表示任一岸的商人和仆人数，并且x，y分别要大于等于0，小于等于M。2 设（m，n

2、）是运载向量，表示运载的商人数和仆人数，0=m=N，0=n=N，0=m+n =3， DoIfsi+1= =sm，u=1，Break ，m，l，i -1，2 ； Ifu= =0，ci+1=dj；Break ，j，1，5； Ift= =0，PrintNo，Result；Break ； bi+1=3，3-si+1； Printsi，- - - -，ci+1，- - - -，bi+1； Ifsi+1= =0，0，Break ，i，1，12 程序运行结果如下： 此岸船上对岸 3，30，20，2 3，10，10，1 3，20，20，3 3，00，10，2 3，12，02，2 1，11，11，1 2，22，

3、03，1 0，20，13，0 0，30，23，2 0，10，13，1 0，20，23，3 可以得出经过11步的渡河就能达到安全渡河的目标及满足渡河的次数尽量少的条件。这11步的渡河方案就是上面程序运行结果中船上下面的一列。渡河的整个过程如下所示： 去2随从 回1随从（3商人3随从）（3商人1随从） 去2随从 回1随从（3商人2随从）（3商人0随从） 去2商人 回1商人1随从（3商人1随从）（1商人1随从） 去2商人 回1随从（2商人2随从）（0商人2随从） 去2随从 回1随从（0商人3随从）（0商人1随从） 去2随从 （0商人2随从）（渡河成功）一 程序实现 #include stdio.h#

4、include string.h#include #include #includeusing namespace std;#include conio.hFILE *fp;/*设立文件指针，以便将它用于其他函数中*/struct along m,s;struct a *next;/*数组类型a：记录各种情况下船上的商人和仆人数，m：代表商人数s：代表仆人数*/struct a *jj,head;/*head为头指针的链表单元（船上的人数的各种情况的链表）*/int n,total=0,js=0;/*total表示船上各种情况总数*/struct aim long m1,s1,m2,s2;in

5、t n;struct aim *back,*next;/*用于建立双向的指针链表，记入符合的情况，m1，s1表示要过岸的商人数和仆人数；m2，s2表示过岸了的商人数和仆人数，n表示来回的次数*/int k1,k2;void freeit(struct aim *p)struct aim *p1=p; p1=p-back;free(p);if(p1!=NULL)p1-next=NULL;return;/*释放该单元格，并将其上的单元格的next指针还原*/ int determ(struct aim *p) struct aim *p1=p;if(p-s1k2)return -1;/*仆人数不能

6、超过总仆人数*/if(p-m1k1)return -1;/*商人数不能超过总商人数*/if(p-s2k2)return -1;/*对岸，同上*/if(p-m2k1)return -1;/*对岸，同上*/if(p-s1s2m1m2m1!=0)if(p-s1p-m1)return -1;if(p-m2!=0)if(p-s2p-m2)return -1;/*两岸商人数均不能小于仆人数*/while(p1!=NULL)p1=p1-back;if(p1!=NULL)if(p1-n%2=p-n%2)if(p1-s1=p-s1)if(p1-s2=p-s2)if(p1-m1=p-m1)if(p1-m2=p-m

7、2)return -1;/*用于解决重复，算法思想：即将每次算出的链表单元与以前的相比较，若重复，则表示出现循环*/if(p-s1=0&p-m1=0)if(p-n%2=0)return 1;else return -1;/*显然如果达到条件就说明ok了*/return 0;/*判断函数*/int sign(int n)if(n%2=0)return -1;return 1;/*符号函数*/void copyit(struct aim *p3,struct aim *p)p3-s1=p-s1;p3-s2=p-s2;p3-m1=p-m1;p3-m2=p-m2;p3-n=p-n+1;p3-back=

8、p;p3-next=NULL;p-next=p3;/*复制内容函数，将p中的内容写入p3所指向的链表单元中*/void print(struct aim *p3)struct aim *p=p3;js+;while(p-back)p=p-back;printf(n第%d种方法:n,js);fprintf(fp,n第%d种方法:n,js);int count=0;while(p) printf(%ld,%ld%ld,%ldt,p-m1,p-s1,p-m2,p-s2);fprintf(fp,%ld,%ld%ld,%ldt,p-m1,p-s1,p-m2,p-s2);p=p-next;count+;c

9、out一共有count步完成n);for(i=0;inext;copyit(p3,p);p3-s1-=fla-m*f;p3-m1-=fla-s*f;p3-s2+=fla-m*f;p3-m2+=fla-s*f;/*运算过程，即过河过程*/j=determ(p3);/*判断，j记录判断结果*/if(j=-1)if(itotal-1)continue;elsefreeit(p3);break;int count1=0;if(j=1)if(itotal-1)print(p3);count1+;continue;elseprint(p3);count1+;freeit(p3);break;/coutcount1back=NULL;p-next=NULL;p-s2=0;p-m2=0;p-n=1;/*设立初始头指针*/printf(请输入船上最多能乘多少人n);fprintf(fp,请输入船上的人数n);scanf(%d,&n);fprintf(fp,n%dn,n);flag=&head;for(e=0;e=n;e+) for(f=0;f0&e+fm=e; jj-s=f; flag-next=jj; jj-next=NULL; flag=jj; /*/printf(照下面的格式输入商人和