|
|
問題 宣教師と先住民
3人の宣教師と3人の先住民が川を渡ることになりました。
川には、2人乗りのボートが1そうしかありません。
どのようなときでも先住民の数が宣教師の数よりも多いと、宣教師は襲われてしまいます。
なお、全員がボートを漕ぐことができます。
また、岸に着いたとき全員がボートを降ります。
6人が安全に川を渡る最短手順を考えてください。
考察
最短手順
・n人ずつ、(n-1)人乗りのとき
3人ずつ、2人乗りのとき、11回
4人ずつ、3人乗りのとき、9回
5人ずつ、4人乗りのとき、7回
6人ずつ、5人乗りのとき、7回
：
n≧7の場合、5回
1: nAna[(n-1)a]→
2: ←[a](n-1)a
3: nA2a[(n-2)A]→
4: ←[Aa](n-2)A(n-2)a
5: 3A3a[3A3a]→
最短手順の考察
ボートに乗るときに制限がなければ、
(n-1)人が渡り1人が戻るとすると、(n-2)人ずつ渡ることになる。
たとえばn=7の場合、(2n)÷(n-2)は商2 余り4 より、2×2+1=5回が必要になる。（必要性）
その実例が存在する。（十分性）
n n-2 (2n)÷(n-2) 回数
-------------------------------
3 1 6 5×2+1=11
4 2 4 3×2+1=7
5 3 3余り1 3×2+1=7
6 4 4 3×2+1=7
7 5 2余り4 2×2+1=5
・4人乗りの場合
n人ずつ（n≧5）のとき、(2n-3)回
1: nAna[AAaa]→
2: ←[Aa]AAaa
3: (n-1)A(n-1)a[AAaa]→
4: ←[Aa]2A2a
：
2k-1: 3A3a[AAaa]→
2k: ←[Aa](n-1)A(n-1)a
+1: 2A2a[AAaa]→
k往復（nが2になるまで）と最後に1回なので、2(n-2)+1=2n-3
(終わり)
類題 嫉妬深い夫
3組の夫婦が川を渡ることになりました。ボートには2人しか乗ることができません。
どの夫も嫉妬深く、彼自身が一緒にいない限り、ボートでも岸でも妻が他の男といることを許しません。
なお、6人ともボートを漕ぐことができます。
また、岸に着いたとき全員が舟を降ります。
3組の夫婦が川を渡る最短手順を考えてください。
答え
M=3、N=3、K=2として、
1: AAAaaa(aa)→
2: ←(a)aa
3: AAAaa(aa)→
4: ←(a)aaa
5: AAAa(AA)→
6: ←(Aa)AAaa
7: AAaa(AA)→
8: ←(a)AAAa
9: aaa(aa)→
10: ←(a)AAAaa
11: aa(aa)→
より、
1: ABCabc(ab)→
2: ←(a)ab
3: ABCac(ac)→
4: ←(a)abc
5: ABCa(BC)→
6: ←(Bb)BCbc
7: ABab(AB)→
8: ←(c)ABCc
9: abc(ab)→
10: ←(a)ABCab
11: ac(ac)→
(終わり)
LET M=3 !m人の宣教師
LET N=3 !n人の先住民
LET K=2 !k人乗りの舟
DIM S$((M+1)*(N+1)) !条件を満たす岸の状態
LET D=0
FOR X=0 TO M
FOR Y=0 TO N
IF X=0 OR X>=Y THEN !条件を満たす
LET D=D+1
LET S$(D)=REPEAT$("A",X)&REPEAT$("a",Y)
END IF
NEXT Y
NEXT X
PUBLIC NUMERIC C !解の数
LET C=0
DIM A(50) !手順（舟の乗せ方）
DIM B(0 TO 50) !こちらの岸の状態
LET B(0)=D
CALL try(1,A,B, M,N,K, D,S$)
IF C=0 THEN PRINT "解なし"
END
EXTERNAL SUB try(P,A(),B(), M,N,K, D,S$()) !バックトラック法で検索する
FOR i=1 TO D !舟に乗る
LET T=LEN(S$(i))
IF T>=1 AND T<=K THEN !k人乗りの舟 ※岸の部分集合
LET L$=S$(B(P-1)) !こちらの岸の状態
LET X=POS(L$,S$(i))
IF X>0 THEN
LET L$(X:X+T-1)="" !渡る
IF MOD(P,2)=1 AND L$="" THEN !すべて渡り終えたなら ※奇数回かつφなら
LET C=C+1
PRINT "No.";C
FOR J=1 TO P-1 !結果を表示する
PRINT STR$(J);": ";
IF MOD(J,2)=1 THEN
PRINT S$(B(J-1));"(";S$(A(J));")→"
ELSE
PRINT "←(";S$(A(J));")";S$(B(J-1))
END IF
NEXT J
PRINT STR$(P);": ";S$(i);"(";S$(i);")→"
PRINT
ELSE
CALL checkRule(L$,D,S$, id) !安全に渡れるなら
IF id>0 THEN
LET R$=S$(D) !向こう側の岸の状態 ※補集合 ~L、差 U-L
LET X=POS(R$,L$)
LET R$(X:X+LEN(L$)-1)=""
CALL checkRule(R$,D,S$, id) !安全に渡れるなら
IF id>0 THEN
FOR J=P-2 TO 0 STEP -2 !同じ状態に戻っていないか
IF id=B(J) THEN EXIT FOR
NEXT J
IF J<0 THEN
LET A(P)=i !記録する
LET B(P)=id
CALL try(P+1,A,B, M,N,K, D,S$) !次へ
!!!IF P<5 THEN CALL try(P+1,A,B, M,N,K, D,S$) !次へ
END IF
END IF
END IF
END IF
END IF
END IF
NEXT i
END SUB
EXTERNAL SUB checkRule(L$,D,S$(), id) !条件を満たすかどうか確認する
FOR id=1 TO D
IF L$=S$(id) THEN EXIT SUB !パターン番号を返す
NEXT id
LET id=-1 !NG
END SUB
実行結果
No. 1
1: AAAaaa(aa)→
2: ←(a)aa
3: AAAaa(aa)→
4: ←(a)aaa
5: AAAa(AA)→
6: ←(Aa)AAaa
7: AAaa(AA)→
8: ←(a)AAAa
9: aaa(aa)→
10: ←(a)AAAaa
11: aa(aa)→
No. 2
1: AAAaaa(aa)→
2: ←(a)aa
3: AAAaa(aa)→
4: ←(a)aaa
5: AAAa(AA)→
6: ←(Aa)AAaa
7: AAaa(AA)→
8: ←(a)AAAa
9: aaa(aa)→
10: ←(A)AAAaa
11: Aa(Aa)→
No. 3
1: AAAaaa(Aa)→
2: ←(A)Aa
3: AAAaa(aa)→
4: ←(a)aaa
5: AAAa(AA)→
6: ←(Aa)AAaa
7: AAaa(AA)→
8: ←(a)AAAa
9: aaa(aa)→
10: ←(a)AAAaa
11: aa(aa)→
No. 4
1: AAAaaa(Aa)→
2: ←(A)Aa
3: AAAaa(aa)→
4: ←(a)aaa
5: AAAa(AA)→
6: ←(Aa)AAaa
7: AAaa(AA)→
8: ←(a)AAAa
9: aaa(aa)→
10: ←(A)AAAaa
11: Aa(Aa)→
|
|