|
|
> No.1013[元記事へ]
GAIさんへのお返事です。
> これはどうやって探せるんですか？
> もしプログラムでやられたら是非拝見させて下さい。
手作業と同様に手を重ねて、樹形図を作成します。
１つ前の手から、今回の手２０通り（Perm(5,2)）をすべて展開していきます。
ただ、「元に戻る」、「以前の手」などの展開はしません。
樹形図の例
(32,0,0,0,0)
→(22,10,0,0,0)
→(12,10,10,0,0)
→(12,10,0,10,0)
→(15,10,0,0,7)
→(22,3,0,0,7)
→(22,0,10,0,0)
→(12,0,10,10,0)
→(15,0,10,0,7)
→(22,0,3,0,7)
→(22,0,0,10,0)
：
→(25,0,0,0,7)
：
この樹形図は、「（単方向）リスト」と呼ばれるデータ構造で、BASICにはありません。
そこで、配列変数Q(,)を使って実装しています。
終了パターンが見つかると、この矢印を遡りその過程を表示します。
サンプル・プログラム ※２進モードで実行のこと
!油分け算
! 32リットルの容器に水が一杯に満たされている。
! この容器とは別に、10リットルの空の容器が３つ、７リットルの空の容器が１つある。
! これらの容器を用いて、８リットルずつに分けたい。どうしたらよいか？
LET C=5 !容器の数 ※←←←←←
!LET C=4
!LET C=3
DIM B(C) !容器の容量 ※←←←←←
DATA 32,10,10,10,7
!DATA 21,11,8,5
!DATA 10,7,3
MAT READ B
! 1. 容器いっぱいに水を満たす
! 2. 容器を空にする
! 3. 他の容器に水を移す
DIM W(C)
SUB move(x,y) !xからyへ移動する
LET t=MIN(W(x),B(y)-W(y)) !分量を算出する
LET W(x)=W(x)-t
LET W(y)=W(y)+t
END SUB
DIM Q(0 TO 8000,0 TO C) !配分のパターン（局面） ※樹形図
MAT Q=ZER
DATA 32,0,0,0,0 !容器の初期状態 ※←←←←←
!DATA 21,0,0,0
!DATA 10,0,0
FOR i=1 TO C
READ Q(0,i)
NEXT i
LET Q(0,0)=-1 !単方向リスト ※番兵
DIM G(C) !最終パターン ※←←←←←
DATA 8,8,8,8,0
!DATA 7,7,7,0
!DATA 5,5,0
MAT READ G
LET top=0 !n手目の展開
LET btm=0
LET n=0
DO WHILE n<=30 !手の上限 ※幅優先探索
PRINT n; top;btm !debug
LET new_btm=btm
FOR i=top TO btm !(n+1)手目へと展開する
DIM M(C)
FOR k=1 TO C !元パターンを復元する
LET M(k)=Q(i,k)
NEXT k
FOR h=0 TO Perm(C,2)-1 !移動は高々20通り
DIM P(2)
CALL Num2Perm(h,P,C,2)
MAT W=M !restore it
CALL move(P(1),P(2)) !移動してみる
FOR x=new_btm TO 0 STEP -1 !最新のものから順に、既出のパターンかどうか確認する
FOR k=1 TO C
IF W(k)<>Q(x,k) THEN EXIT FOR
NEXT k
IF k>C THEN EXIT FOR !一致する
NEXT x
IF x<0 THEN !新しい局面なら、登録する
LET new_btm=new_btm+1 !登録位置を算出する
FOR k=1 TO C !パターン
LET Q(new_btm,k)=W(k)
NEXT k
LET Q(new_btm,0)=i !リンクする
FOR k=1 TO C !終了パターンかどうか確認する
IF W(k)<>G(k) THEN EXIT FOR
NEXT k
IF k>C THEN !解を表示する
LET d=n+1
PRINT "解=";d;"手"
LET x=new_btm !記録を元に「手」を遡る
DO UNTIL x<0
PRINT USING "###:": d;
FOR k=1 TO C
PRINT USING "###": Q(x,k);
NEXT k
PRINT
LET x=Q(x,0) !後方へ
LET d=d-1
LOOP
LET new_btm=new_btm-1 !他を探すため登録しない
!!!STOP
END IF
END IF
NEXT h
NEXT i
LET n=n+1 !次へ
LET top=btm+1
LET btm=new_btm
LOOP
END
EXTERNAL SUB Num2Perm(h, A(),N,R) !番号から順列パターンを生成する ※辞書式順序
LET v=h !非負の10進数整数を(階乗)進数へ
FOR j=1 TO R
LET w=N-R+j
LET t=INT(v/w)
LET A(R-j+1)=v-t*w +1 !(階乗)進数の各桁の値＋１ A[1..R]=PERM(N-1,R-1) … PERM(N-j,R-j) … PERM(N-R,0)
LET v=t
NEXT j
FOR j=R-1 TO 1 STEP -1 !順列パターンへ
FOR k=j+1 TO R
IF A(k)>=A(j) THEN LET A(k)=A(k)+1
NEXT k
NEXT j
END SUB
!アルゴリズム、パズル、幅優先探索、単方向リスト
|
|