集合の計算

!集合 A　⇒　配列変数 A$()
!要素 ai　⇒　添え字iでの値 A$(i)=ai
!要素の数 N(A)　⇒　A$(0)=STR$(nA)
!例. A={1,2,5}の場合、A$(1)="1",A$(2)="2",A$(3)="5"、A$(0)="3"

OPTION BASE 0

LET TRUE=1 !真
LET FALSE=0 !偽

FUNCTION N(A$()) !要素の個数
IF A$(0)="" THEN LET N=0 ELSE LET N=VAL(A$(0))
END FUNCTION
SUB empty(A$()) !空集合にする　A=φ
LET A$(0)=STR$(0)
FOR i=1 TO UBOUND(A$)
LET A$(i)=""
NEXT i
END SUB
SUB element(x$, A$()) !xをAの要素とする　x∈A
LET nA=N(A$)
FOR i=1 TO nA
IF x$=A$(i) THEN EXIT SUB !既に存在するなら、追加しない
NEXT i
LET nA=nA+1
LET A$(nA)=x$
LET A$(0)=STR$(nA)
END SUB
SUB copy(A$(), C$()) !コピーする　C=A
CALL empty(C$)
LET nA=N(A$)
FOR i=1 TO nA
LET C$(i)=A$(i)
NEXT i
LET C$(0)=STR$(nA)
END SUB
SUB union(A$(),B$(), C$()) !和　A∪B
CALL copy(A$, C$)
LET nB=N(B$)
FOR j=1 TO nB
CALL element(B$(j), C$)
NEXT j
END SUB
SUB intersect(A$(),B$(), C$()) !積　A∩B
CALL empty(C$)
LET nA=N(A$)
LET nB=N(B$)
LET nC=N(C$)
FOR i=1 TO nA
FOR j=1 TO nB
IF A$(i)=B$(j) THEN !一致するなら
LET nC=nC+1
LET C$(nC)=B$(j)
END IF
NEXT j
NEXT i
LET C$(0)=STR$(nC)
END SUB
SUB except(A$(),B$() ,C$()) !差　A-B
CALL empty(C$)
LET nA=N(A$)
LET nB=N(B$)
LET nC=N(C$)
FOR i=1 TO nA
FOR j=1 TO nB
IF A$(i)=B$(j) THEN EXIT FOR
NEXT j
IF j>nB THEN !一致しないなら
LET nC=nC+1
LET C$(nC)=A$(i)
END IF
NEXT i
LET C$(0)=STR$(nC)
END SUB
SUB cross(A$(),B$(), C$()) !直積　A×B　※２次元
CALL empty(C$)
LET nA=N(A$)
LET nB=N(B$)
FOR i=1 TO nA
FOR j=1 TO nB
LET C$(i*j)=A$(i)&" "&B$(j)
NEXT j
NEXT i
LET nC=nA*nB
LET C$(0)=STR$(nC)
END SUB
SUB subset(A$(),m,n, C$()) !部分集合　C⊆A　※m<n
CALL empty(C$)
FOR i=m TO n
LET C$(i-m+1)=A$(i)
NEXT i
LET nC=n-m+1
LET C$(0)=STR$(nC)
END SUB

つづき（サブルーチン部分）

FUNCTION isEmpty(A$()) !空集合かどうか確認する　A=φ？
LET nA=N(A$)
IF nA=0 THEN LET isEmpty=TRUE ELSE LET isEmpty=FALSE
END FUNCTION
FUNCTION isElement(x$,A$()) !要素かどうか確認する　x∈A？
LET isElement=TRUE
LET nA=N(A$)
FOR i=1 TO nA
IF x$=A$(i) THEN EXIT FUNCTION !要素として存在するなら
NEXT i
LET isElement=FALSE
END FUNCTION
FUNCTION isEqual(C$(),A$()) !等しいかどうか確認する　C=A？
LET isEqual=FALSE
IF N(C$)=N(A$) AND isSubset(C$,A$)=TRUE THEN LET isEqual=TRUE
END FUNCTION
FUNCTION isSubset(C$(), A$()) !部分集合かどうか確認する　C⊆A？
LET nC=N(C$)
IF nC=0 THEN !空集合なら
ELSE
LET isSubset=FALSE
FOR j=1 TO nC !すべてのx∈Cで、
IF isElement(C$(j),A$)=FALSE THEN EXIT FUNCTION !要素として存在しないなら
NEXT j
END IF
LET isSubset=TRUE
END FUNCTION

!補助ルーチン
SUB PrintOut(nm$,C$()) !外延的表示（要素を並べる）
LET nC=N(C$)
IF nC<1 THEN
PRINT nm$;"=φ"
ELSE
PRINT nm$;"={ ";
FOR i=1 TO nC-1
IF POS(C$(i)," ")>0 THEN !２次元なら
PRINT "{ ";C$(i);" } ";
ELSE
PRINT C$(i);", ";
END IF
IF MOD(i,10)=0 AND nC>10 THEN
PRINT
PRINT REPEAT$(" ",BLEN(nm$&"={ "));
END IF
NEXT i
IF POS(C$(i)," ")>0 THEN !最後の要素
PRINT "{ ";C$(i);" } }"
ELSE
PRINT C$(i);" }"
END IF
END IF
END SUB
SUB conv2to1(A$, C$()) !２次元から１次元へ変換する
CALL empty(C$)
LET nC=N(C$)
IF A$="" THEN EXIT SUB
LET tt$=""
FOR i=1 TO LEN(A$) !文字列の終りまで
LET t$=mid$(A$,i,1)
IF t$="," OR t$=" " THEN !分離文字なら
LET nC=nC+1
LET C$(nC)=tt$ !設定する
LET tt$=""
ELSE
LET tt$=tt$&t$
END IF
NEXT i
LET nC=nC+1
LET C$(nC)=tt$ !設定する
LET C$(0)=STR$(nC)
END SUB
SUB sort(A$()) !昇順に並べ替える
LET nA=N(A$)
FOR i=1 TO nA-1
FOR j=i TO nA
IF A$(j)<A$(i) THEN
LET t$=A$(j) !swap A$(i),A$(j)
LET A$(j)=A$(i)
LET A$(i)=t$
END IF
NEXT j
NEXT i
END SUB

典型的な問題（高校数学）

!３桁の自然数のうち　U={100,101,102, … ,999}
DIM U$(1000)
FOR k=100 TO 999 !要素の定義
CALL element(STR$(k),U$) !k∈U
NEXT k
PRINT N(U$) !N(U)
CALL printout("U",U$) !表示して確認する

!６で割り切れる数　A
DIM A$(1000)
FOR k=INT(100/6)+1 TO INT(1000/6)
CALL element(STR$(k*6),A$) !k*6∈A
NEXT k
PRINT N(A$)
CALL printout("A",A$)

!８で割り切れない数　￢B=U-B
DIM B$(1000) !まず、８で割り切れる数を求めて、、、
FOR k=INT(100/8)+1 TO INT(1000/8)-1 !1000は除く
CALL element(STR$(k*8),B$) !k*8∈B
NEXT k
PRINT N(B$)
CALL printout("B",B$)

DIM Bbar$(1000) !その補集合
CALL except(U$,B$, Bbar$) !U-B
PRINT N(Bbar$)
CALL printout("￢B",Bbar$)

!６でも８でも割り切れる数　A∩B
DIM AnB$(1000)
CALL intersect(A$,B$, AnB$)
PRINT N(AnB$)
CALL printout("A∩B",AnB$)

!６でも８でも割り切れない数　￢A∩￢B=￢(A∪B)=U-(A∪B)　※ド・モルガンの法則
DIM AuB$(1000),F$(1000)
CALL union(A$,B$, AuB$) !A∪B
CALL sort(AuB$)
PRINT N(AuB$)
CALL printout("A∪B",AuB$)
CALL except(U$,AuB$, F$) !U-(A∪B)
PRINT N(F$)
CALL printout("￢A∩￢B",F$)

END

!川渡りパズル（狼とヤギと野菜）をつくる

DIM X$(1) !集合の定義
DATA 1, "人" !要素の個数、要素の定義
MAT READ X$

DIM Y$(3)
DATA 3, "狼","ヤギ","野菜"
MAT READ Y$

!初期化する
DIM Z1$(2),Z2$(2) !禁じ手　Y$={狼,ヤギ,野菜}
CALL subset(Y$,1,2, Z1$) !{狼,ヤギ}
CALL subset(Y$,2,3, Z2$) !{ヤギ,野菜}

DIM D$(10),W$(10) !作業変数
CALL cross(X$,Y$, W$) !乗船の組合せ=(人×物)∪人
CALL union(X$,W$, D$)

DIM bank$(4),opposite_bank$(4),ship$(2) !岸、対岸、船
CALL union(X$,Y$, bank$) !岸=A∪B
CALL empty(ship$) !船=φ
CALL empty(opposite_bank$) !対岸=φ

LET st=0 !ステップ数

LET GameClear=FLASE
DO WHILE GameClear=FLASE !ゲームクリアまで
LET st=st+1
CALL DisplayStatus !現状を表示する

LET aboard=FALSE
DO
IF MOD(st,2)=0 THEN PRINT "対";
PRINT "岸から舟に乗るものを選択してください。（";st;"回目）"
FOR k=1 TO N(D$)
CALL conv2to1(D$(k), W$) !!!PRINT USING"##=<######":k,D$(k)
CALL PrintOut(STR$(k),W$)
NEXT k

DO
INPUT PROMPT "番号を入力してください。":m !選択する
PRINT
LOOP UNTIL m>0 AND m=<N(D$)

CALL conv2to1(D$(m), ship$) !船⊆岸なら、乗船は可能だが、、、
CALL PrintOut("debug",ship$) !debug debug debug
IF MOD(st,2)=1 THEN
CALL copy(bank$, W$)
ELSE
CALL copy(opposite_bank$, W$)
END IF
IF isSubset(ship$,W$)=FALSE THEN
PRINT "選択できません。"
PRINT

ELSE
DIM C$(10) !作業変数

CALL except(W$,ship$, C$) !岸-船
IF check(C$)=TRUE THEN !岸に残されたものを確認しないと、、、
PRINT "禁じ手で選択できません。"
PRINT
ELSE
IF MOD(st,2)=1 THEN
CALL copy(C$, bank$)
ELSE
CALL copy(C$, opposite_bank$)
END IF
LET aboard=TRUE
END IF

END IF
LOOP UNTIL aboard=TRUE !乗船を確認する

つづき

!川を渡る
CALL DisplayStatus !現状を表示する

!船を降りて、対岸を確認する
IF MOD(st,2)=1 THEN
CALL union(opposite_bank$,ship$, C$) !対岸∪船
CALL copy(C$, opposite_bank$)
ELSE
CALL union(bank$,ship$, C$)
CALL copy(C$, bank$)
END IF
CALL empty(ship$) !船=φ

LET GameClear=isEmpty(bank$) !渡りきったら
LOOP

CALL DisplayStatus !現状を表示する
PRINT st;"回でクリア！"

FUNCTION check(C$()) !禁じ手かどうか確認する
LET check=FALSE
IF isSubset(Z1$,C$)=TRUE THEN LET check=TRUE
IF isSubset(Z2$,C$)=TRUE THEN LET check=TRUE
END FUNCTION
SUB DisplayStatus !現状を表示する
CALL PrintOut("岸",bank$)
CALL PrintOut("船",ship$)
CALL PrintOut("対岸",opposite_bank$)
PRINT
END SUB

END

参考、解答を得るプログラム

!狼、やぎ、野菜の有無を２進数で表す。
!狼は２ビット目、やぎは１ビット目、野菜は０ビット目
!例. 岸に狼と野菜があれば、K=2^2+2^0=5
!同様に、移動するものもこの値で表現する。
!例. 狼と野菜を移動するのは、K=2^2+2^0=5だが、１つまでなのでこれは禁じ手となる。

FUNCTION f(i,p) !評価関数　※対岸に移動した数
SELECT CASE p
CASE 0 !何もない
LET f=N2
CASE 1,2,4 !野菜、やぎ、狼
IF MOD(i,2)=1 THEN LET f=N2+1 ELSE LET f=N2-1
CASE ELSE
PRINT "移動できません。（移動は１つまで）"
STOP
END SELECT
END FUNCTION

LET TRUE=1
LET FALSE=0

LET K=7 !岸には{狼,やぎ,野菜}
LET K2=0 !対岸には何もない
LET N2=0 !対岸の個数

FOR i=1 TO 20 !ステップ数　※奇数は岸⇒対岸、偶数は対岸⇒岸
PRINT "●";i;"回目"

IF MOD(i,2)=1 THEN LET x=K ELSE LET x=K2 !どちらの岸か
LET m0=m !前に移動したもの
LET n=-999

IF m0=0 THEN !同じものを移動　※元に戻る
ELSE
CALL www(i,x,0, m,n) !何も移動しないと仮定する
END IF
FOR j=0 TO 2 !野菜、やぎ、狼を移動すると仮定する
IF m0=2^j THEN
ELSE
IF MOD(INT(x/2^j),2)=1 THEN CALL www(i,x,2^j, m,n) !ビットチェック
END IF
NEXT j

PRINT "{ "; !この手にする
CALL printOut(m)
PRINT "}を移動"

IF MOD(i,2)=1 THEN
LET K=K-m !状況を更新する
LET K2=K2+m
ELSE
LET K=K+m
LET K2=K2-m
END IF
LET N2=n

PRINT "岸={ ";
IF MOD(i,2)=0 THEN PRINT "人 ";
CALL printOut(K)
PRINT "}","対岸={ ";
IF MOD(i,2)=1 THEN PRINT "人 ";
CALL printOut(K2)
PRINT "}"
PRINT

IF K=0 THEN EXIT FOR !クリアなら
NEXT i

SUB www(i,x,p, m,n) !移動できるか確認する
LET v0=f(i,p) !pで検討

PRINT "{ ";
CALL printOut(p)
PRINT "}を移動すれば対岸は";v0;"になる"

IF check(x,p)=FALSE THEN !残りは岸に残せれば、採用する
IF v0>=n THEN !今までより、良い手で
PRINT "採用！"
LET n=v0 !対岸の個数
LET m=p !移動するもの
ELSE
PRINT "不採用！"
END IF
ELSE
PRINT "禁じ手です！"
END IF
END SUB

FUNCTION check(x,p) !禁じ手かどうか確認する
LET t=x-p !岸に残すもの
SELECT CASE t
CASE 3,6,7 !{やぎ,野菜}、{狼,やぎ}、{狼,やぎ,野菜}
LET check=TRUE
CASE ELSE
LET check=FALSE
END SELECT
END FUNCTION

SUB PrintOut(p)
IF MOD(INT(p/4),2)=1 THEN PRINT "狼 ";
IF MOD(INT(p/2),2)=1 THEN PRINT "やぎ ";
IF MOD(p,2)=1 THEN PRINT "野菜 ";
END SUB

END

集合の計算	返事を書くノートメニュー
山中和義 <drdlxujciw> 2007/07/13 13:16:04 ** この記事は2回修正されてます
!集合 A　⇒　配列変数 A$() !要素 ai　⇒　添え字iでの値 A$(i)=ai !要素の数 N(A)　⇒　A$(0)=STR$(nA) !例. A={1,2,5}の場合、A$(1)="1",A$(2)="2",A$(3)="5"、A$(0)="3" OPTION BASE 0 LET TRUE=1 !真 LET FALSE=0 !偽 FUNCTION N(A$()) !要素の個数 IF A$(0)="" THEN LET N=0 ELSE LET N=VAL(A$(0)) END FUNCTION SUB empty(A$()) !空集合にする　A=φ LET A$(0)=STR$(0) FOR i=1 TO UBOUND(A$) LET A$(i)="" NEXT i END SUB SUB element(x$, A$()) !xをAの要素とする　x∈A LET nA=N(A$) FOR i=1 TO nA IF x$=A$(i) THEN EXIT SUB !既に存在するなら、追加しない NEXT i LET nA=nA+1 LET A$(nA)=x$ LET A$(0)=STR$(nA) END SUB SUB copy(A$(), C$()) !コピーする　C=A CALL empty(C$) LET nA=N(A$) FOR i=1 TO nA LET C$(i)=A$(i) NEXT i LET C$(0)=STR$(nA) END SUB SUB union(A$(),B$(), C$()) !和　A∪B CALL copy(A$, C$) LET nB=N(B$) FOR j=1 TO nB CALL element(B$(j), C$) NEXT j END SUB SUB intersect(A$(),B$(), C$()) !積　A∩B CALL empty(C$) LET nA=N(A$) LET nB=N(B$) LET nC=N(C$) FOR i=1 TO nA FOR j=1 TO nB IF A$(i)=B$(j) THEN !一致するなら LET nC=nC+1 LET C$(nC)=B$(j) END IF NEXT j NEXT i LET C$(0)=STR$(nC) END SUB SUB except(A$(),B$() ,C$()) !差　A-B CALL empty(C$) LET nA=N(A$) LET nB=N(B$) LET nC=N(C$) FOR i=1 TO nA FOR j=1 TO nB IF A$(i)=B$(j) THEN EXIT FOR NEXT j IF j>nB THEN !一致しないなら LET nC=nC+1 LET C$(nC)=A$(i) END IF NEXT i LET C$(0)=STR$(nC) END SUB SUB cross(A$(),B$(), C$()) !直積　A×B　※２次元 CALL empty(C$) LET nA=N(A$) LET nB=N(B$) FOR i=1 TO nA FOR j=1 TO nB LET C$(ij)=A$(i)&" "&B$(j) NEXT j NEXT i LET nC=nAnB LET C$(0)=STR$(nC) END SUB SUB subset(A$(),m,n, C$()) !部分集合　C⊆A　※m<n CALL empty(C$) FOR i=m TO n LET C$(i-m+1)=A$(i) NEXT i LET nC=n-m+1 LET C$(0)=STR$(nC) END SUB

Re: 集合の計算	返事を書くノートメニュー
山中和義 <drdlxujciw> 2007/07/13 13:17:22 ** この記事は3回修正されてます
つづき（サブルーチン部分） FUNCTION isEmpty(A$()) !空集合かどうか確認する　A=φ？ LET nA=N(A$) IF nA=0 THEN LET isEmpty=TRUE ELSE LET isEmpty=FALSE END FUNCTION FUNCTION isElement(x$,A$()) !要素かどうか確認する　x∈A？ LET isElement=TRUE LET nA=N(A$) FOR i=1 TO nA IF x$=A$(i) THEN EXIT FUNCTION !要素として存在するなら NEXT i LET isElement=FALSE END FUNCTION FUNCTION isEqual(C$(),A$()) !等しいかどうか確認する　C=A？ LET isEqual=FALSE IF N(C$)=N(A$) AND isSubset(C$,A$)=TRUE THEN LET isEqual=TRUE END FUNCTION FUNCTION isSubset(C$(), A$()) !部分集合かどうか確認する　C⊆A？ LET nC=N(C$) IF nC=0 THEN !空集合なら ELSE LET isSubset=FALSE FOR j=1 TO nC !すべてのx∈Cで、 IF isElement(C$(j),A$)=FALSE THEN EXIT FUNCTION !要素として存在しないなら NEXT j END IF LET isSubset=TRUE END FUNCTION !補助ルーチン SUB PrintOut(nm$,C$()) !外延的表示（要素を並べる） LET nC=N(C$) IF nC<1 THEN PRINT nm$;"=φ" ELSE PRINT nm$;"={ "; FOR i=1 TO nC-1 IF POS(C$(i)," ")>0 THEN !２次元なら PRINT "{ ";C$(i);" } "; ELSE PRINT C$(i);", "; END IF IF MOD(i,10)=0 AND nC>10 THEN PRINT PRINT REPEAT$(" ",BLEN(nm$&"={ ")); END IF NEXT i IF POS(C$(i)," ")>0 THEN !最後の要素 PRINT "{ ";C$(i);" } }" ELSE PRINT C$(i);" }" END IF END IF END SUB SUB conv2to1(A$, C$()) !２次元から１次元へ変換する CALL empty(C$) LET nC=N(C$) IF A$="" THEN EXIT SUB LET tt$="" FOR i=1 TO LEN(A$) !文字列の終りまで LET t$=mid$(A$,i,1) IF t$="," OR t$=" " THEN !分離文字なら LET nC=nC+1 LET C$(nC)=tt$ !設定する LET tt$="" ELSE LET tt$=tt$&t$ END IF NEXT i LET nC=nC+1 LET C$(nC)=tt$ !設定する LET C$(0)=STR$(nC) END SUB SUB sort(A$()) !昇順に並べ替える LET nA=N(A$) FOR i=1 TO nA-1 FOR j=i TO nA IF A$(j)<A$(i) THEN LET t$=A$(j) !swap A$(i),A$(j) LET A$(j)=A$(i) LET A$(i)=t$ END IF NEXT j NEXT i END SUB

Re: つづき（サブルーチン部分）	返事を書くノートメニュー
山中和義 <drdlxujciw> 2007/07/13 13:19:43 ** この記事は4回修正されてます
典型的な問題（高校数学） !３桁の自然数のうち　U={100,101,102, … ,999} DIM U$(1000) FOR k=100 TO 999 !要素の定義 CALL element(STR$(k),U$) !k∈U NEXT k PRINT N(U$) !N(U) CALL printout("U",U$) !表示して確認する !６で割り切れる数　A DIM A$(1000) FOR k=INT(100/6)+1 TO INT(1000/6) CALL element(STR$(k6),A$) !k6∈A NEXT k PRINT N(A$) CALL printout("A",A$) !８で割り切れない数　￢B=U-B DIM B$(1000) !まず、８で割り切れる数を求めて、、、 FOR k=INT(100/8)+1 TO INT(1000/8)-1 !1000は除く CALL element(STR$(k8),B$) !k8∈B NEXT k PRINT N(B$) CALL printout("B",B$) DIM Bbar$(1000) !その補集合 CALL except(U$,B$, Bbar$) !U-B PRINT N(Bbar$) CALL printout("￢B",Bbar$) !６でも８でも割り切れる数　A∩B DIM AnB$(1000) CALL intersect(A$,B$, AnB$) PRINT N(AnB$) CALL printout("A∩B",AnB$) !６でも８でも割り切れない数　￢A∩￢B=￢(A∪B)=U-(A∪B)　※ド・モルガンの法則 DIM AuB$(1000),F$(1000) CALL union(A$,B$, AuB$) !A∪B CALL sort(AuB$) PRINT N(AuB$) CALL printout("A∪B",AuB$) CALL except(U$,AuB$, F$) !U-(A∪B) PRINT N(F$) CALL printout("￢A∩￢B",F$) END

Re: つづき（サブルーチン部分）	返事を書くノートメニュー
山中和義 <drdlxujciw> 2007/07/13 13:25:26 ** この記事は3回修正されてます
!川渡りパズル（狼とヤギと野菜）をつくる DIM X$(1) !集合の定義 DATA 1, "人" !要素の個数、要素の定義 MAT READ X$ DIM Y$(3) DATA 3, "狼","ヤギ","野菜" MAT READ Y$ !初期化する DIM Z1$(2),Z2$(2) !禁じ手　Y$={狼,ヤギ,野菜} CALL subset(Y$,1,2, Z1$) !{狼,ヤギ} CALL subset(Y$,2,3, Z2$) !{ヤギ,野菜} DIM D$(10),W$(10) !作業変数 CALL cross(X$,Y$, W$) !乗船の組合せ=(人×物)∪人 CALL union(X$,W$, D$) DIM bank$(4),opposite_bank$(4),ship$(2) !岸、対岸、船 CALL union(X$,Y$, bank$) !岸=A∪B CALL empty(ship$) !船=φ CALL empty(opposite_bank$) !対岸=φ LET st=0 !ステップ数 LET GameClear=FLASE DO WHILE GameClear=FLASE !ゲームクリアまで LET st=st+1 CALL DisplayStatus !現状を表示する LET aboard=FALSE DO IF MOD(st,2)=0 THEN PRINT "対"; PRINT "岸から舟に乗るものを選択してください。（";st;"回目）" FOR k=1 TO N(D$) CALL conv2to1(D$(k), W$) !!!PRINT USING"##=<######":k,D$(k) CALL PrintOut(STR$(k),W$) NEXT k DO INPUT PROMPT "番号を入力してください。":m !選択する PRINT LOOP UNTIL m>0 AND m=<N(D$) CALL conv2to1(D$(m), ship$) !船⊆岸なら、乗船は可能だが、、、 CALL PrintOut("debug",ship$) !debug debug debug IF MOD(st,2)=1 THEN CALL copy(bank$, W$) ELSE CALL copy(opposite_bank$, W$) END IF IF isSubset(ship$,W$)=FALSE THEN PRINT "選択できません。" PRINT ELSE DIM C$(10) !作業変数 CALL except(W$,ship$, C$) !岸-船 IF check(C$)=TRUE THEN !岸に残されたものを確認しないと、、、 PRINT "禁じ手で選択できません。" PRINT ELSE IF MOD(st,2)=1 THEN CALL copy(C$, bank$) ELSE CALL copy(C$, opposite_bank$) END IF LET aboard=TRUE END IF END IF LOOP UNTIL aboard=TRUE !乗船を確認する

Re: !川渡りパズル（狼とヤギと野菜）をつくる	返事を書くノートメニュー
山中和義 <drdlxujciw> 2007/07/13 13:26:24 ** この記事は2回修正されてます
つづき !川を渡る CALL DisplayStatus !現状を表示する !船を降りて、対岸を確認する IF MOD(st,2)=1 THEN CALL union(opposite_bank$,ship$, C$) !対岸∪船 CALL copy(C$, opposite_bank$) ELSE CALL union(bank$,ship$, C$) CALL copy(C$, bank$) END IF CALL empty(ship$) !船=φ LET GameClear=isEmpty(bank$) !渡りきったら LOOP CALL DisplayStatus !現状を表示する PRINT st;"回でクリア！" FUNCTION check(C$()) !禁じ手かどうか確認する LET check=FALSE IF isSubset(Z1$,C$)=TRUE THEN LET check=TRUE IF isSubset(Z2$,C$)=TRUE THEN LET check=TRUE END FUNCTION SUB DisplayStatus !現状を表示する CALL PrintOut("岸",bank$) CALL PrintOut("船",ship$) CALL PrintOut("対岸",opposite_bank$) PRINT END SUB END

Re: つづき	返事を書くノートメニュー
山中和義 <drdlxujciw> 2007/07/13 20:39:28
参考、解答を得るプログラム !狼、やぎ、野菜の有無を２進数で表す。 !狼は２ビット目、やぎは１ビット目、野菜は０ビット目 !例. 岸に狼と野菜があれば、K=2^2+2^0=5 !同様に、移動するものもこの値で表現する。 !例. 狼と野菜を移動するのは、K=2^2+2^0=5だが、１つまでなのでこれは禁じ手となる。 FUNCTION f(i,p) !評価関数　※対岸に移動した数 SELECT CASE p CASE 0 !何もない LET f=N2 CASE 1,2,4 !野菜、やぎ、狼 IF MOD(i,2)=1 THEN LET f=N2+1 ELSE LET f=N2-1 CASE ELSE PRINT "移動できません。（移動は１つまで）" STOP END SELECT END FUNCTION LET TRUE=1 LET FALSE=0 LET K=7 !岸には{狼,やぎ,野菜} LET K2=0 !対岸には何もない LET N2=0 !対岸の個数 FOR i=1 TO 20 !ステップ数　※奇数は岸⇒対岸、偶数は対岸⇒岸 PRINT "●";i;"回目" IF MOD(i,2)=1 THEN LET x=K ELSE LET x=K2 !どちらの岸か LET m0=m !前に移動したもの LET n=-999 IF m0=0 THEN !同じものを移動　※元に戻る ELSE CALL www(i,x,0, m,n) !何も移動しないと仮定する END IF FOR j=0 TO 2 !野菜、やぎ、狼を移動すると仮定する IF m0=2^j THEN ELSE IF MOD(INT(x/2^j),2)=1 THEN CALL www(i,x,2^j, m,n) !ビットチェック END IF NEXT j PRINT "{ "; !この手にする CALL printOut(m) PRINT "}を移動" IF MOD(i,2)=1 THEN LET K=K-m !状況を更新する LET K2=K2+m ELSE LET K=K+m LET K2=K2-m END IF LET N2=n PRINT "岸={ "; IF MOD(i,2)=0 THEN PRINT "人 "; CALL printOut(K) PRINT "}","対岸={ "; IF MOD(i,2)=1 THEN PRINT "人 "; CALL printOut(K2) PRINT "}" PRINT IF K=0 THEN EXIT FOR !クリアなら NEXT i SUB www(i,x,p, m,n) !移動できるか確認する LET v0=f(i,p) !pで検討 PRINT "{ "; CALL printOut(p) PRINT "}を移動すれば対岸は";v0;"になる" IF check(x,p)=FALSE THEN !残りは岸に残せれば、採用する IF v0>=n THEN !今までより、良い手で PRINT "採用！" LET n=v0 !対岸の個数 LET m=p !移動するもの ELSE PRINT "不採用！" END IF ELSE PRINT "禁じ手です！" END IF END SUB FUNCTION check(x,p) !禁じ手かどうか確認する LET t=x-p !岸に残すもの SELECT CASE t CASE 3,6,7 !{やぎ,野菜}、{狼,やぎ}、{狼,やぎ,野菜} LET check=TRUE CASE ELSE LET check=FALSE END SELECT END FUNCTION SUB PrintOut(p) IF MOD(INT(p/4),2)=1 THEN PRINT "狼 "; IF MOD(INT(p/2),2)=1 THEN PRINT "やぎ "; IF MOD(p,2)=1 THEN PRINT "野菜 "; END SUB END