夫妻过河问题

题目简介：

有三对夫妻要过河，约束条件是，根据法律，任一女子不得在其丈夫不在场的情况下与另外男子在一起，问此时这三对夫妻能否过河？

解题思路：

在任何状态下，六人以及船的位置可以用七个boolean来表示：

船的位置用一个 boolean 类型的变量表示：

boolean ship；

三对夫妻用两个数组表示:

boolean a[3];//丈夫的位置

boolean b[3];//妻子的位置

则问题转化为：

由状态

State {
boolean ship=true;//表示船在此岸
boolean man[3]={true,true,true};//表示三名男子全在此岸
boolean woman[3]={true,true,true};//表示三名女子全在此岸
}

经过怎样的安全路径到达状态：

State {
boolean ship=false;
boolean man[3]={false,false,false};
boolean woman[3]={false,false,false};
}

安全路径是指：

这条路径上的所有状态均是安全（合法）的

这条路径上的所有状态转换均是安全（合法）的

判断某个状态是否安全的标准是：

任意妻子不得在其丈夫不在身边的情况下与其它男人在一起，即：

所有妻子都和她的丈夫在一起，或三名丈夫在同侧。

/**
     * 判断该状态是否是合法的
     * 
     * @return true为合法，false为不合法
     */
    public boolean isLowful() {
        if (man[0] == man[1] && man[1] == man[2])
            return true;// 所有丈夫都在同一侧时一定是合法的
        for (int i = 0; i < 3; i++)
            if (man[i] != woman[i])
                return false;// 任意丈夫与妻子不在同一侧时一定是不合法的
        return true;// 所有妻子都和丈夫在同一侧，所以是合法的
    }

判断某个状态转换是否安全的标准是：

状态转换过程中船必须由一岸到了另一岸；

状态转换过程中一定有且仅有一或二名人员随船到了另一岸：

 1     /**
 2      * 判断两状态之间的迁移是否合法
 3      * 
 4      * @param state1
 5      * @param state2
 6      * @return 合法则返回true
 7      */
 8     private boolean isLowful(SpouseQuestionState state1, SpouseQuestionState state2) {
 9         if (state1 == null || state2 == null)
10             return false;
11         //System.out.println(Integer.toString(state1.hashCode(),2)+"比较"+Integer.toString(state2.hashCode(),2));
12         if (state1.ship == state2.ship)
13             return false;
14         int count = 0;
15         for (int i = 0; i < 3; i++) {
16             if (state1.man[i] == state2.man[i])
17                 continue;// 两个状态中某个人位置没有变动
18             if (state1.man[i] == state1.ship && state2.man[i] == state2.ship) {
19                 count++;
20                 continue;
21             }
22             // 一个人随船到了另一侧
23             return false;// 其它情况
24         }
25         for (int i = 0; i < 3; i++) {
26             if (state1.woman[i] == state2.woman[i])
27                 continue;// 两个状态中某个人位置没有变动
28             if (state1.woman[i] == state1.ship && state2.woman[i] == state2.ship) {
29                 count++;
30                 continue;
31             }
32             // 一个人随船到了另一侧
33             return false;// 其它情况
34         }
35         if (count == 1 || count == 2)
36             return true;
37         return true;// 超过两人乘船或无人驾驶
38 
39     }

对代码进行适量的优化：

显然以下两个状态是完全等价的：

State {
boolean ship=false;
boolean man[3]={true,false,false};
boolean woman[3]={true,false,false};
}
和
State {
boolean ship=false;
boolean man[3]={false,true,false};
boolean woman[3]={false,true,false};
}

我们可以重写State的hashCode()和equals()方法，使这两个对象等价：

 1 public int hashCode(){
 2         if(hash==0){
 3             for(int ti=0;ti<3;ti++)
 4                 for(int tj=0;tj<ti;tj++)
 5             {
 6             int hash1=ship?1:0;
 7             for(int x=0;x<3;x++){
 8                 int i=x==ti?tj:x==tj?ti:x;
 9                 hash1=hash1<<1;
10                 hash1+=man[i]?1:0;
11                 hash1=hash1<<1;
12                 hash1+=woman[i]?1:0;
13             }
14             hash1+=128;
15             hash=hash1>hash?hash1:hash;
16             }
17         }
18         return hash;
19     }
20 
21     public boolean equals(SpouseQuestionState object){
22         if(this==object)return true;
23         if(object==null)return false;
24         if(object.getClass()!=this.getClass())return false;
25         return this.hashCode()==object.hashCode();
26     }

算法设计：

使用回溯法，发现一条路走不通就返回并另选一条，一旦走到终点就将路径输出：

 1     private void Digui2(State start, LinkedList<State> last, State state, StateTransition stateTransition) {
 2         if (start.equals(state.getLastState())) {
 3             // System.out.println("	抵达终点");
 4             if (last.size() <= 20) {
 5                 for (State sta : last) {
 6                     System.out.println(Integer.toString(sta.hashCode(), 2));
 7                 }
 8                 System.out.println("抵达终点,耗时"+(last.size()+1));
 9             }
10             last.pollLast();
11             return;
12         }
13         Set<StateTransition> temp = new HashSet<>(stateTransition.getAllLowfulStateTranssitionFrom(start));
14         // if(temp==null){
15         // System.out.println("	此路不通");
16         // return;
17         // }
18         Iterator<StateTransition> iterator = temp.iterator();
19         while (iterator.hasNext()) {
20             StateTransition sta = iterator.next();
21             if (last.contains(sta.getEnd())) {
22                 iterator.remove();
23             }
24         }
25         // temp.removeAll(last);
26         if (temp.isEmpty()) {
27             // System.out.println("	此路不通");
28             last.pollLast();
29             return;
30         }
31         for (StateTransition x : temp) {
32             last.add(start);
33             // System.out.print(x.toString()+"	");
34             Digui2(x.getEnd(), last, state, stateTransition);
35         }
36         last.pollLast();
37         return;
38     }

以下为全部代码：

<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://www.springframework.org/schema/beans 
                        http://www.springframework.org/schema/beans/spring-beans.xsd">

    <!-- bean definitions here -->
    <bean id="State" class="com.lille.mathModel.riverCrossing.stateImpl.SpouseQuestionState">
    </bean>
    <bean id="StateTransition" class="com.lille.mathModel.riverCrossing.stateTransitionImpl.SpouseQuestionStateTransition"></bean>
</beans>
applicationContext.xml
  1 /**
  2  * 
  3  */
  4 package com.lille.mathModel.riverCrossing.stateImpl;
  5 
  6 import java.util.ArrayList;
  7 import java.util.HashMap;
  8 import java.util.HashSet;
  9 import java.util.LinkedList;
 10 import java.util.Map;
 11 import java.util.Set;
 12 
 13 import com.lille.mathModel.riverCrossing.state.State;
 14 
 15 /**
 16  * @author Lille qliujinming@qq.com
 17  * @time 2018-3-18
 18  *
 19  */
 20 public class SpouseQuestionState implements State {
 21 
 22     public final static Map<Integer, SpouseQuestionState> ALL_LOWFUL_STATE=get_ALL_LOWFUL_STATE();
 23     private static Map<Integer,SpouseQuestionState> get_ALL_LOWFUL_STATE(){
 24         Map<Integer,SpouseQuestionState> temp=new HashMap<Integer,SpouseQuestionState>();
 25         for(SpouseQuestionState state:getAllState()){
 26             temp.put(state.hashCode(), state);
 27         }
 28         return temp;
 29     }
 30     /*
 31      * （非 Javadoc）
 32      * 
 33      * @see com.lille.mathModel.riverCrossing.state.State#getAllLowfullState()
 34      */
 35     @Override
 36     public ArrayList<SpouseQuestionState> getAllLowfulState(){
 37         return getAllState();
 38     }
 39     public static ArrayList<SpouseQuestionState> getAllState() {
 40         // TODO 自动生成的方法存根
 41         LinkedList<SpouseQuestionState> temp = new LinkedList<SpouseQuestionState>();
 42         Set<Boolean> set = new HashSet<Boolean>();
 43         set.add(true);
 44         set.add(false);
 45         for (boolean t0 : set)
 46             for (boolean t1 : set)
 47                 for (boolean t2 : set)
 48                     for (boolean t3 : set)
 49                         for (boolean t4 : set)
 50                             for (boolean t5 : set)
 51                                 for (boolean t6 : set) {
 52                                     SpouseQuestionState statetemp = new SpouseQuestionState(t0, t1, t2, t3, t4, t5, t6);
 53                                     if (statetemp.isLowful()) {
 54                                         temp.add(statetemp);
 55                                     }
 56                                 }
 57 
 58         return new ArrayList<SpouseQuestionState>(temp);
 59     }
 60 
 61     /*
 62      * （非 Javadoc）
 63      * 
 64      * @see com.lille.mathModel.riverCrossing.state.State#getFirstState()
 65      */
 66     @Override
 67     public State getFirstState() {
 68         // TODO 自动生成的方法存根
 69         return FIRST_STATE;
 70     }
 71 
 72     /*
 73      * （非 Javadoc）
 74      * 
 75      * @see com.lille.mathModel.riverCrossing.state.State#getLastState()
 76      */
 77     @Override
 78     public State getLastState() {
 79         // TODO 自动生成的方法存根
 80         return LAST_STATE;
 81     }
 82 
 83     /**
 84      * 判断该状态是否是合法的
 85      * 
 86      * @return true为合法，false为不合法
 87      */
 88     public boolean isLowful() {
 89         if (man[0] == man[1] && man[1] == man[2])
 90             return true;// 所有丈夫都在同一侧时一定是合法的
 91         for (int i = 0; i < 3; i++)
 92             if (man[i] != woman[i])
 93                 return false;// 任意丈夫与妻子不在同一侧时一定是不合法的
 94         return true;// 所有妻子都和丈夫在同一侧，所以是合法的
 95     }
 96     public int hashCode(){
 97         if(hash==0){
 98             for(int ti=0;ti<3;ti++)
 99                 for(int tj=0;tj<ti;tj++)
100             {
101             int hash1=ship?1:0;
102             for(int x=0;x<3;x++){
103                 int i=x==ti?tj:x==tj?ti:x;
104                 hash1=hash1<<1;
105                 hash1+=man[i]?1:0;
106                 hash1=hash1<<1;
107                 hash1+=woman[i]?1:0;
108             }
109             hash1+=128;
110             hash=hash1>hash?hash1:hash;
111             }
112         }
113         return hash;
114     }
115     public boolean equals(SpouseQuestionState object){
116         if(this==object)return true;
117         if(object==null)return false;
118         if(object.getClass()!=this.getClass())return false;
119         return this.hashCode()==object.hashCode();
120     }
121     /*
122     public boolean equals(SpouseQuestionState object){
123         if(this==object)return true;
124         if(object==null)return false;
125         if(object.getClass()!=this.getClass())return false;
126         for(int i=0;i<3;i++){
127             for(int j=0;j<i;j++){
128                 hash=object.ship?1:0;
129                 for(int x=0;x<3;x++){
130                     int temp=x==i?j:x==j?i:x;
131                     hash=hash<<1;
132                     hash+=object.man[x]?1:0;
133                     hash=hash<<1;
134                     hash+=object.woman[x]?1:0;
135                 }
136                 hash+=128;
137                 if(hashCode()==128)return true;
138             }
139         }
140         return this.hashCode()==object.hashCode();
141     }*/
142     SpouseQuestionState() {
143 
144     }
145     SpouseQuestionState(boolean ship, boolean man0, boolean man1, boolean man2, boolean woman0, boolean woman1,
146             boolean woman2) {
147         this.ship = ship;
148         this.man = new boolean[] { man0, man1, man2 };
149         this.woman = new boolean[] { woman0, woman1, woman2 };
150     }
151     /**
152      * 初态下所有元素都在此岸
153      */
154     private static final SpouseQuestionState FIRST_STATE=ALL_LOWFUL_STATE.get(255);
155     /**
156      * 终态下所有元素都在彼岸
157      */
158     private static final SpouseQuestionState LAST_STATE=ALL_LOWFUL_STATE.get(128);
159     public boolean ship;
160     public boolean man[] = new boolean[3];
161     public boolean woman[] = new boolean[3];
162     private int hash;
163 }
SpouseQuestionState.java
  1 package com.lille.mathModel.riverCrossing.stateTransitionImpl;
  2 
  3 import java.util.ArrayList;
  4 import java.util.HashMap;
  5 import java.util.HashSet;
  6 import java.util.Set;
  7 
  8 import com.lille.mathModel.riverCrossing.state.State;
  9 import com.lille.mathModel.riverCrossing.stateImpl.SpouseQuestionState;
 10 import com.lille.mathModel.riverCrossing.stateTransition.StateTransition;
 11 
 12 public class SpouseQuestionStateTransition implements StateTransition {
 13 
 14     @Override
 15     public ArrayList<StateTransition> getAllLowfulStateTranssition(ArrayList<State> stateList) {
 16         // TODO 自动生成的方法存根
 17 
 18         return null;
 19     }
 20 
 21     @Override
 22     public Set<SpouseQuestionStateTransition> getAllLowfulStateTranssitionFrom(State state) {
 23         // TODO 自动生成的方法存根
 24         HashSet<SpouseQuestionStateTransition> temp = FROM_TABLE.get(state);
 25         if (temp == null) {
 26             temp = new HashSet<SpouseQuestionStateTransition>();
 27             FROM_TABLE.put(state, temp);
 28             SearchAboutStart((SpouseQuestionState) state, temp);
 29         }
 30         return FROM_TABLE.get(state);
 31     }
 32 
 33     @Override
 34     public Set<SpouseQuestionStateTransition> getAllLowfulStateTranssitionTo(State state) {
 35         // TODO 自动生成的方法存根
 36         return null;
 37     }
 38 
 39     private final HashMap<State, HashSet<SpouseQuestionStateTransition>> FROM_TABLE = new HashMap<State, HashSet<SpouseQuestionStateTransition>>();
 40     private final HashMap<State, HashSet<SpouseQuestionStateTransition>> TO_TABLE = new HashMap<State, HashSet<SpouseQuestionStateTransition>>();
 41     private final SpouseQuestionState start;
 42     private final SpouseQuestionState end;
 43 
 44     public SpouseQuestionState getStart() {
 45         return start;
 46     }
 47 
 48     public SpouseQuestionState getEnd() {
 49         return end;
 50     }
 51 
 52     public SpouseQuestionStateTransition() {
 53         start = null;
 54         end = null;
 55     }
 56 
 57     public SpouseQuestionStateTransition(SpouseQuestionState start, SpouseQuestionState end) {
 58         this.start = start;
 59         this.end = end;
 60     }
 61 
 62     /**
 63      * 判断两状态之间的迁移是否合法
 64      * 
 65      * @param state1
 66      * @param state2
 67      * @return 合法则返回true
 68      */
 69     private boolean isLowful(SpouseQuestionState state1, SpouseQuestionState state2) {
 70         if (state1 == null || state2 == null)
 71             return false;
 72         //System.out.println(Integer.toString(state1.hashCode(),2)+"比较"+Integer.toString(state2.hashCode(),2));
 73         if (state1.ship == state2.ship)
 74             return false;
 75         int count = 0;
 76         for (int i = 0; i < 3; i++) {
 77             if (state1.man[i] == state2.man[i])
 78                 continue;// 两个状态中某个人位置没有变动
 79             if (state1.man[i] == state1.ship && state2.man[i] == state2.ship) {
 80                 count++;
 81                 continue;
 82             }
 83             // 一个人随船到了另一侧
 84             return false;// 其它情况
 85         }
 86         for (int i = 0; i < 3; i++) {
 87             if (state1.woman[i] == state2.woman[i])
 88                 continue;// 两个状态中某个人位置没有变动
 89             if (state1.woman[i] == state1.ship && state2.woman[i] == state2.ship) {
 90                 count++;
 91                 continue;
 92             }
 93             // 一个人随船到了另一侧
 94             return false;// 其它情况
 95         }
 96         if (count == 1 || count == 2)
 97             return true;
 98         return true;// 超过两人乘船或无人驾驶
 99 
100     }
101 
102     /**
103      * 取得指定起点的所有合法状态迁移，并将其储存在set中
104      * 
105      * @param state
106      * @param set
107      * @return 若set不为空，返回true
108      */
109     private boolean SearchAboutStart(SpouseQuestionState state, HashSet<SpouseQuestionStateTransition> set) {
110 
111         for (int i = 0; i < 6; i++)
112             for (int j = 0; j <=i; j++) {
113                 int key = 0;
114                 if (i != j)
115                     key = (1 << i) + (1 << j) + (1 << 6);
116                 else
117                     key = (1 << i) + (1 << 6);
118                 SpouseQuestionState temp = SpouseQuestionState.ALL_LOWFUL_STATE.get(key^state.hashCode());
119                 if (isLowful(state, temp)){
120                     set.add(new SpouseQuestionStateTransition(state, temp));}
121             }
122         return !set.isEmpty();
123     }
124 
125     /**
126      * 
127      */
128     public String toString() {
129         return Integer.toString(start.hashCode(), 2) + "到" + Integer.toString(end.hashCode(), 2);
130 
131     }
132 
133     private int hash;
134 
135     public int hashCode() {
136         if (hash == 0) {
137             hash = start.hashCode();
138             hash = hash*128 + end.hashCode();
139         }
140         return hash;
141     }
142 
143     public boolean equals(SpouseQuestionStateTransition x) {
144         if (x == null )
145             return false;
146         return this.hashCode()==x.hashCode();
147         
148     }
149 }
SpouseQuestionStateTransition.java
 1 package com.lille.mathModel.riverCrossing.state;
 2 
 3 import java.util.ArrayList;
 4 
 5 /**
 6  * 
 7  * @author Lille qliujinming@qq.com
 8  * @time 2018-3-18
 9  */
10 public interface State {
11     /**
12      * 取得所有合法状态
13      * 
14      * @return
15      */
16     public ArrayList<? extends State> getAllLowfulState();
17 
18     /**
19      * 取得初态
20      * 
21      * @return
22      */
23     public State getFirstState();
24 
25     /**
26      * 取得终态
27      * 
28      * @return
29      */
30     public State getLastState();
31 }
State.java
 1 package com.lille.mathModel.riverCrossing.stateTransition;
 2 
 3 import java.util.ArrayList;
 4 import java.util.Set;
 5 
 6 import com.lille.mathModel.riverCrossing.state.State;
 7 import com.lille.mathModel.riverCrossing.stateTransitionImpl.SpouseQuestionStateTransition;
 8 
 9 public interface StateTransition {
10     /**
11      * 获取该状态迁移的初始状态
12      * @return
13      */
14     public State getStart();
15     /**
16      * 该状态迁移的目的地
17      * @return
18      */
19     public State getEnd();
20     /**
21      * 获得所有合法的状态迁移
22      * 
23      * @param stateList
24      *            所有的合法状态
25      * @return
26      */
27     public ArrayList<StateTransition> getAllLowfulStateTranssition(ArrayList<State> stateList);
28 
29     /**
30      * 获得以state为起点的所有合法状态迁移
31      * 
32      * @param state
33      * @return
34      */
35     public Set<SpouseQuestionStateTransition> getAllLowfulStateTranssitionFrom(State state);
36 
37     /**
38      * 获得所有以state为终点的所有合法状态迁移
39      * 
40      * @param state
41      * @return
42      */
43     public Set<SpouseQuestionStateTransition> getAllLowfulStateTranssitionTo(State state);
44 }
StateTransition.java
 1 package com.lille.test;
 2 
 3 import java.util.HashSet;
 4 import java.util.Iterator;
 5 import java.util.LinkedList;
 6 import java.util.Set;
 7 
 8 import org.junit.Test;
 9 import org.springframework.context.ApplicationContext;
10 import org.springframework.context.support.ClassPathXmlApplicationContext;
11 
12 import com.lille.mathModel.riverCrossing.state.State;
13 import com.lille.mathModel.riverCrossing.stateTransition.StateTransition;
14 
15 public class Test01 {
16     @Test
17     public void Test1() {
18         String xml = "applicationContext.xml";
19         @SuppressWarnings("resource")
20         ApplicationContext context = new ClassPathXmlApplicationContext(xml);
21         State state = (State) context.getBean("State");
22         StateTransition stateTransition = (StateTransition) context.getBean("StateTransition");
23         hashSet.add(state.getFirstState());
24         // Digui(state, stateTransition);
25         LinkedList<State> last = new LinkedList<State>();
26         Digui2(state.getFirstState(), last, state, stateTransition);
27     }
28 
29     Set<State> hashSet = new HashSet<State>();
30 
31     private void Digui2(State start, LinkedList<State> last, State state, StateTransition stateTransition) {
32         if (start.equals(state.getLastState())) {
33             // System.out.println("	抵达终点");
34             if (last.size() <= 20) {
35                 for (State sta : last) {
36                     System.out.println(Integer.toString(sta.hashCode(), 2));
37                 }
38                 System.out.println("抵达终点,耗时"+(last.size()+1));
39             }
40             last.pollLast();
41             return;
42         }
43         Set<StateTransition> temp = new HashSet<>(stateTransition.getAllLowfulStateTranssitionFrom(start));
44         // if(temp==null){
45         // System.out.println("	此路不通");
46         // return;
47         // }
48         Iterator<StateTransition> iterator = temp.iterator();
49         while (iterator.hasNext()) {
50             StateTransition sta = iterator.next();
51             if (last.contains(sta.getEnd())) {
52                 iterator.remove();
53             }
54         }
55         // temp.removeAll(last);
56         if (temp.isEmpty()) {
57             // System.out.println("	此路不通");
58             last.pollLast();
59             return;
60         }
61         for (StateTransition x : temp) {
62             last.add(start);
63             // System.out.print(x.toString()+"	");
64             Digui2(x.getEnd(), last, state, stateTransition);
65         }
66         last.pollLast();
67         return;
68     }
69 
70     private void Digui(State state, StateTransition stateTransition) {
71         boolean flag = false;
72         do {
73             flag = false;
74             Set<State> hashSet2 = new HashSet<State>();
75             for (State temp : hashSet) {
76                 for (StateTransition trtemp : stateTransition.getAllLowfulStateTranssitionFrom(temp)) {
77                     if (!hashSet.contains(trtemp.getEnd())) {
78                         hashSet2.add(trtemp.getEnd());
79                         System.out.println(trtemp.toString());
80                     }
81                 }
82             }
83             if (hashSet.addAll(hashSet2))
84                 flag = true;
85         } while (flag);
86     }
87 
88 }
Test01.java

以下为最终结果：

11111111
10111010
11111110
10101010
11111010
10110000
11111100
10010100
11010101
10010000
11110000
抵达终点,耗时12
11111111
10111010
11111110
10101010
11111010
10110000
11111100
10010100
11010101
10010000
11010100
抵达终点,耗时12
11111111
10111100
11111110
10101010
11111010
10110000
11111100
10010100
11010101
10010000
11110000
抵达终点,耗时12
11111111
10111100
11111110
10101010
11111010
10110000
11111100
10010100
11010101
10010000
11010100
抵达终点,耗时12

每个字节表示一个状态，首位始终为1，不然会参差不齐的，剩下七位分别是船、男A、女A、男B、女B、男C、女C，1表示此岸，0表示彼岸

为什么要用Spring呢，因为刚学想练练手。

PS:用java来做算法题真是让人头疼

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/liujinming/p/8605806.html