首页 > 代码库 > 野人与传教士问题
野人与传教士问题
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;>
实验结果:
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。