甜橘子，专注成都网站制作网站设计与营销型网站建设与优化
QQ :532337155
电话：028-86922220
update((X,Y,0),Move,Statu1):- %船在左岸时
从策划到设计制作，每一步都追求做到细腻，制作可持续发展的企业网站。为客户提供成都网站建设、网站设计、网站策划、网页设计、国际域名空间、虚拟主机、网络营销、VI设计、 网站改版、漏洞修补等服务。为客户提供更好的一站式互联网解决方案,以客户的口碑塑造优易品牌,携手广大客户,共同发展进步。
(A,B)=X,
(C,D)=Y,
(E,F)=Move,
C1 is C+E,
D1 is D+F,
A1 is A-E,
B1 is B-F,
Statu1=((A1,B1),(C1,D1),1).
update((X,Y,1),Move,Statu1):- %船在右岸时
(A,B)=X,
(C,D)=Y,
(E,F)=Move,
C1 is C-E,
D1 is D-F,
A1 is A+E,
B1 is B+F,
Statu1=((A1,B1),(C1,D1),0).
?- update(((3,3),(0,0),0),(1,1),X).
X = (2,2),(1,1),1 ;
no
?- update(((0,0),(3,3),0),(1,1),X).
X = (-1,-1),(4,4),1 ;
no
?- update(((1,2),(2,3),1),(3,4),X).
X = (4,6),(-1,-1),0 ;
no
请参看参考资料，有点类似，语言不一样，但是万变不离其中，思想是一样的。
//CrossRiverQuestion.java
import java.util.ArrayList;
import java.util.List;
public class CrossRiverQuestion {
public static void main(String[] args) {
CrossRiverQuestion q = new CrossRiverQuestion(5, 4);
q.solveQuestion();
}
private int peoNum;
private int savageNum;
private ListNode resultList = new ArrayListNode();
public ListNode solveQuestion() {
Node n = new Node(peoNum,savageNum,0,0,0,new ArrayListInteger(),0,0);
boolean dfsResult = dfs(n);
if(dfsResult) {
resultList.add(0,n);
for(Node node : resultList) {
System.out.println("左岸传教士："+node.getLeftPeo()+"左岸野人： "+node.getLeftSavage()+" 右岸传教士： "+node.getRightPeo()+"右岸野人："+node.getRightSavage()+"船上传教士："+node.getOnBoatPeoNum()+"船上野人："+node.getOnBoatSavageNum());
}
return resultList;
}
return null;
}
public CrossRiverQuestion(int peoNum, int savageNum) {
super();
this.peoNum = peoNum;
this.savageNum = savageNum;
}
private boolean dfs(Node n) {
if(n.hasVisited()) return false;
n.addCheckSum();
if(n.getLeftPeo()==0n.getLeftSavage()==0) return true;
if(n.getLeftPeo()0||n.getRightPeo()0||n.getLeftSavage()0||n.getRightSavage()0) {
return false;
}
if(n.getLeftPeo()n.getLeftSavage()n.getLeftPeo()0) return false;
if(n.getRightPeo()n.getRightSavage()n.getRightPeo()0) return false;
if(n.getCURR_STATE()==n.getStateBoatLeft()) {
Node n1 = new Node(n.getLeftPeo()-1,n.getLeftSavage()-1,n.getRightPeo()+1,n.getRightSavage()+1,n.getStateBoatRight(),n.getNodesCheckSum(),1,1);
if(dfs(n1)) {
resultList.add(0,n1);
return true;
}
Node n4 = new Node(n.getLeftPeo()-2,n.getLeftSavage(),n.getRightPeo()+2,n.getRightSavage(),n.getStateBoatRight(),n.getNodesCheckSum(),2,0);
if(dfs(n4)) {
resultList.add(0,n4);
return true;
}
Node n5 = new Node(n.getLeftPeo(),n.getLeftSavage()-2,n.getRightPeo(),n.getRightSavage()+2,n.getStateBoatRight(),n.getNodesCheckSum(),0,2);
if(dfs(n5)) {
resultList.add(0,n5);
return true;
}
}
else {
Node n6 = new Node(n.getLeftPeo(),n.getLeftSavage()+1,n.getRightPeo(),n.getRightSavage()-1,n.getStateBoatLeft(),n.getNodesCheckSum(),0,1);
if(dfs(n6)) {
resultList.add(0,n6);
return true;
}
Node n7 = new Node(n.getLeftPeo()+1,n.getLeftSavage(),n.getRightPeo()-1,n.getRightSavage(),n.getStateBoatLeft(),n.getNodesCheckSum(),1,0);
if(dfs(n7)) {
resultList.add(0,n7);
return true;
}
Node n1 = new Node(n.getLeftPeo()+1,n.getLeftSavage()+1,n.getRightPeo()-1,n.getRightSavage()-1,n.getStateBoatLeft(),n.getNodesCheckSum(),1,1);
if(dfs(n1)) {
resultList.add(0,n1);
return true;
}
Node n4 = new Node(n.getLeftPeo()+2,n.getLeftSavage(),n.getRightPeo()-2,n.getRightSavage(),n.getStateBoatLeft(),n.getNodesCheckSum(),2,0);
if(dfs(n4)) {
resultList.add(0,n4);
return true;
}
Node n5 = new Node(n.getLeftPeo(),n.getLeftSavage()+2,n.getRightPeo(),n.getRightSavage()-2,n.getStateBoatLeft(),n.getNodesCheckSum(),0,2);
if(dfs(n5)) {
resultList.add(0,n5);
return true;
}
}
return false;
}
public ListNode getResultList() {
return resultList;
}
}
Node.java
import java.util.ArrayList;
import java.util.List;
public class Node {
private ListInteger nodesCheckSum = new ArrayListInteger();
private int leftPeo;
private int rightPeo;
private int leftSavage;
private int rightSavage;
private int CURR_STATE = 0;
private int onBoatPeoNum = 0;
private int onBoatSavageNum = 0;
private final int STATE_BOAT_LEFT = 0;
private final int STATE_BOAT_RIGHT = 1;
public Node(int leftPeo, int leftSavage, int rightPeo, int rightSavage, int state, List checkSumList, int onBoatPeoNum, int onBoatSavageNum) {
this.CURR_STATE = state;
this.leftPeo = leftPeo;
this.leftSavage = leftSavage;
this.rightPeo = rightPeo;
this.rightSavage = rightSavage;
this.nodesCheckSum.addAll(checkSumList);
this.onBoatPeoNum = onBoatPeoNum;
this.onBoatSavageNum = onBoatSavageNum;
}
public int getLeftPeo() {
return leftPeo;
}
public void setLeftPeo(int leftPeo) {
this.leftPeo = leftPeo;
}
public int getRightPeo() {
return rightPeo;
}
public void setRightPeo(int rightPeo) {
this.rightPeo = rightPeo;
}
public int getLeftSavage() {
return leftSavage;
}
public void setLeftSavage(int leftSavage) {
this.leftSavage = leftSavage;
}
public int getRightSavage() {
return rightSavage;
}
public void setRightSavage(int rightSavage) {
this.rightSavage = rightSavage;
}
@Override
public String toString() {
return leftPeo+","+leftSavage+","+rightPeo+","+rightSavage+","+CURR_STATE;
}
public int getCURR_STATE() {
return CURR_STATE;
}
public void setCURR_STATE(int cURR_STATE) {
CURR_STATE = cURR_STATE;
}
public int getStateBoatLeft() {
return STATE_BOAT_LEFT;
}
public int getStateBoatRight() {
return STATE_BOAT_RIGHT;
}
public int calcCheckSum() {
return 1*getCURR_STATE()+10*getLeftPeo()+100*getLeftSavage()+1000*getRightPeo()+10000*getRightSavage();
}
public void addCheckSum() {
int checkSum = calcCheckSum();
nodesCheckSum.add(checkSum);
}
public boolean hasVisited() {
int sum = calcCheckSum();
for (Integer checkSum : nodesCheckSum) {
if(checkSum==sum) return true;
}
return false;
}
public ListInteger getNodesCheckSum() {
return nodesCheckSum;
}
public int getOnBoatPeoNum() {
return onBoatPeoNum;
}
public void setOnBoatPeoNum(int onBoatPeoNum) {
this.onBoatPeoNum = onBoatPeoNum;
}
public int getOnBoatSavageNum() {
return onBoatSavageNum;
}
public void setOnBoatSavageNum(int onBoatSavageNum) {
this.onBoatSavageNum = onBoatSavageNum;
}
}
问题：
有3个传教士和3个野人要过河，只有一艘船，这艘船每次只能载2个人过河，且无论哪边野人的数量大于传教士的数量时，野人就会吃掉传教士。怎样让他们都安全过河？
C语言源代码：
#include stdio.h
#include string.h
#define STEP_MAX 20 //来回过河的次数
#define KIND_NUM 3 //每个种类的数量
#define BOAT_NUM 2 //船的载重量
typedef enum
{
BOAT_THIS,//船在本岸
BOAT_THAT,//船在对岸
} boat_t;
typedef enum
{
ROAD_GO,//过河
ROAD_COME,//回来
} road_t;
typedef struct
{
int ye;//对岸野人数量
int man;//对岸传教士数量
boat_t boat;//船是否在对岸
} state_t;//一种局面
typedef struct
{
int ye;//野人过河数量
int man;//传教士过河的数量
road_t road;//回来或过河
} step_t;//一个步骤
state_t states[STEP_MAX]={0};
step_t steps[STEP_MAX]={0};
//判断所有的野人和传教士是否都到了对岸
bool final(state_t s)
{
const state_t cs=
{
KIND_NUM,
KIND_NUM,
BOAT_THAT
};
if(memcmp(cs,s,sizeof(state_t))==0)
{
return true;
}
return false;
}
//是否会发生野人杀传教士
bool bad(state_t s)
{
if(((KIND_NUM-s.ye)(KIND_NUM-s.man) (KIND_NUM-s.man)0)
||(s.yes.man s.man0))
{
return true;
}
return false;
}
//第n种局面是否跟前面的相重复
bool repeat(state_t s[],int n)
{
int i;
for (i = 0; i n; i++)
{//已经有这种情况了
if (memcmp(states[i], states[n], sizeof(states[i])) == 0)
{
return true;
}
}
return false;
}
void output(step_t steps[STEP_MAX],int n)
{
char *kinds[KIND_NUM]={"野人","传教士"};
char *routine[2]={"过河.","回来."};
int i;
for (i = 0; i n; i++)
{
if((steps[i].ye * steps[i].man)0)
{
printf("%d个%s和%d个%s%s\n",steps[i].ye,kinds[0],
steps[i].man,kinds[1],routine[steps[i].road]);
}
else if(steps[i].ye0)
{
printf("%d个%s%s\n",steps[i].ye,kinds[0],
routine[steps[i].road]);
}
else if(steps[i].man0)
{
printf("%d个%s%s\n",steps[i].man,kinds[1],
routine[steps[i].road]);
}
}
printf("\n");
}
//搜索过河方案(n表示过河次数)
void search(int n)
{
int i,j;
if(nSTEP_MAX)
{//步数限制太少了
printf("Step Overflow!");
return;
}
if(final(states[n]))
{//都到对岸了
output(steps,n);
return;
}
if(bad(states[n]))
{//发生了野人杀传教士了
return;
}
if(repeat(states,n))
{//与前面的局面相重复了
return;
}
if(states[n].boat==BOAT_THIS)
{//船在本岸
for (i = 0; i = BOAT_NUM i=(KIND_NUM-states[n].ye); i++)
for (j = 0; j = BOAT_NUM-i j=(KIND_NUM-states[n].man); j++)
{
if(i==0 j==0)
{
continue;
}
steps[n].ye=i;
steps[n].man=j;
steps[n].road=ROAD_GO;
memcpy(states[n+1], states[n], sizeof(state_t));
states[n+1].ye+=i;
states[n+1].man+=j;
states[n+1].boat=BOAT_THAT;
search(n+1);
}
}
else
{
for (i = 0; i = BOAT_NUM i=states[n].ye; i++)
for (j = 0; j = BOAT_NUM-i j=states[n].man; j++)
{
if(i==0 j==0)
{
continue;
}
steps[n].ye=i;
steps[n].man=j;
steps[n].road=ROAD_COME;
memcpy(states[n+1], states[n], sizeof(state_t));
states[n+1].ye-=i;
states[n+1].man-=j;
states[n+1].boat=BOAT_THIS;
search(n+1);
}
}
}
int main()
{
search(0);
return 0;
}
;
三对三有解。
我用 Python 写了搜寻答案的程序。
要知道其它组合有没有解，只要改一改 “mCOUNT, cCOUNT = 3, 3” 这一行然后运行就知道了。
有空的话我会译成 Java 贴上来。
'''
Solve the Missionaries And Cannibals Puzzle by trying all legal moves.
The puzzle imposes two constraints:
1) Relative headcount: missionaries must be = cannibals at any point.
2) Boat capacity: max is two.
'''
def comb( items, r ):
'''Returns all combinations of elements in items taken r at a time.'''
if r == 0:
yield ( ) # Returns tuple to enable direct conversion to set.
else:
for i in xrange( len( items ) ):
for subComb in comb( items[ i + 1 : ], r - 1 ):
yield ( items[ i ], ) + subComb
# Simply represent the elements of the puzzle by characters.
MISSIONARY, CANNIBAL, BOAT = 'm', 'c', 'B'
mCOUNT, cCOUNT = 3, 3
# Constraint #2: boat capacity.
nMAXCROSSER = 2
nMINCROSSER = 1
class RiverSide:
'''Represents the state of a riverside.'''
def __init__( self, men = [ ], boat = [ ] ):
self.men = men
self.boat = boat
def __eq__( self, other ):
self.men.sort( ); other.men.sort( )
return self.men == other.men and self.boat == other.boat
def __repr__( self ):
return 'BOAT' + `self.boat`.ljust( 8 ) + 'MEN' + `self.men`
def _xferBoat( self, otherSide ):
'''To be called only by xferMen( ).'''
otherSide.boat.append( self.boat.pop( ) )
def xferMen( self, otherSide, menList ):
for man in menList:
otherSide.men.append( self.men.pop( self.men.index( man ) ) )
# Nice to automate boat xfer here.
self._xferBoat( otherSide )
# Constraint #1: relative headcount.
def fatal( self ):
'''Returns true iff the cannibals outnumbers missionaries.'''
mCount = self.men.count( MISSIONARY )
return mCount and mCount self.men.count( CANNIBAL )
class RiverScene:
'''Represents the state of a riverscene.'''
def __init__( self, sourceSide = RiverSide( ), targetSide = RiverSide( ) ):
self.source = sourceSide
self.target = targetSide
def __eq__( self, other ):
return self.source == other.source and self.target == other.target
def __repr__( self ):
return `self.source` + '\n' + `self.target`
def fatal( self ):
return self.source.fatal( ) or self.target.fatal( )
def solve( firstScene, finalScene ):
'''Returns a list of solution steps if solution's found; else returns None.'''
def solutionSteps( takenSteps ):
'''
The solution searching recursive workhorse function.
Takes a list containing the first scene and returns a list of
solution steps leading to the final scene if solution was found.
Optimizations done:
1) elimination of equivalent combinations of men to be moved
2) maximization of headcount to move from source
(minimization for the reverse direction)
'''
lastStep = takenSteps[ - 1 ]
if lastStep == finalScene: return takenSteps
from copy import deepcopy
newStep = deepcopy( lastStep )
# To enable moving of both direction to share the same chunk of code.
start, stop, step = nMAXCROSSER, nMINCROSSER - 1, -1
src, dst = newStep.source, newStep.target
if dst.boat:
start, stop, step = nMINCROSSER, nMAXCROSSER + 1, 1
src, dst = dst, src
for nCrosser in range( start, stop, step ):
for men in set( comb( src.men, nCrosser ) ):
src.xferMen( dst, men )
if not newStep.fatal( ) and newStep not in takenSteps:
takenSteps.append( newStep )
sol = solutionSteps( takenSteps )
if sol:
return sol
else:
takenSteps.pop( )
# Rewind before trying next move.
dst.xferMen( src, men )
takenSteps = [ firstScene ]
return solutionSteps( takenSteps )
# Setup.
men = [ MISSIONARY ] * mCOUNT + [ CANNIBAL ] * cCOUNT
boat = [ BOAT ]
source = RiverSide( men, boat )
target = RiverSide( )
firstScene = RiverScene( source, target )
finalScene = RiverScene( target, source )
print '\nTrying to solve puzzle of', mCOUNT, 'missionaries and', cCOUNT, 'cannibals...\n'
solutionSteps = solve( firstScene, finalScene )
if solutionSteps:
print 'Solution found:\n\n'
for step in solutionSteps:
print step, '\n'
else:
print 'No solution found.'
程序过程是没问题的,只是在函数内声明的局部变量与全局变量同名,造成在函数内全局变量不起作用,
在函数
int
boatf(int
im,int
ic,int
ii)
中,由于形参局部变量与全局变量同名,实际在该函数中起作用的只是局部变量,再加上函数里没有把局部变量运算后的值赋给全局变量,所以函数运行结束后,全局变量的值与函数运行前的值一样.在整个程序运行过程中,main
函数中的im
,ic的值始终都是3,结果就是一种死循环状态.
答案补充
不过我不清楚你设计从
"右岸到左岸用boatr"
的函数作用是什么.
先一传一野过河，然后传再返回载一野过来，然后由野返回载一传过来，再由野载一传来，最后再由野去载最后的一个野人，就OK.啦