「宣教師と人食い人」の編集履歴（バックアップ）一覧はこちら

「宣教師と人食い人」(2010/07/16 (金) 14:41:45) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

#asciiart(blockquote){
/***********************************************************
	cannibals.c -- 宣教師と人食い人
***********************************************************/
#N88BASIC

Declare Function sprintf CDECL Lib"msvcrt"(buffer As *Byte, ...) As Long

Const M = 3  /* 宣教師の数 */
Const C = 3  /* 人食い人の数 */
Const B = 2  /* ボートの定員 */

Dim np As Long, solution As Long
Dim mb[ELM((B+1)*(B+2)/2)] As Byte, cb[ELM((B+1)*(B+2)/2)] As Byte
Dim mh[ELM(2*(M+1)*(C+1))] As Byte, ch[ELM(2*(M+1)*(C+1))] As Byte, flag[M,C] As Byte

Dim mmm[10] As *Byte, ccc[10] As *Byte

lstrcpy(mmm, "MMMMMMMMMM")
lstrcpy(ccc, "CCCCCCCCCC")


Sub found(n As Long)  /* 解の表示 */

	Dim i As Long

	Dim sss[999] As Byte
	solution = solution + 1
	Print "解"; solution
	i=0
	While i <= n
		sprintf(sss, Ex"%4d  %-*.*s %-*.*s  /  %-*.*s %-*.*s\n", _
			i, M, mh[i], mmm, C, ch[i], ccc, _
			   M, M - mh[i], mmm, C, C - ch[i], ccc)
		i=i+1
		Print MakeStr(sss)
	Wend
End Sub

Dim static_i As Long
Sub try()  /* 再帰的に試す */

	static_i = 0
	Dim j As Long, m As Long, c As Long
	static_i = static_i + 1
	j = 1
	While j < np
		If (static_i And 1) Then  /* 奇数回目は向こうに行く */
			m = mh[static_i - 1] - mb[j]:  c = ch[static_i - 1] - cb[j]
		Else      /* 偶数回目はこちらに来る */
			m = mh[static_i - 1] + mb[j]:  c = ch[static_i - 1] + cb[j]
		End If
		if (m < 0 Or c < 0 Or m > M Or c > C Or (flag[m,c] And (1 << (static_i And 1)))) Then *CONT
		mh[static_i] = m:  ch[static_i] = c
		If (m = 0 And c = 0) Then 
			found(static_i)
		Else
			flag[m,c] = flag[m,c] Or (1 << (static_i And 1)):  try()
			flag[m,c] = flag[m,c] Xor (1 << (static_i And 1))
		End If
*CONT
		j = j + 1
	Wend
	static_i = static_i - 1
End Sub


Dim m As Long, c As Long
np = 0
m = 0
While m <= B
	c = 0
	While c <= B - m
		If (m = 0 Or m >= c) Then 
			mb[np] = m:  cb[np] = c:  np++
		End If
		c=c+1
	Wend
	m=m+1
Wend

m=0
While m <= M
	c=0
	While c <= C
		If ((m > 0 And m < c) Or (m < M And M - m < C - c)) Then
			flag[m,c] = flag[m,c] Or (1 Or 2)
		End If
		c=c+1
	Wend
	m=m+1
Wend
mh[0] = M:  ch[0] = C:  flag[M,C] = flag[M,C] Or 1
solution = 0:  try()
If (solution = 0) Then Print "解はありません."

}