我用c语言写了一个关于商人过河的问题

王朝vc·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

#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++。。》作者是唐诠,是江苏省的教材

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有  導航