商人过河问题程序

return;
end;
function jueche=guohe
%%%%%%%%%%%%%%%%%%%%%%
程序开始需要知道商人和仆人数；
n=input(‘输入商人数目:’,’12’);
nn=input(‘输入仆人数目:’,’12’);
nnn=input(‘输入船的最大容量:’,’20’);
if nn>n
return 0;
pointer=pointer-> next;
}
return 1;
}
}
int judge(int a,int b,int c,int d,int n) /*判断这个状态是否可行，其中使用了history函数*/
{
if(history(a,b,n)==0) return 0;
if(a> =0&&b> =0&&a <=3&&b <=3&&c> =0&&d> =0&&c <=3&&d <=3&&a+c==3&&b+d==3)
c=A(i,:)+d(j,:) ;
x=find((A(:,1)==c(1))&(A(:,2)==c(2))&(A(:,3)==c(3))) ;
v(i,x)=1; %x为空不会改变v值
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% dijstra算法
{
int x;
int y;
int state;
struct node *next;
};
typedef struct node state;
typedef state *link;
link PPointer1=NULL;
link PPointer2=NULL;
int a1,b1;
int a2,b2;
/*栈中每个数据都分为0，1状态*/
3人的可以过河，4人的没有办法。
用递归的源程序如下：
运行结果是没有解，超过3人的没有解。
开始时商人，强盗所在的河的这边设为0状态，另一边设为1状态（也就是船开始时的一边设为0，当船驶到对岸是设为1状态，在这两个状态时，都必须符合条件）
#include <stdlib.h>
struct node /*建立一个类似栈的数据结构并且可以浏览每一个数据点*/
{
if(Duhe(a,b-1,1)==1)
return 1;
}
else
{
Pop(0);
return 0;
}
}
if(n==1) /*判断0状态时，商匪状态是否符合要求*/
{
if(judge(a+1,b+1,2-a,2-b,0))
{
if(Duhe(a+1,b+1,0)==1)
return 1;
}
if(judge(a,b+2,3-a,1-b,0))
{
Push(a,b,n);
return 1;
}
else if(a==0)
{
Push(a,b,n);
return 1;
}
else if(a> =b)
{
Push(a,b,n);
return 1;
}
else return 0;
}
}
}
else return 0;
}
int Duhe(int a,int b,int n) /*递归法解决商人渡河问题，如果这一个状态符合*/
{
if(Duhe(a,b+2,0)==1)
return 1;
}
if(judge(a+来自,b,1-a,3-b,0)){
if(Duhe(a+2,b,0)==1)
return 1;
}
if(judge(a+1,b,2-a,3-b,0))
{
if(Duhe(a+1,b,0)==1)
return 1;
}
if(judge(a,b+1,3-a,2-b,0))
{ /*则判断下一个状态，直至问题解决*/
if(a==0&&b==0) return 1;
if(n==0) /*判断0状态时，商匪状态是否符合要求*/
{
if(judge(a-1,b-1,4-a,4-b,1))
{
if(Duhe(a-1,b-1,1)==1)
return 1;
}
if(judge(a,b-2,3-a,5-b,1))
g=g+1;
h=lmd(h);
end
jueche=A(jueche,:);
jueche(:,3)=[];
clear all % 080817
clc % n为商人数，m为仆人数，h为每次过河的最多人数
n=3;m=3;h=2; %初始状态及数据
m0=0;n0=0;
tic
LS=0; % 允许的状态集合S与个数LS
break;
end
for j=1:size(a,1)
pp=a(j,1);
if v(k,pp)~=0
if T(pp)>(P(k)+v(k,pp))
T(pp)=(P(k)+v(k,pp));
lmd(pp)=k;
end
end
end
mi=min(T(a));
if mi==inf
break;
else
d=find(T==mi);
void Push(int a,int b,int n)
{
link newnode;
newnode=(link)malloc(sizeof(state));
newnode-> x=a;
newnode-> y=b;
newnode-> state=n;
newnode-> next=NULL;
if(PPointer1==NULL)
for i=0:nnn
for j=0:nnn
if (i+j<=nnn)&(i+j>0) % 满足条D={(u,v)|1<=u+v<=nnn,u,v=0,1,2}
d(jc,1:3)=[i,j，1]；%生成一个决策向量立刻扩充为三维；
d(jc+1,1:3)=[-i,-j,-1]; % 同时生成他的负向量；
d=d(1);
P(d)=mi;
T(d)=inf;
k=d;
S(d)=1;
end
end
if lmd(y)==inf
jueche='can not reach';
return;
end
jueche(1)=y;
g=2; h=y;
while(1)
if h==x
break;
end
jueche(g)=lmd(h);
{
if(Duhe(a,b-2,1)==1)
return 1;
}
if(judge(a-2,b,5-a,3-b,1))
{
if(Duhe(a-2,b,1)==1)
return 1;
}
if(judge(a-1,b,4-a,3-b,1))
{
if(Duhe(a-1,b,1)==1)
return 1;
}
if(judge(a,b-1,3-a,4-b,1))
if ((i>=j)&((n-i)>=(nn-j)))|((i==0)|(i==n))
% (i>=j)&((n-i)>=(nn-j)))|((i==0)|(i==n))为可以存在的状态的约束条件
A(kx,1:3)=[i,j,1]; %生成状态数组集合D `
A(kx+1,1:3)=[i,j,0];
kx=kx+2;
pointer=pointer-> next;
}
getch();
}
a = [
0, 0;
0, 1;
0, 2;
0, 3;
3, 0;
3, 1;
3, 2;
3, 3;
1, 1;
2, 2;
]; % 10 enabled states
s=[0, 0;
0, 1;
0, 2;
0, 3;
1, 0;
1, 1;
1, 2;
1, 3;
{
if(Duhe(a,b+1,0)==1)
return 1;
}
else
{
Pop(1);
return 0;
}
}
return 0;
}
main()
{
link pointer;
Push(3,3,0);
Duhe(3,3,0);
pointer=PPointer1;
while(pointer!=NULL)
{
printf( "%d,%d---%d\n ",pointer-> x,pointer-> y,pointer-> state);
n=input(‘输入商人数目:’,’23’);
nn=input(‘输入仆人数目:’,’23’);
nnn=input(‘输入船的最大容量:’,’34’);
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 决策生成
jc=1; %决策向量放在矩阵d中，jc为插入新元素的行标初始为1；
for i = 1:12
* R5 P0 S8 N$ a' E- O
& B4 i4 Z# s# z D7 O7 j; f
for j = 1:5
t = 0;
r = mod(i, 2);
m = r;
u = 0;
for k = 1:10
if s(i, + (-1)^i * d(j, == a(k,
t = 1;
end;
b(i+1, = [3, 3] - s(i+1, ;
play = sprintf('{%d, %d}-{%d, %d}-{%d, %d}', s(i, 1), s(i, 2), c(i+1, 1), c(i+1, 2), b(i+1, 1), b(i+1, 2));
disp(play)
if s(i+1, ==[0, 0]
2, 0;
2, 1;
2, 2;
2, 3;
3, 0;
3, 1;
3, 2;
3, 3;
];
d = [
0, 2;
2, 0;
1, 1;
0, 1;
1, 0;
]; % 5 enabled decisions
i = 1;
j = 1;
k = 1;
s(1, = [3, 3];
disp('This shore - On Boat - That shore')
}
int history(int a,int b,int n) /*比较输入的数据和栈中是否有重复的*/
{
link pointer;
if(PPointer1==NULL)
return 1;
else
{
pointer=PPointer1;
while(pointer!=NULL)
{
if(pointer-> x==a&&pointer-> y==b&&pointer-> state==n)
end
end
end
if t==1
if u==0
s(i+1, = s(i, + (-1)^i * d(j, ;
c(i+1, = d(j, ;
return;
elseif u==1
continue;
end
else continue;
end
end;
if t==0
disp('No Result');
return;
PPointer1=NULL;
PPointer2=NULL;
}
pointer=PPointer1;
while(pointer-> next!=PPointer2)
pointer=pointer-> next;
free(PPointer2);
PPointer2=pointer;
PPointer2-> next=NULL;
{
PPointer1=newnode;
PPointer2=newnode;
}
else
{
PPointer2-> next=newnode;
PPointer2=newnode;
}
}
void Pop() /*弹栈*/
{
link pointer;
if(PPointer1==PPointer2)
{
free(PPointer1);
LD=0; %允许的决策集合D与个数LD
for i=0:n
for j=0:m
x=1; y=size(A,1);
m=size(v,1);
T=zeros(m,1);
T=T.^-1;
lmd=T;
P=T;
S=zeros(m,1);
S(x)=1;
P(x)=0; lmd(x)=0;
k=x;
while(1)
a=find(S==0);
aa=find(S==1);
if size(aa,1)==m
{
switch(n)
{
case 1:
{
if(a==3)
{
Push(a,b,n);
return 1;
}
else if(a==0)
{
Push(a,b,n);
return 1;
}
else if(a==b)
{
Push(a,b,n);
return 1;
}
else return 0;
}
case 0:
{
if(a==3)
end
end
j=nn;
end;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 将状态向量生成抽象矩阵
k=(1/2)*size(A,1);
CX=zeros(2*k,2*k);
a=size(d,1);
for i=1:2*k
for j=1:a
jc=jc+2; % 由于生成两个决策向量，则jc要向下移动两个； end
end
j=0;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 状态数组生成
kx=1; % 状态向量放在A矩阵中，生成方法同矩阵生成；
for i=n:-1:0
for j=nn:-1:0