中文XML论坛--过河问题[讨论]

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

题目：

有一条河，在河的左岸有3个人和3个野兽要过河。河里有一只船，该船每次最多可以装2个物体（人或兽）。在河两岸上如果人的数目小于兽的数目，人就被兽吃掉。请列出人和兽能安全过河所有方法。

[此贴子已经被作者于2006-5-29 10:38:33编辑过]

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

算法分析：
将某一时刻河岸的整个状态抽象为一个结构体，而没一个状态会由下列5中情况派生出5个子状态：1个人过河，2个人过河，1个兽过河，2个兽过河，1个人和一个兽过河。对每一个子状态进行判断：如果左边和右边都有人，两边的人数必须分别大于等于两边的兽数；如果左边有人，右边没人，左边的人数必须大于左边兽数；如果左边没人，右边有人，右边的人数必须大于右边的兽数。

算法描述：
typedef struct _stNode {
int hl, bl, hr, br;
} stNode;

bool humbst(stNode st, void (*opt)(stNode sm, FILE *fp), FILE *fp)
{
bool rev = false;
stNode st1, st2, st3, st4, st5;

do
{
  /*
   如果左边和右边都有人，两边的人数必须分别大于等于两边的兽数；
   如果左边有人，右边没人，左边的人数必须大于左边兽数；
   如果左边没人，右边有人，右边的人数必须大于右边的兽数。
  */
  if ((st.hl && (st.hl >= st.bl) && st.hr && (st.hr >= st.br))
   || (st.hl && st.hl >= st.bl && !st.hr)
   || (!st.hl && st.hr && st.hr >= st.br))
  {
   opt(st, fp); /* 显示合法状态 */
   rev = true;
   if (st.hl >= 1) /* 将左边的一个人运到右边 */
   {
    fprintf(fp, "load = one human\n", 0);
    st1.hl = st.hl - 1;
    st1.bl = st.bl;
    st1.hr = st.hr + 1;
    st1.br = st.br;
    st1.parent = &st;
    if (humbst(st1, opt, fp))
    {
     fprintf(fp, "\n", 0);
    }
   }

   if (st.hl >= 2) /* 将左边的两个人运到右边 */
   {
    fprintf(fp, "load = two human\n", 0);
    st2.hl = st.hl - 2;
    st2.bl = st.bl;
    st2.hr = st.hr + 2;
    st2.br = st.br;
    st2.parent = &st;
    if (humbst(st2, opt, fp))
    {
     fprintf(fp, "\n", 0);
    }
   }

   if (st.bl >= 1) /* 将左边的一个兽运到右边 */
   {
    fprintf(fp, "load = one beast\n", 0);
    st3.hl = st.hl;
    st3.bl = st.bl - 1;
    st3.hr = st.hr;
    st3.br = st.br + 1;
    st3.parent = &st;
    if (humbst(st3, opt, fp))
    {
     fprintf(fp, "\n", 0);
    }
   }

   if (st.bl >= 2) /* 将左边的两个兽运到右边 */
   {
    fprintf(fp, "load = two beast\n", 0);
    st4.hl = st.hl;
    st4.bl = st.bl - 2;
    st4.hr = st.hr;
    st4.br = st.br + 2;
    st4.parent = &st;
    if (humbst(st4, opt, fp))
    {
     fprintf(fp, "\n", 0);
    }
   }

   if (st.hl >= 1 && st.bl >= 1) /* 将左边的一个人一个兽运到右边 */
   {
    fprintf(fp, "load = one human and one beast\n", 0);
    st5.hl = st.hl - 1;
    st5.bl = st.bl - 1;
    st5.hr = st.hr + 1;
    st5.br = st.br + 1;
    st5.parent = &st;
    if (humbst(st5, opt, fp))
    {
     fprintf(fp, "\n", 0);
    }
   }
  }
}while (false);

return rev;
}

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

程序运行结果表明满足条件的渡河方案共有12种。

我现在的疑问就是会不会存在某种情况：有一个状态，该状态的左岸和右岸人兽数目满足限制条件，当从该状态的左岸继续运输到右岸时，该状态的任何子状态的人兽数目都不满足条件（兽的数目大于人的数目），但是通过先从该状态的右岸先运输到左岸，然后在继续从左岸运输到右岸则存在合法的解决方案。

因为在我的算法中我隐式地认为只能从左岸运东西到右岸，而不能右岸运东西到左岸。上面我有疑问的情况说通俗点就是会不会某个状态已经不满足条件，但是可以通过将刚才从左岸运过来的东西再回运（回运以后的子状态如果与该状态的父状态相同则不算），调整一下后继续操作也可以找出合理的解决方案。

例如：
S1->S2->S3，此时S3的某边的人数已经小于兽数，所以将S3的右边物体（人或兽）回运到左边得状态S4，且S2与S4不相同，从S4继续操作以后，成功找到一种解决方案：S1->S2->S3->S4->S5->S6……->Sn。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

晕，这个就是一个图的遍历问题。
也就是说，两边的状态各看作图的节点
如果一个状态可以到另一个状态在节点之间连边
然后dfs一下

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

“该状态的任何子状态的人兽数目都不满足条件”
如何定义“子状态”？
需要注意的是：船的位置（在哪侧）也是“状态”的一个组成部分。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

每个状态都可能对应5种子状态：
个人过河，2个人过河，1个兽过河，2个兽过河，1个人和一个兽过河。

我在做的过程中确实没考虑船的位置。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

考虑河的左岸，用（X,Y,Z）表示河左岸有X个人、Y个兽、Z条船。
则初始状态为（3,0,1），目标状态为（0，0，0）。
要注意到，（2，2，0）和（2，2，1）是两个相当不同的状态。

[此贴子已经被作者于2006-5-30 14:17:04编辑过]

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

嗯，Logician说的没错了。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

以下是引用Logician在2006-5-30 1:53:00的发言：
考虑河的左岸，用（X,Y,Z）表示河左岸有X个人、Y个兽、Z个人。
则初始状态为（3,0,1），目标状态为（0，0，0）。
要注意到，（2，2，0）和（2，2，1）是两个相当不同的状态。

Logician兄所说的(X,Y,Z)中X和Z都表示人，他们的区别是什么啊？

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

不好意思，写错了，Z是船。Z=1表示船在左岸，Z=0表示船在右岸。


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	2,343.750ms