人狼羊c語言

❶ c語言一個人帶著一隻羊,一顆白菜，一條狼想過河，假設他每次只能帶一隻羊，一隻狼或一顆白菜過河，並限

這個題目是不是哪裡出了問題？
按照這個要求，不論先帶哪個過河都不行啊，剩下的兩個總是不能單獨在一起的啊。。。

❷ 數學建模 人狼羊菜問題

1。先送羊，回，再送狼，帶回羊，送菜，回，再送一次羊！

2。先送羊，回，再送菜，帶回羊，送狼，回，再送一次羊！

❸ C語言編程！！！羊，狼，白菜，過河方法~！~~@。@

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STEP 20

//index: 0 - 狼，1－羊，2－菜，3－農夫，value：0－本岸，1－對岸
int a[MAX_STEP][4];
int b[MAX_STEP];

char *name[] =
{
"空手",
"帶狼",
"帶羊",
"帶菜"
};

void search(int iStep)
{
int i;
if (a[iStep][0] + a[iStep][1] + a[iStep][2] + a[iStep][3] == 4)
{
for (i = 0; i < iStep; i++)
{
if (a[i][3] == 0)
{
printf("%s到對岸\n", name[b[i] + 1]);
}
else
{
printf("%s回本岸\n", name[b[i] + 1]);
}
}
printf("\n");
return;
}
for (i = 0; i < iStep; i++)
{
if (memcmp(a[i], a[iStep], sizeof(a[i])) == 0)
{
return;
}
}
if (a[iStep][1] != a[iStep][3] && (a[iStep][2] == a[iStep][1] || a[iStep][0] == a[iStep][1]))
{
return;
}
for (i = -1; i <= 2; i++)
{
b[iStep] = i;
memcpy(a[iStep + 1], a[iStep], sizeof(a[iStep + 1]));
a[iStep + 1][3] = 1 - a[iStep + 1][3];
if (i == -1)
{
search(iStep + 1);
}
else if (a[iStep][i] == a[iStep][3])
{
a[iStep + 1][i] = a[iStep + 1][3];
search(iStep + 1);
}
}
}

int main()
{
search(0);
return 0;
}

❹ 人 狼 羊 菜 過河 perl

#include <iostream>
using namespace std;

const int VEGET = 1;
const int SHEEP = VEGET << 1;
const int WOLF = SHEEP << 1;
const int FARMER = WOLF << 1;

bool used[20]; // 狀態是否到達過的標志
int bfs[1000]; // 廣度優先搜索時存放狀態
int pre[1000]; // 父結點

inline int SetBit( int x, int pos )
{
return x | pos;
}

inline int DelBit( int x, int pos )
{
return x & ~pos;
}

// 檢查狀態x是否合法
inline bool IsLegal( int x )
{
if ( x & FARMER ) // 如果農夫在的話
{
// 菜和羊都不在，或是羊和狼都不在是不可以的
if ( ((x&(VEGET|SHEEP))==0) || ((x&(SHEEP|WOLF))==0) )
{
return false;
}
} else // 如果農夫不在的話
{
// 菜和羊都在，或是羊和狼都在是不可以的
if ( ((x&(VEGET|SHEEP))==(VEGET|SHEEP)) || ((x&(SHEEP|WOLF))==(SHEEP|WOLF)) )
{
return false;
}
}

// 否則，是合法的狀態
return true;
}

// 廣度優先搜索
int BFSSearch()
{
int i;
int x;
int iLeft = -1;
int iRight = 1;
bfs[0] = FARMER|WOLF|SHEEP|VEGET;
used[ bfs[0] ] = true;

while( ++iLeft<iRight ) // 只要狀態沒有結束
{
if ( bfs[iLeft] & FARMER ) // 這里有農夫
{
x = DelBit(bfs[iLeft],FARMER);
if ( !used[x] && IsLegal(x) ) // 農夫什麼都不帶過去
{
pre[iRight] = iLeft;
bfs[iRight] = x;
used[x] = true;
iRight++;
}

for ( i=0; i<3; i++ ) // 帶一樣東西過去
{
if ( (bfs[iLeft]&(1<<i)) == 0 ) // 如果要帶過去的不在這邊
{
continue;
}

x = DelBit(bfs[iLeft],FARMER|(1<<i) );
if ( !used[x] && IsLegal(x) ) // 狀態不存在且可行
{
pre[iRight] = iLeft;
bfs[iRight] = x;
used[x] = true;

if( x == 0 ) // 如果找到目標，返回
{
return iRight;
}

iRight++;
}
}
} else
{
x = SetBit(bfs[iLeft],FARMER);
if ( !used[x] && IsLegal(x) ) // 農夫什麼都不帶回來
{
pre[iRight] = iLeft;
bfs[iRight] = x;
used[x] = true;
iRight++;
}

for ( i=0; i<3; i++ ) // 帶一樣東西回來
{
if ( bfs[iLeft]&(1<<i) ) // 如果要帶回來的已經在這邊
{
continue;
}

x = SetBit(bfs[iLeft],FARMER|(1<<i) );
if ( !used[x] && IsLegal(x) ) // 狀態不存在且可行
{
pre[iRight] = iLeft;
bfs[iRight] = x;
used[x] = true;
if( x == 0 )
{
return iRight;
}
iRight++;
}
}
}
}

return -1;
}

// 遞歸輸出結果
void OutputSolution( int iRet )
{
if ( pre[iRet] != -1 )
{
OutputSolution( pre[iRet] );
}

cout << " --> ";
if ( bfs[iRet]&FARMER )
{
cout << "Farmer ";
} else
{
cout << " ";
}

if ( bfs[iRet]&WOLF )
{
cout << "Wolf ";
} else
{
cout << " ";
}

if ( bfs[iRet]&SHEEP )
{
cout << "Sheep ";
} else
{
cout << " ";
}

if ( bfs[iRet]&VEGET )
{
cout << "Vegetable ";
} else
{
cout << " ";
}

cout << endl;
}

int main(int argc, char* argv[])
{
memset( used, 0, sizeof(used) );
memset( pre, 0xff, sizeof(pre) );

int iRet = BFSSearch();
if ( iRet == -1 )
{
cout << "No solution!" << endl;
} else
{
OutputSolution( iRet );
}
return 0;
}

❺ 求狼羊白菜過河的C語言編程題詳解。希望不要用數組解決。

按照你的要求，不使用數組。

我的思路，起點貨物狼、羊、白菜，人一直在開船，通過遞歸函數，每次靠岸嘗試裝卸貨方案，直到找滿足條件的方案。將可行方案存放在結構鏈表中形成操作流水列印。

人狼羊菜存儲方式模擬4位2進制，用1111表示，每位表示一個單位，1存在，0不存在。

#include<stdio.h>
#include<malloc.h>
typedefenum{false,true}bool;
typedefstructopRecord//用結構鏈表記錄操作流水
{
intp1_take;//p1載貨值
intp1_goAd;//p1卸貨值
intp2_take;//p2載貨值
intp2_goAd;//p2卸貨值
intcen;//遞歸層號
structopRecord*next;
}OPR;
OPR*oprHead;
OPR*oprTail;
char*getName(intb);//獲取對應名稱
intbeEaten(intp1,intp2);//檢查是否發生被吃事件，發生返回1，未發生返回0
inttoShip(int*p1,int*p2,int*ship,boolf);//遞歸函數：上船人及任意一組合，返回狀態，1：方案可行；0：方案不可行
intgetFist(intpn);//獲取物品組合中第一個
voidaddLog(intp1_take,intp1_goAd,intp2_take,intp2_goAd,intcen);//將有效操作添加進日誌,cen相同，將視為修改覆蓋
voidprintfLog();//列印操作流水
OPR*findLogBycen(intcen);//通過cen查找流水。有返回節點指針。無返回NULL

intcount=1;
intflag=0;//標識變數=1成立；=0不成立
intcen=0;
intmain()
{
intp1=111,ship=1000,p2=0000;//p1,p2分別表示兩岸，4位數每一位分別表示人狼羊菜，位數值1表示存在，0表示不存在
oprHead=(OPR*)malloc(sizeof(OPR));
oprHead->next=NULL;
oprTail=NULL;
printf("河岸有人、狼、羊、白菜要過河,船每次載人及一物，為避免人上船後狼吃羊或羊吃菜 開始生成方案: ");
if(toShip(&p1,&p2,&ship,0))
{
printf(" 開始生成結果報告： ");
printfLog();
}
else
printf("無可行方案！！ ");
return0;
}
voidaddLog(intp1_take,intp1_goAd,intp2_take,intp2_goAd,intcen)//將有效操作添加進日誌,cen相同，將視為修改覆蓋,
{
OPR*oprNew=findLogBycen(cen);
if(oprNew==NULL)//通過查找。確認無記錄，新增記錄
{
oprNew=(OPR*)malloc(sizeof(OPR));
oprNew->p1_take=p1_take;
oprNew->p1_goAd=p1_goAd;
oprNew->p2_take=p2_take;
oprNew->p2_goAd=p2_goAd;
oprNew->cen=cen;
oprNew->next=NULL;
if(oprHead->next==NULL)
oprHead->next=oprNew;
else
oprTail->next=oprNew;
oprTail=oprNew;
}
else//查找發現已有記錄，修改
{
oprNew->p1_take=p1_take;
oprNew->p1_goAd=p1_goAd;
oprNew->p2_take=p2_take;
oprNew->p2_goAd=p2_goAd;
}
}
OPR*findLogBycen(intcen)//通過cen查找流水。有返回節點指針。無返回NULL
{
OPR*headSave=oprHead;
while(headSave->next!=NULL)
{
if(headSave->next->cen==cen)
returnheadSave->next;
headSave=headSave->next;
}
returnNULL;
}
voidprintfLog()//列印操作流水
{
OPR*headSave=oprHead;
intp1_take,p1_goAd,p2_take,p2_goAd,cen,p1TOp2,p2TOp1;
while(headSave->next!=NULL)
{
p1_take=headSave->next->p1_take;
p1_goAd=headSave->next->p1_goAd;
p2_take=headSave->next->p2_take;
p2_goAd=headSave->next->p2_goAd;
cen=headSave->next->cen;
if(p1_take>0||p1_goAd>0)
p1TOp2=1;
else
p1TOp2=0;
if(p2_take>0||p2_goAd>0)
p2TOp1=1;
else
p2TOp1=0;
printf("操作流水%2d:",cen);
printf("%s%s",p1TOp2>0?"從p1":"",p2TOp1>0?"從p2":"");
printf("%s%s",p1_goAd>0?getName(p1_goAd):"",p1_goAd>0?"下船":"");
printf("%s%s",p1_take>0?getName(p1_take):"",p1_take>0?"上船":"");
printf("%s%s",p2_goAd>0?getName(p2_goAd):"",p2_goAd>0?"下船":"");
printf("%s%s",p2_take>0?getName(p2_take):"",p2_take>0?"上船":"");

if(headSave->next->next!=NULL)
printf("。之後行駛方向：%s%s ",p1TOp2>0?"p1->p2":"",p2TOp1>0?"p1<-p2":"");
else
printf(" ");
headSave=headSave->next;
}
}
char*getName(intb)//獲取對應名稱
{
if(b==1000)
return"人";
elseif(b==100)
return"狼";
elseif(b==10)
return"羊";
elseif(b==1)
return"菜";
return"";
}
inttoShip(int*p1,int*p2,int*ship,boolf)//遞歸函數：上船人及任意一組合；lastTake:上一次承載物體，首次調用傳0；f=0：p1->p2方向;1:反向。返回狀態，1：方案可行；0：方案不可行;
{
inttake=-1,goAd,gdflag=1,cenSave;//take:上船物體。goAd：下船物體。gdflag:標識變數，p2判斷能否直接下船,1能0不能
cenSave=++cen;
while(1)
{
goAd=*ship-1000;
if(f==0)//准備p1往p2
{
if(take==-1)
take=getFist(*p1);
*p1-=take;
*p1+=goAd;
gdflag=1;//標識置1，等到p2首先嘗試直接卸貨
}
else//准備p2往p1
{
if(take==-1&&gdflag==0)
{
take=getFist(*p2);
printf("開始嘗試替換貨物： ");
}
if(gdflag==1)//如果p2可以直接卸貨
*p2+=goAd;
else//如果不能直接卸貨，嘗試帶走一個同時卸貨
{
*p2-=take;
*p2+=goAd;
}
}
printf("遞歸層級%d：假設%s從%s上船。%s下船，%s方向行駛。 ",cenSave,take>0?getName(take):"無貨物",f==0?"p1":"p2",goAd!=0?getName(goAd):"無貨物",f==0?"p1往p2":"p2往p1");

if(beEaten(*p1,*p2))//如果發生被吃，假設失敗，還原數據，選擇下一假設
{
if(f==0)
{
*p1+=take;
*p1-=goAd;
}
else
{
if(gdflag==1)//p2點確定不能直接卸貨，還原數據，標識置0
{
printf("----不能直接卸貨，貨物%s回到船上。",getName(goAd));
*p2-=goAd;
gdflag=0;
continue;
}
else//不能直接卸貨並嘗試替換貨物失敗，選擇下一個貨物替換
{
*p2+=take;
*p2-=goAd;
}
}
if(take==1)
{
printf("本次靠岸無可行的裝卸方案，返回層級%d！ ",cenSave-1);
return0;
}
take=take/10;//嘗試選擇下一個貨物
continue;
}
else
{

if(f==1&&gdflag==1)//p2直接卸貨假設成立船清空
*ship=1000;
else
*ship=1000+take;//換貨假設成立貨物裝船
if(*p1==0)//如果已經完全轉移
{
printf("所有貨物過河成功！！ ");
return1;
}
if(f==0)
addLog(take,goAd,0,0,cenSave);//生成流水日誌
else
addLog(0,0,take,goAd,cenSave);//生成流水日誌
if(toShip(p1,p2,ship,f==0?1:0))
{
return1;
}
else//由於下級失敗，本回合重新選擇
{
gdflag=0;
continue;
}
}
}
}
intgetFist(intpn)//獲取物品組合中第一個
{
inti,count=0;
while(1)//上船物體從岸上第一個物體開始選擇
{
if(pn<=1)
break;
pn=pn/10;
count++;
}
for(i=0;i<count;i++)
pn=pn*10;
returnpn;
}
intbeEaten(intp1,intp2)//檢查是否發生被吃事件，發生返回1，未發生返回0
{
intren=0;
if(p1==110&&++ren==1)
printf("----河岸p1狼把羊吃了！重新選擇 ");
if(p2==110&&++ren==1)
printf("----河岸p2狼把羊吃了！重新選擇 ");
if(p1==11&&++ren==1)
printf("----河岸p1羊把菜吃了！重新選擇 ");
if(p2==11&&++ren==1)
printf("----河岸p2羊把菜吃了！重新選擇 ");
returnren;
}

❻ 關於人狼羊白菜過河的c語言編程題

先把羊運過去，再把草運過去，把羊接回來，把狼運過去，回去再把羊運過去

❼ 請用C語言編寫：

我用一個類似的不過我沒看明白
#include <stdio.h>
#include <stdlib.h>
#define maxloop 100 //最大層數，對於不同的擴展方法自動調整取值
#define pristnum 3
#define slavenum 3
struct SPQ
{
int sr,pr; //船運行一個來回後河右岸的野人、傳教士的人數
int sl,pl; //船運行一個來回後河左岸的野人、傳教士的人數
int ssr,spr; //回來（由左向右時）船上的人數
int sst,spt; //去時（由右向左時）船上的人數
int loop; //本結點所在的層數
struct SPQ *upnode ,*nextnode;//本結點的父結點和同層的下一個結點的地址
}spq;
int loopnum;//記錄總的擴展次數
int openednum;//記錄已擴展節點個數
int unopenednum;//記錄待擴展節點個數
int resultnum;
struct SPQ *opened;
struct SPQ *oend;
struct SPQ *unopened;
struct SPQ *uend;
struct SPQ *result;
void initiate();
void releasemem();
void showresult();
void addtoopened(struct SPQ *ntx);
int search();
void goon();
int stretch(struct SPQ* ntx);
void recorder();
void main()
{
int flag; //標記擴展是否成功
for( ; ; )
{
initiate();
flag = search ();
if(flag == 1)
{
recorder();
releasemem();
showresult();
goon();
}
else
{
printf("無法找到符合條件的解");
releasemem();
goon();
}
}
}
void initiate()
{
int x;
char choice;
uend = unopened = (struct SPQ*)malloc(sizeof(spq));
if(uend==NULL)
{
printf("\n內存不夠！\n");
exit(0);
}
unopenednum=1;
openednum=0;
unopened -> upnode = unopened; //保存父結點的地址以成鏈表
unopened -> nextnode = unopened;
unopened -> sr = slavenum;
unopened -> pr = pristnum;
unopened -> sl = 0;
unopened -> pl = 0;
unopened -> sst = 0;
unopened -> spt = 0;
unopened -> ssr = 0;
unopened -> spr = 0;
unopened -> loop = 0;
printf("題目：設有n個傳教士和m個野人來到河邊，打算乘一隻船從右岸到左岸去。\n");
printf("該船的負載能力為兩人。在任何時候，如果野人人數超過傳教士人數，野人\n");
printf("就會把傳教士吃掉。他們怎樣才能用這條船安全的把所有人都渡過河去?\n");
printf("\n默認的n、m值皆為3\n");
for(;;)
{
printf("\n是否修改？(Y/N)");
scanf("%s",&choice);
choice=toupper(choice);
if(choice=='Y')
{
printf("\n請輸入傳教士人數");
for(;;)
{
scanf("%d",&x);
if(x>0)
{
unopened -> pr = x;
break;
}
else printf("\n輸入值應大於0！\n請重新輸入");
}
printf("\n請輸入野人人數");
for(;;)
{
scanf("%d",&x);
if(x>0)
{
unopened -> sr = x;
break;
}
else printf("\n輸入值應大於0！\n請重新輸入");
}
break;
}
if(choice=='N')break;
}

}
int search()
{
int flag;
struct SPQ *ntx; //提供將要擴展的結點的指針
for( ; ; )
{
ntx = unopened; //從待擴展鏈表中提取最前面的一個
if(ntx->loop == maxloop)
return 0;
addtoopened(ntx); //將ntx加入已擴展鏈表，並將這個節點從待擴展鏈表中去掉
flag = stretch(ntx); //對ntx進行擴展,返回-1,0,1
if(flag == 1)
return 1;
}
}
int stretch(struct SPQ *ntx)
{
int fsr , fpr ; //在右岸上的人數
int fsl , fpl ; //在左岸上的人數
int sst , spt ; //出發時在船上的人數
int ssr , spr ; //返回時船上的人數
struct SPQ *newnode;
for (sst = 0 ; sst <= 2 ; sst++) //討論不同的可能性並判斷是否符合條件
{
fsr = ntx -> sr;
fpr = ntx -> pr;
fsl = ntx -> sl;
fpl = ntx -> pl;
if ((sst <= fsr) && (( 2 - sst) <= fpr))//滿足人數限制
{
spt = 2 - sst;
fsr = fsr - sst;
fpr = fpr - spt;
if((fpr == 0) && (fsr == 0))//搜索成功
{
newnode = (struct SPQ*) malloc (sizeof(spq));
if(newnode==NULL)
{
printf("\n內存不夠！\n");
exit(0);
}
newnode -> upnode = ntx; //保存父結點的地址以成鏈表
newnode -> nextnode = NULL;
newnode -> sr = 0;
newnode -> pr = 0;
newnode -> sl = opened -> sr;
newnode -> pl = opened -> pr;
newnode -> sst = sst;
newnode -> spt = spt;
newnode -> ssr = 0;
newnode -> spr = 0;
newnode -> loop = ntx -> loop + 1;
oend -> nextnode = newnode;
oend = newnode;
openednum++;
return 1;
}
else if ((fpr - fsr) * fpr >= 0) //判斷是否滿足傳教士人數必須大於或等於野人人數
{
fsl = fsl + sst;
fpl = fpl + spt;
for (ssr = 0 ; ssr <= 1 ; ssr++) //返回
{
int ffsl , ffpl;
if ((ssr <= fsl) && ((1 - ssr) <= fpl))
{
spr = 1 - ssr;
ffsl = fsl - ssr;
ffpl = fpl - spr;
if ((ffpl - ffsl) * ffpl >= 0)
{ //若符合條件則分配內存並付值
int ffsr , ffpr;
ffsr = fsr + ssr;
ffpr = fpr + spr;
newnode = (struct SPQ*) malloc (sizeof(spq));
if(newnode==NULL)
{
printf("\n內存不夠！\n");
exit(0);
}
newnode -> upnode = ntx; //保存父結點的地址以成鏈表
newnode -> sr = ffsr;
newnode -> pr = ffpr;
newnode -> sl = ffsl;
newnode -> pl = ffpl;
newnode -> sst = sst;
newnode -> spt = spt;
newnode -> ssr = ssr;
newnode -> spr = spr;
newnode -> loop = ntx -> loop + 1;
uend -> nextnode = newnode;
uend = newnode;
unopenednum++;

}
}
}
}
}
}
return 0;
}
void addtoopened(struct SPQ *ntx)
{
unopened = unopened -> nextnode;
unopenednum--;
if (openednum == 0 )
oend = opened = ntx;
oend -> nextnode = ntx;
oend = ntx;
openednum++;
}
void recorder()
{
int i , loop;
struct SPQ *newnode;
struct SPQ *ntx;
loop = oend -> loop;
ntx = oend;
resultnum = 0;
for( i = 0 ; i <= loop ; i++ )
{
newnode = (struct SPQ*) malloc (sizeof(spq));
if(newnode==NULL)
{
printf("\n內存不夠！\n");
exit(0);
}
newnode -> sr = ntx -> sr;
newnode -> pr = ntx -> pr;
newnode -> sl = ntx -> sl;
newnode -> pl = ntx -> pl;
newnode -> sst = ntx -> sst;
newnode -> spt = ntx -> spt;
newnode -> ssr = ntx -> ssr;
newnode -> spr = ntx -> spr;
newnode -> nextnode = NULL;
ntx = ntx -> upnode;
if(i == 0)
result = newnode;
newnode -> nextnode = result;
result = newnode;
resultnum++;
}
}
void releasemem()
{
int i;
struct SPQ* nodefree;
for ( i = 1 ; i < openednum ; i++ )
{
nodefree = opened;
opened = opened -> nextnode;
free(nodefree);
}
for ( i = 0 ; i < unopenednum ; i++ )
{
nodefree = unopened;
unopened = unopened -> nextnode;
free(nodefree);
}
}
void showresult()
{
int i;
int fsr , fpr ; //在右岸上的人數
int fsl , fpl ; //在左岸上的人數
struct SPQ* nodefree;
printf("%d個傳教士",result -> pr);
printf("%d個野人",result -> sr);
printf("%d個傳教士",result -> pl);
printf("%d個野人",result -> sl);
for ( i = 1 ; i < resultnum ; i++ )
{
nodefree = result;
result = result -> nextnode;
free(nodefree);
printf("\n\n\t左岸人數 船上人數及方向 右岸人數\n");
printf("第%d輪\n",i);
fpl = result -> pl - result -> spt + result -> spr;
fpr = result -> pr - result -> spr;
fsl = result -> sl - result -> sst + result -> ssr;
fsr = result -> sr - result -> ssr;
printf("傳教士%8d%8d\t<-\t%8d\n",fpl,result -> spt,fpr);
printf("野 人%8d%8d\t<-\t%8d\n",fsl,result -> sst,fsr);
printf("傳教士%8d%8d\t->\t%8d\n",result -> pl,result -> spr,result -> pr - result -> spr);
printf("野 人%8d%8d\t->\t%8d\n",result -> sl,result -> ssr,result -> sr - result -> ssr);
}
printf("\n全體傳教士和野人全部到達對岸");
free(result);
}
void goon()
{
char choice;
for(;;)
{
printf("是否繼續？(Y/N)\n");
scanf ("%s" , &choice);
choice=toupper(choice);
if(choice=='Y')break;
if(choice=='N')exit(0);
}
}

❽ C語言編程！！！羊，狼，白菜，過河方法~！

過河的方法用語言表述是這樣的：
第一次帶羊過去，第二次帶白菜過去同時帶羊回來，第三次帶狼過去，第四次帶羊過去

❾ 有沒有電腦編程高手幫我編個C++的程序，題目如下： 一個人帶有一隻羊, 一框菜和一隻狼要過河, 但船上除了載

#include <stdio.h>
#include <string.h>

int visited[2][2][2][2];

int dfs(int p, int v, int s, int w)
{
if(visited[p][v][s][w]>=0)
return visited[p][v][s][w];
visited[p][v][s][w] = 0;
if(v==s&&s!=p)
return 0;
if(w==s&&w!=p)
return 0;
if(p==0&&v==0&&s==0&&w==0)
return 1;
if(dfs(1-p,v,s,w))
{
puts("人 自己到對岸");
visited[p][v][s][w] = 1;
return 1;
}
if(v==p&&dfs(1-p,1-v,s,w))
{
puts("人 和 菜 到對岸");
visited[p][v][s][w] = 1;
return 1;
}
if(w==p&&dfs(1-p,v,s,1-w))
{
puts("人 和 狼 到對岸");
visited[p][v][s][w] = 1;
return 1;
}
if(s==p&&dfs(1-p,v,1-s,w))
{
puts("人 和 羊 到對岸");
visited[p][v][s][w] = 1;
return 1;
}
return 0;
}

int main()
{
memset(visited,-1,sizeof(visited));
dfs(1,1,1,1);
return 0;
}

輸出:
人 和 羊 到對岸
人 自己到對岸
人 和 狼 到對岸
人 和 羊 到對岸
人 和 菜 到對岸
人 自己到對岸
人 和 羊 到對岸
#include <stdio.h> #include <string.h> int visited[2][2][2][2]; int dfs(int p, int v, int s, int w) { if(visited[p][v][s][w]>=0) return visited[p][v][s][w]; visited[p][v][s][w] = 0; if(v==s&&s!=p) return 0; if(w==s&&w!=p) return 0; if(p==0&&v==0&&s==0&&w==0) return 1; if(dfs(1-p,v,s,w)) { puts("人 自己到對岸"); visited[p][v][s][w] = 1; return 1; } if(v==p&&dfs(1-p,1-v,s,w)) { puts("人 和 菜 到對岸"); visited[p][v][s][w] = 1; return 1; } if(w==p&&dfs(1-p,v,s,1-w)) { puts("人 和 狼 到對岸"); visited[p][v][s][w] = 1; return 1; } if(s==p&&dfs(1-p,v,1-s,w)) { puts("人 和 羊 到對岸"); visited[p][v][s][w] = 1; return 1; } return 0; } int main() { memset(visited,-1,sizeof(visited)); dfs(1,1,1,1); return 0; }

❿ 人狼羊草過河問題 船需人劃,最多載一物.試安排他們過河

設目的地為南 另一端為北
先把羊從北岸運到南岸,此時北岸剩狼和草,
然後人自行駕船回北岸,將草運裝船運到南岸
到南岸之後將草卸下,載上羊返回北岸
到北岸卸下羊 裝上狼,將狼載上運到南岸
到南岸卸下,此時南岸剩狼和草
空載駕船到北岸 裝上羊 返回南岸