每日一题5

Question

有3只母雞分別帶著3只小雞要過河，河邊只有一條船，其中母雞都會划船，小雞中只有一隻會划船，小雞離開媽媽與其他母雞在一起時小雞會被其他母雞啄死。示例：将母鸡标记为A,B,C,它们的孩子标记为a（会划船）,b,cABCc   ab->  
ABCc   <-a     b...

Answer 1

百度：
设大老虎为ABC，相应的小老虎为abc，其中c会划船。
    1、ac过河，c回来 (a小老虎已过河)
    2、bc过河，c回来 (ab小老虎已过河)
    3、BA过河，Bb回来 (Aa母子已过河)
    4、Cc过河，Aa回来 (Cc母子已过河)
    5、AB过河，c回来 (ABC三个大老虎已过河)
    6、ca过河，c回来 (ABCa已过河)
    7、cb过河，大功告成！ 
就OK了

Answer 2

今天题目明显不适合用代码写啊
特别是只有6只鸡的情况下O(N)和O(N^2)的速度，没什么本质区别啊

Answer 3

然后通过 BFS 可以得到最优解

Answer 4

ABCabc
ABCc    ab->
ABCc    <-a    b
ABC     ac->   b
ABC     <-a    bc
Aa      BC->   bc
Aa      <-Bb   Cc
Bb      Aa->   Cc
Bb      <-Cc   Aa
bc      BC->   Aa
bc      <-a    ABC
c       ab->   ABC
c       <-a    ABCb
        ac->   ABCb
               ABCabc

Answer 5

代码不高兴写了，只提供一段代码，可以提高比较状态速度的。为了提高速度，用字母ABDabd表示，原因如下  // 当前状态：0x01 = A, 0x02 = B, 0x04 = D, 0x21 = a, 0x22 = b, 0x24 = d
  int[] left; int[] boat; int[] right; boolean fromLeft;
  /** 返回某个int代表的名字
   * 母鸡比小鸡小32，正好
   */
  private static char getName(int x) {
    return (char) ('A' + x - 1);
  }  /**
   * 数组可以是左岸、右岸或者船。
   */
  private static boolean check(int[] array) {
    int parent = 0;
    int child = 0;
    for (int x : array) {
      if ((parent & 0x20) == 0) {
        parent |= x;
      } else {
        child |= x;
      }
    }
    child &= 0x1F;
    if (parent == 0 || child == 0) {
      // 只有母鸡或小鸡，不用比较
      return true;
    }
    if ((parent ^ child) == 0) {
      // 所谓异或，某位上数字相异为1，即非零的情况下，至少有一对母子分离
      return false;
    }
    return true;
  }

Answer 6

今天的题还是用笔算比较方便。希望明天的问题能比较有趣，LZ加油吧。
不知道lz平时的问题是否来自Project Euler？
虽然没在上面做过题，不过看别人挑出的一些问题，跟LZ出的题目感觉比较像，偏重于思考，而不是建模。

Answer 7

确实是euler，做lz的题目，我已经用掉七八张A4纸了

Answer 8

话说这个题和那个人鬼渡河有什么不同？
代码：#include <stdio.h>
typedef struct state s;int isSafe(s);struct state
{
int people;
int ghost;
};s st = {3, 3};
s temp;
int scheme[6][2] = { {-2, 0}, {0, -2}, {-1, -1}, {0, 1}, {1, 0}, {1, 1}};int main()
{
temp.ghost = 3; 
temp.people = 3;
int flag = 0, i; printf("Start: People: 3\t Ghost: 3\n");
while( st.people != 0 || st.ghost != 0 )
{
//东岸往西岸运送
if(flag%2 == 0)
{
for(i = 0; i < 3; i++)
{
temp.people += scheme[i][0];
temp.ghost += scheme[i][1];
if( isSafe(temp) == 1 )
{
st.people = temp.people;
st.ghost = temp.ghost;
break;
}
else
{
temp.people -= scheme[i][0];
temp.ghost -= scheme[i][1];
}
}
}
//西岸往东岸运送
else  
{
for(i = 3; i < 6; i++)
{
temp.people += scheme[i][0];
temp.ghost += scheme[i][1];
if( isSafe(temp) == 1 )
{
st.people = temp.people;
st.ghost = temp.ghost;
break;
}
else
{
temp.people -= scheme[i][0];
temp.ghost -= scheme[i][1];
}
}
}
flag++;
printf("People: %d\t Ghost: %d\n", st.people, st.ghost);
} return 0;
}int isSafe(s s)
{
//三人或者零人，安全
if(s.people == 3 || s.people == 0)
return 1;
else if( s.people == 1 && s.ghost == 1)
return 1;
else if( s.people == 2 && s.ghost == 2 )
return 1;
return 0;
}

Answer 9

首先就是母鸡不能离开小鸡，这也就是说必须先把母鸡全部搞到对岸，假设a会划船，倒推，最后两次肯定是a把b和c度过去的，在渡bc之前，ABC已经都在对岸，a从对岸过来，那么A也在对岸，BC和bc没有渡河，开始的时候只能a来渡，也就只能度bc那么：
                    ac->  
<-a              ab->
<-a              BC->
<-Bb            Aa->
<-Cc            BC->
<-a              ab->
<-a              ac->
搞定

Answer 10

将母鸡标记为A,B,C,它们的孩子标记为a（会划船）,b,cBb先过河
AC过河
最后ac过河 不就可以了吗？完全符合楼主条件。

Answer 11

将母鸡标记为A,B,C,它们的孩子标记为a（会划船）,b,c;
1.ABCc ab->   
2.ABCc <-a b
3.ABC ac-> b
4.ABC <-a bc
5.Aa BC-> bc
6.Aa <-Bb Cc
7.ab ->AB Cc
8. ->ab ABCc
这样没问题吧.

Answer 12

搞错了,更正一下:
将母鸡标记为A,B,C,它们的孩子标记为a（会划船）,b,c;
1.ABCc ab->   
2.ABCc <-a b
3.ABC ac-> b
4.ABC <-a bc
5.Aa BC-> bc
6.Aa <-Bb Cc
7.Bb ->Aa Cc
8.Bb <-Cc Aa
9.bc BC-> Aa
10.bc <-a ABC
11.c ->ab ABC
12.c <-a ABbC
13 ac-> ABbC
 

Answer 13

假设a会划船ABCabc
BbCc   Aa->
BbCc   <-a  A
abc    BC-> A
abc    <-C  AB
Cc     ab-> AB
Cc     <-a  ABb
a      Cc-> ABbCc
a      <-A  BbCc
       Aa-> AaBbCc

Answer 14

假设a会划船ABCabc
BbCc   Aa->
BbCc   <-a  A
abc    BC-> A
abc    <-C  AB
ab     Cc-> AB
ab     <-B  ACc
a      Bb-> ACc
a      <-A  BbCc
       Aa-> AaBbCc

Answer 15

这个非最优解，可以再剩下两步，思路如下：
1.      ABCabc2. AaCc Bb->
3. AaCc <--B b4. ABC ac-> b
5. ABC <--a bc6. Aa BC-> bc
7. Aa <--Cc Bb8. ac AC-> Bb
9. ac <--C ABb10. a Cc-> ABb
11. a <--A BCbc12. Aa-> BCbc13. ABCabc

Answer 16

又想了一下，发现还能省下两步......我错了
ABCa能开船...
1. ABCabc
2. BCbc Aa->
3. BCbc <--a A
4. abc BC-> A
5. abc <--C AB
6. ab Cc-> AB
7. ab <--B ACc
8. a Bb-> ACc
9. a <--A BCbc
10. Aa-> BCbc
11. ABCabc

Answer 17

这题目copy得太不负责了，copy至少也要检查一下吧。