出个题,农夫带着狼、羊、白菜过河!大家进来看看

11 楼

brien [专家分：0] 发布于 2004-09-21 11:23:00

#include <iostream.h>
struct Condition {
    int farmer;
    int wolf;
    int sheep;
    int cabbage;
};
struct Condition conditions [20];
char* action[100];
void takeWolfOver(int i)
{
    action[i] = "把狼带过河.";
    conditions[i+1].wolf=1;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void takeWolfBack(int i)
{
    action[i] = "把狼带回来.";
    conditions[i+1].wolf=0;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void takeSheepOver(int i)
{
    action[i] = "把羊带过河.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=1;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void takeSheepBack(int i)
{
    action[i] = "把羊带回来.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=0;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void takeCabbageOver(int i)
{
    action[i] = "把菜带过去.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=1;
}
void takeCabbageBack(int i)
{
    action[i] = "把菜带回来.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=0;
}
void getOverBarely(int i)
{
    action[i] = "空手过河.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void getBackBarely(int i)
{
   action[i] = "空手返回.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void showSolution(int i)
{
    int c;
    cout<<"可以这样安排："<<endl;
    for(c=0; c<i; c++)
    {
      cout<<c+1<<action[c]<<endl;
    }
      cout<<"OK，任务完成了！"<<endl;
    }
void doStep(int i)
{
    int c;
    int j;
    if(conditions[i].farmer==1&&
        conditions[i].wolf==1&&
        conditions[i].sheep==1&&
        conditions[i].cabbage==1)
    {
        //OK，所有的东东都安全过河了！
        showSolution(i);
        return;
    }
    //check for lose.
    if(
        (conditions[i].farmer!=conditions[i].wolf && conditions[i].wolf==conditions[i].sheep)
        ||
        (conditions[i].farmer!=conditions[i].sheep && conditions[i].sheep==conditions[i].cabbage)
    )
    {
        //有问题，狼会吃掉羊，或羊会吃掉菜的！
        return;
    }
     for (c=0; c<i; c++)
    {
        if(conditions[c].farmer==conditions[i].farmer&&
            conditions[c].wolf==conditions[i].wolf&&
            conditions[c].sheep==conditions[i].sheep&&
            conditions[c].cabbage==conditions[i].cabbage)
        {
            //已经过河了，或是全部又返回.
            return;
        }
    }


    j=i+1;
    if(conditions[i].farmer==0)
    {
        conditions[j].farmer=1;

        getOverBarely(i);
        doStep(j);

        if(conditions[i].wolf==0)
        {
            takeWolfOver(i);
            doStep(j);
        }
        if(conditions[i].sheep==0)
        {
            takeSheepOver(i);
            doStep(j);
        }
        if(conditions[i].cabbage==0)
        {
            takeCabbageOver(i);
            doStep(j);
        }
    }
    else
    {
        conditions[j].farmer=0;

        getBackBarely(i);
        doStep(j);

        if(conditions[i].wolf==1)
        {
            takeWolfBack(i);
            doStep(j);
        }
        if(conditions[i].sheep==1)
        {
            takeSheepBack(i);
            doStep(j);
        }
        if(conditions[i].cabbage==1)
        {
            takeCabbageBack(i);
            doStep(j);
        }
    }
}
void main()
{
    cout<<"有一个农夫带一条狼、一只羊和一棵白菜过河. "<<endl;
    cout<<"如果没有农夫看管，则狼要吃羊，羊要吃白菜."<<endl;
    cout<<"但是船很小，只够农夫带一样东西过河。"<<endl;
    cout<<"问农夫该如何解此难题？"<<endl;
    conditions[0].farmer = 0;
    conditions[0].wolf   = 0;
    conditions[0].sheep  = 0;
    conditions[0].cabbage= 0;
    doStep(0);
}
这个算法也是别人想出来的，这是我的一个作业。

12 楼

混混兔 [专家分：1600] 发布于 2004-09-21 17:51:00

…………以前提过了，不过可以在回答一次
这个是一个图的应用
{狼、羊、白菜}，{狼、羊}，{羊、白菜}，{狼、白菜}，{狼}，{白菜}，{羊}，{}
从题目上可以推测出，岸边出现的情况，只能是上面的几种状态（我们叫状态节点）
，最后一个{}代表岸边为空。节点之间是有路径的比如：{狼、羊、白菜}可以转化为{狼、羊}，{羊、白菜}，{狼、白菜}中的一种，

整个题目就变成{狼、羊、白菜} -》？？？？ -》 {}
其中某些状态如 {狼、羊}，{羊、白菜}，这些状态为死亡或障碍节点
把某一状态节点能向其他状态节点发展，就设定有路
整个就变成{狼、羊、白菜}节点走到 {}节点的路径问题
其中要求不能重复节点（也就是重复状态），不能走到死亡节点上

也就是一个图的路径问题

13 楼

wangyang2486 [专家分：90] 发布于 2004-10-06 15:00:00

是不是狼不能和羊在一起，而羊不能和白菜在一起啊，如果在一起是不是会被吃掉的啊，等待回答[em12][em12][em12][em12][em12][em12][em12][em12][em12]
谢谢公孙成哥哥回答我，快哦！~！~~！~！~！~！~！~！~！~！~

14 楼

ddr400yk [专家分：820] 发布于 2004-10-06 19:36:00

这似乎是一道数学问题。

15 楼

小波波 [专家分：240] 发布于 2004-10-07 11:00:00

嗯我是这样想的
先是在河的左边，第一次把羊带过河右边在返回左边，再将狼或白菜中的一个带过河右边，过河后在将羊带回左过，然后再将狼和白菜留下的带过河，在返回去将羊渡过河右边去，就成功了
其中农夫略去不写
[em2][em3][em2][em3][em2][em3][em2][em3][em2][em3]

16 楼

公孙成 [专家分：1040] 发布于 2004-10-07 13:24:00

13楼的
你说的对
但如果有农夫看着就不会

17 楼

wangyang2486 [专家分：90] 发布于 2004-10-08 20:07:00

这是脑筋急转弯的题目啊
碰到很多的，只要弄清怎么带来带去，再编写出程序就好了
还有公孙哥哥帮我做下“各位兄弟姐妹们，帮我做下啊，我才垃圾水平”的标题进去的题目好吗
谢谢你了[em11][em11][em11][em11][em11][em11][em11]

18 楼

gugolqyda [专家分：0] 发布于 2006-05-10 08:50:00

#include <iostream.h>
struct Condition {
    int farmer;
    int wolf;
    int sheep;
    int cabbage;
};
struct Condition conditions [20];
char* action[100];
void takeWolfOver(int i)
{
    action[i] = "把狼带过河.";
    conditions[i+1].wolf=1;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void takeWolfBack(int i)
{
    action[i] = "把狼带回来.";
    conditions[i+1].wolf=0;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void takeSheepOver(int i)
{
    action[i] = "把羊带过河.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=1;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void takeSheepBack(int i)
{
    action[i] = "把羊带回来.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=0;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void takeCabbageOver(int i)
{
    action[i] = "把菜带过去.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=1;
}
void takeCabbageBack(int i)
{
    action[i] = "把菜带回来.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=0;
}
void getOverBarely(int i)
{
    action[i] = "空手过河.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void getBackBarely(int i)
{
   action[i] = "空手返回.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void showSolution(int i)
{
    int c;
    cout<<"可以这样安排："<<endl;
    for(c=0; c<i; c++)
    {
      cout<<c+1<<action[c]<<endl;
    }
      cout<<"OK，任务完成了！"<<endl;
    }
void doStep(int i)
{
    int c;
    int j;
    if(conditions[i].farmer==1&&
        conditions[i].wolf==1&&
        conditions[i].sheep==1&&
        conditions[i].cabbage==1)
    {
        //OK，所有的东东都安全过河了！
        showSolution(i);
        return;
    }
    //check for lose.
    if(
        (conditions[i].farmer!=conditions[i].wolf && conditions[i].wolf==conditions[i].sheep)
        ||
        (conditions[i].farmer!=conditions[i].sheep && conditions[i].sheep==conditions[i].cabbage)
    )
    {
        //有问题，狼会吃掉羊，或羊会吃掉菜的！
        return;
    }
     for (c=0; c<i; c++)
    {
        if(conditions[c].farmer==conditions[i].farmer&&
            conditions[c].wolf==conditions[i].wolf&&
            conditions[c].sheep==conditions[i].sheep&&
            conditions[c].cabbage==conditions[i].cabbage)
        {
            //已经过河了，或是全部又返回.
            return;
        }
    }


    j=i+1;
    if(conditions[i].farmer==0)
    {
        conditions[j].farmer=1;

        getOverBarely(i);
        doStep(j);

        if(conditions[i].wolf==0)
        {
            takeWolfOver(i);
            doStep(j);
        }
        if(conditions[i].sheep==0)
        {
            takeSheepOver(i);
            doStep(j);
        }
        if(conditions[i].cabbage==0)
        {
            takeCabbageOver(i);
            doStep(j);
        }
    }
    else
    {
        conditions[j].farmer=0;

        getBackBarely(i);
        doStep(j);

        if(conditions[i].wolf==1)
        {
            takeWolfBack(i);
            doStep(j);
        }
        if(conditions[i].sheep==1)
        {
            takeSheepBack(i);
            doStep(j);
        }
        if(conditions[i].cabbage==1)
        {
            takeCabbageBack(i);
            doStep(j);
        }
    }
}
void main()
{
    cout<<"有一个农夫带一条狼、一只羊和一棵白菜过河. "<<endl;
    cout<<"如果没有农夫看管，则狼要吃羊，羊要吃白菜."<<endl;
    cout<<"但是船很小，只够农夫带一样东西过河。"<<endl;
    cout<<"问农夫该如何解此难题？"<<endl;
    conditions[0].farmer = 0;
    conditions[0].wolf   = 0;
    conditions[0].sheep  = 0;
    conditions[0].cabbage= 0;
    doStep(0);
}

19 楼

gugolqyda [专家分：0] 发布于 2006-05-10 08:51:00

#include <iostream.h>
struct Condition {
    int farmer;
    int wolf;
    int sheep;
    int cabbage;
};
struct Condition conditions [20];
char* action[100];
void takeWolfOver(int i)
{
    action[i] = "把狼带过河.";
    conditions[i+1].wolf=1;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void takeWolfBack(int i)
{
    action[i] = "把狼带回来.";
    conditions[i+1].wolf=0;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void takeSheepOver(int i)
{
    action[i] = "把羊带过河.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=1;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void takeSheepBack(int i)
{
    action[i] = "把羊带回来.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=0;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void takeCabbageOver(int i)
{
    action[i] = "把菜带过去.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=1;
}
void takeCabbageBack(int i)
{
    action[i] = "把菜带回来.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=0;
}
void getOverBarely(int i)
{
    action[i] = "空手过河.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void getBackBarely(int i)
{
   action[i] = "空手返回.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void showSolution(int i)
{
    int c;
    cout<<"可以这样安排："<<endl;
    for(c=0; c<i; c++)
    {
      cout<<c+1<<action[c]<<endl;
    }
      cout<<"OK，任务完成了！"<<endl;
    }
void doStep(int i)
{
    int c;
    int j;
    if(conditions[i].farmer==1&&
        conditions[i].wolf==1&&
        conditions[i].sheep==1&&
        conditions[i].cabbage==1)
    {
        //OK，所有的东东都安全过河了！
        showSolution(i);
        return;
    }
    //check for lose.
    if(
        (conditions[i].farmer!=conditions[i].wolf && conditions[i].wolf==conditions[i].sheep)
        ||
        (conditions[i].farmer!=conditions[i].sheep && conditions[i].sheep==conditions[i].cabbage)
    )
    {
        //有问题，狼会吃掉羊，或羊会吃掉菜的！
        return;
    }
     for (c=0; c<i; c++)
    {
        if(conditions[c].farmer==conditions[i].farmer&&
            conditions[c].wolf==conditions[i].wolf&&
            conditions[c].sheep==conditions[i].sheep&&
            conditions[c].cabbage==conditions[i].cabbage)
        {
            //已经过河了，或是全部又返回.
            return;
        }
    }


    j=i+1;
    if(conditions[i].farmer==0)
    {
        conditions[j].farmer=1;

        getOverBarely(i);
        doStep(j);

        if(conditions[i].wolf==0)
        {
            takeWolfOver(i);
            doStep(j);
        }
        if(conditions[i].sheep==0)
        {
            takeSheepOver(i);
            doStep(j);
        }
        if(conditions[i].cabbage==0)
        {
            takeCabbageOver(i);
            doStep(j);
        }
    }
    else
    {
        conditions[j].farmer=0;

        getBackBarely(i);
        doStep(j);

        if(conditions[i].wolf==1)
        {
            takeWolfBack(i);
            doStep(j);
        }
        if(conditions[i].sheep==1)
        {
            takeSheepBack(i);
            doStep(j);
        }
        if(conditions[i].cabbage==1)
        {
            takeCabbageBack(i);
            doStep(j);
        }
    }
}
void main()
{
    cout<<"有一个农夫带一条狼、一只羊和一棵白菜过河. "<<endl;
    cout<<"如果没有农夫看管，则狼要吃羊，羊要吃白菜."<<endl;
    cout<<"但是船很小，只够农夫带一样东西过河。"<<endl;
    cout<<"问农夫该如何解此难题？"<<endl;
    conditions[0].farmer = 0;
    conditions[0].wolf   = 0;
    conditions[0].sheep  = 0;
    conditions[0].cabbage= 0;
    doStep(0);
}

20 楼

moz [专家分：37620] 发布于 2006-05-10 12:49:00

DECLARE FUNCTION Check! (a$())
DIM c$(3), d$(3)
c$(1) = "狼羊菜"

     CLS
     PRINT , , "这边有 ", "那边有 "
     PRINT STRING$(60, "-")
     PRINT "没过河之前的情况是:", c$(1), c$(3)

DO
  IF k = 0 THEN j1 = 1 ELSE j1 = 3
  j2 = 4 - j1
  IF i = 0 THEN
     d$(2) = ""
     d$(j1) = c$(j1)
     d$(j2) = c$(j2)
  ELSE
     d$(2) = MID$(c$(j1), i * 2 - 1, 2)
     d$(j1) = LEFT$(c$(j1), i * 2 - 2) + MID$(c$(j1), i * 2 + 1)
     d$(j2) = c$(j2)
  END IF
  IF Check(d$()) = 0 AND i <> ii THEN
     c$(j1) = d$(j1)
     c$(j2) = d$(j2) + d$(2)
     chi = chi + 1
     PRINT "第"; chi; "次农夫带着"; d$(2); "过河后:", c$(1), c$(3)
     k = 1 - k
     IF i = 0 THEN ii = 0 ELSE ii = LEN(c$(j2)) \ 2
     i = 0
  ELSE
     i = i + 1
  END IF
LOOP UNTIL LEN(c$(3)) >= 6

FUNCTION Check (a$())
FOR i = 1 TO 3
    IF INSTR(a$(i), "羊") > 0 AND INSTR(a$(i), "狼") > 0 THEN Check = -1
    IF INSTR(a$(i), "羊") > 0 AND INSTR(a$(i), "菜") > 0 THEN Check = -1
NEXT
END FUNCTION
=======================================================================
                            这边有        那边有
------------------------------------------------------------
没过河之前的情况是:         狼羊菜
第 1 次农夫带着羊过河后:    狼菜          羊
第 2 次农夫带着过河后:      狼菜          羊
第 3 次农夫带着狼过河后:    菜            羊狼
第 4 次农夫带着羊过河后:    菜羊          狼
第 5 次农夫带着菜过河后:    羊            狼菜
第 6 次农夫带着过河后:      羊            狼菜
第 7 次农夫带着羊过河后:                  狼菜羊
================================================================
的确有点牵强,只是针对不同的问题有不同的方法,
这个题目巧合的过于简单,那程序碰巧的完成了也就算了.
真要去做回溯不是不可以,只是小菜大吃了.

您尚未登录，请登录后再回复。点此登录或注册

主题：出个题,农夫带着狼、羊、白菜过河!大家进来看看

回复列表（共23个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖