/*实在不好意思，在trans()函数中我没有把开始调试时的用的4改成total-1，现已改正，并已注明改正处，谢谢，并致以歉意*/
#include "stdio.h"
#include "string.h"
#include "conio.h"
FILE *fp;/*设立文件指针，以便将它用于其他函数中*/
struct a{
long 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;
int 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->s1>k2)return -1;/*仆人数不能超过总仆人数*/
if(p->m1>k1)return -1;/*商人数不能超过总商人数*/
if(p->s2>k2)return -1;/*对岸，同上*/
if(p->m2>k1)return -1;/*对岸，同上*/
if(p->s1<0)return -1;/*仆人数不能为负*/
if(p->s2<0)return -1;/*商人数不能为负*/
if(p->m1<0)return -1;/*对岸，同上*/
if(p->m2<0)return -1;/*对岸，同上*/
if(p->m1!=0)
if(p->s1>p->m1)return -1;
if(p->m2!=0)
if(p->s2>p->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->m2)
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=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("\nit's%d:\n",js);
fprintf(fp,"\nit's%d:\n",js);
while(p){ printf("%ld,%ld::%ld,%ld\t",p->m1,p->s1,p->m2,p->s2);
fprintf(fp,"%ld,%ld::%ld,%ld\t",p->m1,p->s1,p->m2,p->s2);
p=p->next;
;}
}/*打印函数，将p3所指的内容打印出来*/
void trans(struct aim *p){
struct aim *p3;/*p3为申请的结构体指针*/
struct a *fla;
int i,j,f,e;
fla=&head;
p3=(struct aim *)malloc(sizeof(struct aim));
f=sign(p->n);
for(i=0;i<total;i++){
fla=fla->next;
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(i<total-1){continue;}
else{
freeit(p3);
break;}}
if(j==1){if(i<total-1){print(p3);
continue;}
else{print(p3);
freeit(p3);
break;}}
if(j==0)trans(p3);
}
return;
}/*转移函数，即将人转移过河*/
/*n=0*/
main()
{ struct aim *p,*p1;int j,a,e,f;
struct a *flag;/*flag是用与记录头指针*/
FILE*fpt;
if((fpt=fopen("c:result.dat","w+"))==0){
printf("can't creat it\n");
exit(0);}
fp=fpt;
clrscr();
p=(struct aim *)malloc(sizeof(struct aim));
p->back=NULL;
p->next=NULL;
p->s2=0;
p->m2=0;
p->n=1;/*设立初始头指针*/
printf("please input the total of people on the board\n");
fprintf(fp,"\nplease input the total of people on the board\n");
scanf("%d",&n);
fprintf(fp,"\n%d\n",n);
flag=&head;
for(e=0;e<=n;e++)
for(f=0;f<=n;f++)
if(e+f>0&&e+f<=n)
{ total++;
jj=(struct a*)malloc(sizeof(struct a));
jj->m=e;
jj->s=f;
flag->next=jj;
jj->next=NULL;
flag=jj;
}
/*********************************/
printf("please input the total of merchant and salvent as follow: mechant,salvent;\n");
fprintf(fp,"\nplease input the total of merchant and salvent as follow: mechant,salvent;\n");
scanf("%ld,%ld",&p->m1,&p->s1);
fprintf(fp,"\n%ld,%ld\n",p->m1,p->s1);
/**********************************/
k1=p->m1;
k2=p->s1;
trans(p);
fclose(fpt);
getch();
}
/*一年前，我初学c语言，在数模书上无意中看到这道题原题是：有n个商人k个仆人过河，船上最多有m个人，两岸上有任意一岸仆人数多于商人数商人都会死，问应如何安排才能使商人顺利过河，若不能则不打印出全过程：建议开始值n=3,k=3,m=2
这个问题是在我自学过指针后才有思路的，并且在此之前我也在提问题的地方求教过，如今写来仅表纪念，还请大家不要笑我，谢谢*/
注明：我并非计算机专业，开始我本只想写着好玩，而且我只是想将自己
没想到。。。。不过我倒是没什么，只觉的自己的风格有待提高，其实想法很简单，就是用穷举搜索的方法，先将船上的人数建成一个二维的列表，两岸的人数建立成一个双向的链表，用于存储符合条件的情况，用检查重复的方法来解决循环出现。其实它可用来解决这样一类过河的问题，
解决问题的思想是基于多维向量的运算，不加注释，并非我一相情愿，只是我用的是turboc2.0，在其环境下无法使用中文，又怕我蹩脚的英文吓到大家，反而增加误会，还有我自己确实对c了解不是很多，我今年大二
，大二上学期才学了c，用的是一本《c/c++。。》作者是唐诠，是江苏省的教材
