你把问题看简单了。你的程序有几个问题：
int boatf(int im,int ic,int ii)在这个函数中改变的im和ic的值只是改变的两个临时变量的值，并没有改变全局变量im和ic的值。你可以把前两个参数去掉。
还有，你的for循环并不是可以正确遍历所有情况的。
我写了一个程序，tc2.0通过了。在执行到第145种方案时成功。
程序中case的几个带缺顺序请不要任意改动，因为ltor和rtol函数中他们有对应关系。
本题目一共有5的13次方种方案，我的算法能排除很多非法方案。当然，我的算法不是最好的，希望高手能提供更高效的算法。
做这个程序累坏了我几万个脑细胞，楼主给多加点分吧！谢谢了！
#include<stdio.h>/*定义N为所用步数，先定为6步*/
#define N 6
/*分别为左岸和右岸的im，ic数*/
int iml, imr, icl, icr
/*定义sn为左右岸的移动的每一步*/
int sn[N+N-1] = {0}
void ltor(int i)
/* left to right */
{
switch (i) {
case 0:
iml--
icl--
printf("%dim %dic | im + ic --> | %dim %dic\n", iml, icl, imr, icr)
imr++
icr++
break
case 1:
iml -= 2
printf("%dim %dic | im + im --> | %dim %dic\n", iml, icl, imr, icr)
imr += 2
break
case 2:
icl -= 2
printf("%dim %dic | ic + ic --> | %dim %dic\n", iml, 蠢轿辩icl, imr, icr)
icr += 2
break
case 3:
iml--
printf("%dim %dic | im --> | %dim %dic\n", iml, icl, imr, icr)
imr++
break
case 4:
icl--
printf("%dim %dic | ic --> | %dim %dic\n", iml, icl, imr, icr)
icr++
break
default:
printf("error\n")
}
}
void rtol(int i)
/* right to left */
{
switch (i) {
case 0:
imr--
icr--
printf("%dim %dic | <-- im + ic | %dim %dic\n", iml, icl, imr, icr)
iml++
icl++
帆樱 break
case 1:
imr -= 2
printf("%dim %dic | <-- im + im | %dim %dic\n", iml, icl, imr, icr)
iml += 2
break
case 2:
icr -= 2
printf("%dim %dic | <-- ic + ic | %dim %dic\n", iml, icl, imr, icr)
icl += 2
break
case 3:
imr--
printf("%dim %dic | <-- im | %dim %dic\n", iml, icl, imr, icr)
iml++
break
case 4:
icr--
printf("%dim %dic | <-- ic | %dim %dic\n", iml, icl, imr, icr)
icl++
break
default:
printf("error\n")
}
}
int set(int k)
/* set sn[i] */
{
int i
for (i = k + 1 i < N + N - 1 i++)
/* k 位之后的sn元素都赋值为零*/
sn[i] = 0
sn[k]++
/* k 位元素自加1*/
for (i = k i > 0 i--)
/* 每位元素超过4则置零，并向前一位进一*/
{
if (sn[i] > 4) {
sn[i] = 0
sn[i - 1]++
} else break
}
if (sn[0] > 5)
/*sn遍历一遍则返回0，否则返回1*/
return 0
else return 1
}
void restart(void)
/* restart the work */
{
imr = icr = 0
iml = icl = 3
}
void main() {
int i,
step,
found = 0
unsigned long n = 0
/* The NUM of the plans */
do {
i = 0
step = N - 1
n++
restart()
ltor(sn[i])
while ((step--) || !(iml == 0 && icl == 0)) {
i++
rtol(sn[i])
if (sn[i] == sn[i - 1]) {
printf("The %ldth plan to R is not perfect!\n", n)
break
}
if ((imr > 0 && imr < icr) || imr < 0 || icr < 0 || (iml > 0 && iml < icl) || iml < 0 || icl < 0) {
printf("The %ldth plan to R is fail!\n", n)
break
}
i++
ltor(sn[i])
if (sn[i] == sn[i - 1]) {
printf("The %ldth plan to R is not perfect!\n", n)
break
}
if ((imr > 0 && imr < icr) || imr < 0 || icr < 0 || (iml > 0 && iml < icl) || iml < 0 || icl < 0) {
printf("The %ldth plan to R is fail!\n", n)
break
}
}
if (iml == 0 && icl == 0) {
printf("The plan to Pass the river is success!\n")
getchar()
break
}
} while ( set ( i ))
}
本来没打算发出来。送你算了。下面的程序称得上perfect,程序在dev-c++下编译通过.
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define maxloop 100/* 最大层数，对于不同的扩展方法自动调整取值 */
#define pristnum 3 /*初始化时设定有3个野人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()
int main()
{
int flag /* 标记扩展是否成功 */
for( )
{
initiate()
flag = search ()
if(flag == 1)
{
recorder()
releasemem()
showresult()
goon()
}
else
{
printf("无法找到符合条件的解")
releasemem()
goon()
}
}
system("pause")
return 0
}
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)
}
}
有3个传教士和3个野人要过河，只有一艘船，这艘船每次只能载2个人过河，且无论哪边野人的数量大于传教士的数量时，野人就会段誉吃高铅掉传教士。怎样让他们都安全过河？C语言源代码：
#include <stdio.h>
#include <string.h>
#define STEP_MAX 20 //来回过河的次数
#define KIND_NUM 3 //每个种类的数量
#define BOAT_NUM 2 //船的载重量
typedef enum
{
BOAT_THIS,//船在本岸
BOAT_THAT,//船在对岸
} boat_t
typedef enum
{
ROAD_GO,//过河
ROAD_COME,//回来
} road_t
typedef struct
{
int ye//对岸野人数量
int man//对岸传教士数量
boat_t boat//船是否在对岸
} state_t//一种局面
typedef struct
{
int ye//野人过河数量
int man//传教士过河的数量
road_t road//回来或过河
} step_t//一个步骤
state_t states[STEP_MAX]={0}
step_t steps[STEP_MAX]={0}
//判断所有的野人和传教士是否都到了对岸
bool final(state_t s)
{
const state_t cs=
{
KIND_NUM,
KIND_NUM,
BOAT_THAT
}
if(memcmp(&cs,&s,sizeof(state_t))==0)
{
return true
}
return false
}
//是否会发生野人杀传教士
bool bad(state_t s)
{
if(((KIND_NUM-s.ye)>(KIND_NUM-s.man) &&(KIND_NUM-s.man)>0)
||(s.ye>s.man &&s.man>0))
{
return true
}
return false
}
//第n种局面是否跟前面的相重复
bool repeat(state_t s[],int n)
{
int i
for (i = 0i <ni++)
{//已经有这种情况了
if (memcmp(&states[i], &states[n], sizeof(states[i])) == 0)
{
return true
}
}
return false
}
void output(step_t steps[STEP_MAX],int n)
{
char *kinds[KIND_NUM]={"野人","传教士"}
char *routine[2]={"过河.","回来."}
int i
for (i = 0i <ni++)
{
if((steps[i].ye * steps[i].man)>0)
{
printf("%d个%s和%d个%s%s\n",steps[i].ye,kinds[0],
steps[i].man,kinds[1],routine[steps[i].road])
}
else if(steps[i].ye>0)
{
printf("%d个%s%s\n",steps[i].ye,kinds[0],
routine[steps[i].road])
}
else if(steps[i].man>0)
{
printf("%d个%s%s\n",steps[i].man,kinds[1],
routine[steps[i].road])
}
}
printf("\n")
}
//搜索过河方案(n表示过河次数)
void search(int n)
{
int i,j
if(n>STEP_MAX)
{//步数限制太少了
printf("Step Overflow!")
return
}
if(final(states[n]))
{//都到对岸了
output(steps,n)
return
}
if(bad(states[n]))
{//发生了野人杀传教士了
return
}
if(repeat(states,n))
{//与前面的局面相重复了
return
}
if(states[n].boat==BOAT_THIS)
{//船在本戚燃好岸
for (i = 0i <= BOAT_NUM &&i<=(KIND_NUM-states[n].ye)i++)
for (j = 0j <= BOAT_NUM-i &&j<=(KIND_NUM-states[n].man)j++)
{
if(i==0 &&j==0)
{
continue
}
steps[n].ye=i
steps[n].man=j
steps[n].road=ROAD_GO
memcpy(&states[n+1], &states[n], sizeof(state_t))
states[n+1].ye+=i
states[n+1].man+=j
states[n+1].boat=BOAT_THAT
search(n+1)
}
}
else
{
for (i = 0i <= BOAT_NUM &&i<=states[n].yei++)
for (j = 0j <= BOAT_NUM-i &&j<=states[n].manj++)
{
if(i==0 &&j==0)
{
continue
}
steps[n].ye=i
steps[n].man=j
steps[n].road=ROAD_COME
memcpy(&states[n+1], &states[n], sizeof(state_t))
states[n+1].ye-=i
states[n+1].man-=j
states[n+1].boat=BOAT_THIS
search(n+1)
}
}
}
int main()
{
search(0)
return 0
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）