问题描述:
河左岸有三个修道士,三个野人和一条船,假定船最多只能运两个人,且任何岸边的野人数目不得超过修道士,否则修道士就会被野人吃掉。
如何才能把修道士和野人都运到右岸?
Savage.rb
SAVAGE = 0
BOANERGES = 1
DEEP = 5
#记录状态
class Status
@@StatusList = Array.new
@@Pos = -1
attr_writer :nSavage #岸边野人的数量,全部到对岸为0
attr_writer :nBoanerges #岸边传教士的数量,全部到对岸为0
attr_writer :nSide #船的位置,在此岸为-1,对岸为1
attr_writer :nMoveSavage #渡河的野人的数量,用于递归时记录操作状态
attr_writer :nMoveBoanerges #渡河的传教士的数量,用于递归时记录操作状态
attr_reader :nSavage
attr_reader :nBoanerges
attr_reader :nSide
attr_reader :nMoveSavage
attr_reader :nMoveBoanerges
def initialize()
@nSavage = 3
@nBoanerges = 3
@nSide = -1
@nMoveSavage = 0
@nMoveBoanerges = 0
end
def Status.getList()
return @@StatusList
end
def Status.getPos()
return @@Pos
end
def Status.addStatus(stat)
@@StatusList.push(stat)
@@Pos += 1
end
def Status.delStatus()
@@StatusList.pop()
@@Pos -= 1
end
end
class Ship
def Ship.hasNextStep(stat)
store = [[],[],[],[],[]]
if stat.nSide == -1 then
store[0][SAVAGE] = 2
store[0][BOANERGES] = 0
store[1][SAVAGE] = 1
store[1][BOANERGES] = 1
store[2][SAVAGE] = 0
store[2][BOANERGES] = 2
store[3][SAVAGE] = 1
store[3][BOANERGES] = 0
store[4][SAVAGE] = 0
store[4][BOANERGES] = 1
elsif stat.nSide == 1
store[0][SAVAGE] = 0
store[0][BOANERGES] = 1
store[1][SAVAGE] = 1
store[1][BOANERGES] = 0
store[2][SAVAGE] = 0
store[2][BOANERGES] = 2
store[3][SAVAGE] = 1
store[3][BOANERGES] = 1
store[4][SAVAGE] = 2
store[4][BOANERGES] = 0
end
iStart = 0
if stat.nMoveSavage == 0 && stat.nMoveBoanerges == 0
iStart = 0
else
for iStart in 0...DEEP
puts iStart
if stat.nMoveSavage == store[iStart][SAVAGE] && stat.nMoveBoanerges == store[iStart][BOANERGES]
break
end
end
iStart += 1
end
if (iStart < DEEP)
i = 0
for i in iStart...DEEP
nSideSavage = stat.nSavage + stat.nSide * store[i][SAVAGE]
nSideBoanerges = stat.nBoanerges + stat.nSide * store[i][BOANERGES]
nBesideSavage = 3 - nSideSavage
nBesideBoanerges = 3 - nSideBoanerges
#传教士数量大于等于野人或为零
if ((nSideSavage <= nSideBoanerges || nSideBoanerges == 0) &&
(nBesideSavage <= nBesideBoanerges || nBesideBoanerges == 0) &&
nSideSavage >= 0 && nSideBoanerges >= 0 && nBesideSavage >= 0 && nBesideBoanerges >= 0) then
#如果本此解等于上次,放弃
if Status.getPos > 0
if (Status.getList()[Status.getPos - 1].nMoveBoanerges == store[i][BOANERGES] &&
Status.getList()[Status.getPos - 1].nMoveSavage == store[i][SAVAGE])
next
end
end
break
end
end
if i < DEEP
stat.nMoveSavage = store[i][SAVAGE]
stat.nMoveBoanerges = store[i][BOANERGES]
return true
end
end
return false;
end
#递归函数
def Ship.find(stat)
if hasNextStep(stat)
pNew = Status.new
pNew.nSavage = stat.nSavage + stat.nMoveSavage * stat.nSide
pNew.nBoanerges = stat.nBoanerges + stat.nMoveBoanerges * stat.nSide
pNew.nSide = stat.nSide * -1
pNew.nMoveSavage = 0
pNew.nMoveBoanerges = 0
Status.addStatus(pNew)
if pNew.nSavage == 0 && pNew.nBoanerges == 0
Status.delStatus()
return true
end
return find(pNew)
else
if Status.getPos == 0
return false
end
Status.delStatus()
return find(Status.getList()[Status.getPos])
end
return true
end
end
initStat = Status.new
Status.addStatus(initStat)
if (Ship.find(initStat))
puts "渡河过程如下:"
Status.getList().each do |stat|
print "下次渡河方向:", (stat.nSide == -1) ? "-->" : "<--", " 人数:野人", stat.nMoveSavage, " 传教士", stat.nMoveBoanerges, " 当前此岸野人数:", stat.nSavage, " 传教士数:", stat.nBoanerges, "\n"
end
else
puts "此题无解"
end
print "Press ENTER to return."
$stdin.gets
分享到:
相关推荐
c++实现的修道士野人问题 河的左岸有N个野人和N个修道士以及一条小船,修道士们想用这条小船把所有的人都运到河的右岸,但又受到以下限制: 修道士和野人都会划船,但船一次只能载C人。 在任何岸边,为了防止...
C语言实现野人与修道士过河问题 源代码
野人与修道士问题,C++完整工程项目及源代码
修道士与野人过河问题,包括界面编写。
用三维数组STATE(0:n,0:n,0:n)代表渡河过程中所有状态(合法的和非法的)。STATE(x1,x2,x3)为真,表示该状态已经出现过(“已达”);为假,表示未曾出现过(“未达”)。
假设有n个修道士和n个野人准备渡河,但只有一条能容纳c人的小船,为了防止野人侵犯修道士,要求无论在何处,修道士的个数不得少于野人的人数(除非修道士个数为0)。如果两种人都会划船,试设计一个算法,确定他们...
java实现野人与传教士过河问题,需要c或者c#(有动画演示)见主页。
修道士野人问题C++
问题:设有3个传教士和3个野人来到河边,打算乘一只船从右岸渡到左岸去。该船的负载能力为两人。在任何时候,如果野人人数超过传教士人数,那么...2、在任何岸边,野人数不能超过修道士数,否则修道士将会被野人吃掉
修道士与野人渡河问题C语言源代码,为新手编程人员提供参考
包含prolog求解修道士与野人问题的实验报告、源代码及试验运行截图
在河的右岸有3个修道士、3个野人和一条船,修道士要把所有人都运到河对岸,但是:...(2)在两个岸边,野人数目不能超过修道士的数目,否则后者被吃掉。野人完全服从修道士的任何渡河方案。 包含prolog代码以及实验报告
修道士与野人问题+图书管理系统的课程设计,绝对正确可用
假设有 N 个传教士和 N 个野人准备渡河,但只有一条能容纳 C 人的小船,1 ,为了防止野人伤害传教士,要求无论在何处,传教士的个数不得少于野人的人数(除非传教士个数为 0)。如果两种人都会划船,试设计一个算法...
人工智能实验-修道士与野人问题,A星算法
1.问题重述 在河的左岸有N个传教士、N个野人和一条船,传教士们想...(2)在任何岸边野人数目都不能超过修道士,否则修道士会被野人吃掉。 假定野人会服从任何一种过河安排,请规划出一个确保修道士安全过河的计划。
假设有n个修道士和n个野人准备渡河,但只有一条能容纳c人的小船,为了防止野人侵犯修道士,要求无论在何处,修道士的个数不得少于野人的人数(除非修道士个数为0)。如果两种人都会划船,试设计一个算法,确定他们...
假设有n个修道士和n个野人准备渡河,但只有一条能容纳c人的小船,为了防止野人侵犯修道士,要求无论在何处,修道士的个数不得少于野人的人数(除非修道士个数为0)。如果两种人都会划船,试设计一个算法,确定他们...
修道士&野人的终极测试数据,为修道士或野人的数量从3到11提供了解
传教士与野人问题源码 动态 演示 源码,欢迎大家下载