首页 > 代码库 > 野人与传教士问题

野人与传教士问题

1.题目简述:有N个传教士和N个野人要过河,现在有一条船只能承载N个人(包括野人),在任何时刻,如果有野人和传教士在一起,必须要求传教士的人数多于或等于野人的人数。
2.解答描述:这题我通过人工只能基于生产式系统解答,其实就是算法中说的深度优先搜索算法。在自己归纳策略集的时候发现当N=1时一次就过去了,当N=2时只有两条规则,当N=3时有5条规则,当N=4时有9条规则,当N=5时有14条规则,所以取N=3时比较便于表达又有代表性(当然河对岸的规则相同)。
3.具体代码:
代码如下,所有思想基本标注:

 

#include "stdafx.h"#include<process.h> #include<stdio.h>#include <stdlib.h>#define NULL 0#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef struct{	int m; //传教士人数	int c; //野人人数	int b; //船的位置变量}QElemType; /* 定义队列的数据元素类型QElemType为结构体类型 */typedef struct _Rule{	int m;//传教士人数	int c;//野人人数}Rule;Rule rule[5] = {{1,1}, {1,0}, {0,1}, {2,0}, {0,2}};  // 规则集etypedef struct QNode{	QElemType data;	struct QNode *next;}QNode,*QueuePtr;//节点结构体typedef struct{	QueuePtr front,rear; //队头、队尾指针 }LinkQueue;/* 构造一个空队列Q */void InitQueue(LinkQueue *Q){ 	(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));	if(!(*Q).front)		exit(0);	(*Q).front->next=NULL;}/* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */int DeQueue(LinkQueue *Q,QElemType *e){ 	QueuePtr p;	if((*Q).front==(*Q).rear)		return ERROR;	p=(*Q).front->next;	*e=p->data;	(*Q).front->next=p->next;	if((*Q).rear==p)		(*Q).rear=(*Q).front;	free(p);	return OK;} /* 插入元素e为Q的新的队尾元素 */void EnQueue(LinkQueue *Q,QElemType e){	QueuePtr p=(QueuePtr)malloc(sizeof(QNode));	if(!p) 		exit(0);	p->data=http://www.mamicode.com/e;>


实验结果: