八皇后问题
1.问题描述
设在初始状态下在国际象棋的棋盘上没有任何棋子（这里的棋子指皇后棋子）。然后顺序在第1行，第2行……第8行上布放棋子。在每一行中共有8个可选择的位置，但在任一时刻棋盘的合法布局都必须满足3个限制条件（1）任意两个棋子不得放在同一行（2）任意两个棋子不得放在同一列上（3）任意棋子不得放在同一正斜线和反斜线上。
2.基本要求
编写求解并输出此问题的一个合法布局的程序。
3、实现提示：
在第i行布放棋子时，从第1列到第8列逐列考察。当在第i行第j列布放棋子时，需要考察布放棋子后在行方向、列方向、正斜线和反斜线方向上的布局状态是否合法，若该棋子布放合法，再递归求解在第i+1行布放棋子；若该棋子布放不合法，移去这个棋子，恢复布放该棋子前的状态，然后再试探在第i行第j+1列布放棋子。
4 程序代码
#include
#include
static char Queen[8][8];
static int a[8];
static int b[15];
static int c[15];
static int QueenNum=0;//记录总的棋盘状态数
void qu(int i);//参数i代表行
{
int Line,Column;
//棋盘初始化，空格为*，放置皇后的地方为@
for(Line=0;Line<8;Line++)
{
a[Line]=0; //列标记初始化，表示无列冲突
for(Column=0;Column<8;Column++)
Queen[Line][Column]='*';
}
//主、从对角线标记初始化，表示没有冲突
for(Line=0;Line<15;Line++)
b[Line]=c[Line]=0;
qu(0);
return 0;
}
void qu(int i)
{
int Column;
for(Column=0;Column<8;Column++)
{
if(a[Column]==0&&b[i-Column+7]==0&&c[i+Column]==0) //如果无冲突
{
Queen[i][Column]='Q'; //放皇后
a[Column]=1;//标记，下一次该列上不能放皇后
b[i-Column+7]=1;//标记，下一次该主对角线上不能放皇后
c[i+Column]=1;//标记，下一次该从对角线上不能放皇后
if(i<7) qu(i+1); //如果行还没有遍历完，进入下一行
else//否则输出
//输出棋盘状态
int Line,Column;
cout<<"第"<<++QueenNum<<"种状态为："< for(Line=0;Line<8;Line++) { for(Column=0;Column<8;Column++) cout< cout< } cout< getchar(); } /*如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置*/ Queen[i][Column]='*'; a[Column]=0; b[i-Column+7]=0; c[i+Column]=0; } } } 5 程序结果 题目2 背包问题的求解 1.问题描述 假设有一个能装入总体积为T的背包和n件体积分别为w1,w2,…w n的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+…+w m=T，要求找出所有满足上述条件的解。 例如：当T=10，各件物品的体积{1,8,4,3,5,2}时，可找到下列4组解： (1,4,3,2) (1,4,5) (8,2) (3,5,2)。 2.实现提示 可利用回溯法的设计思想来解决背包问题。首先，将物品排成一列，然后，顺序选取物品装入背包，若已选取第i件物品后未满，则继续选取第i+1件，若该件物品“太大”不能装入，则弃之，继续选取下一件，直至背包装满为止。 如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入的物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直到求得满足条件的解，或者无解。 由于回溯求解的规则是“后进先出”，自然要用到“栈”。 进一步考虑：如果每件物品都有体积和价值，背包又有大小限制，求解背包中存放物品总价值最大的问题解---最优解或近似最优解。 3．题目源代码 #define maxsize 1024 #define null 0 #include"stdio.h" #include"conio.h" #include"stdio.h" typedef struct{ int last; int data[maxsize]; }seqlist; //定义顺序表结构体 typedef struct{ int top; int sum; int data[maxsize]; }seqstack; //定义栈结构体 seqstack *init_seqstack(){ seqstack *s; s=new seqstack; if(!s) { printf("空间不足"); return null; } else s->top=-1; s->sum=0; return s; } } //栈初试化 int empty_seqstack(seqstack *s) { if (s->top==-1) return 1; else return 0; } //判断空栈 int push_seqstack(seqlist *l,int i,seqstack *s) //入栈{ if(s->top==maxsize-1) return 0; else { s->top++; s->data[s->top]=i; //顺序表中第i 个元素，i 入栈 s->sum=s->sum+l->data[i]; //栈中sum加和！ return 1; } } int pop_seqstack(seqlist *l,seqstack *s,int *x) //出栈{ if(empty_seqstack(s)) return 0; else { *x=s->data[s->top]; s->sum=s->sum-l->data[s->data[s->top]]; s->top--; return 1; } } seqlist *init_seqlist() { seqlist *l; int x=1; l=new seqlist; l->last=0; printf("-------------------------------------------\n请依次输入个物品的大小，输入0结束。\n-------------------------------------------\n"); scanf("%d",&x); while(x!=0) { l->data[l->last]=x; l->last++; scanf("%d",&x); } return l; } /*创建数组，储存物品体积*/ void knapsk(int n,seqlist *l) { seqstack *s; int flag=1; int i=0; int t; s=init_seqstack(); //初始化栈命名为S while(flag!=0) { while(i<=l->last) { push_seqstack(l,i,s); if(s->sum==n) { printf("-------------------------------------------\n可行的解是:"); for(t=0;t<=s->top;t++) printf("%d ",l->data[s->data[t]]); printf("\n"); pop_seqstack(l,s,&i); i++; } else { if(s->sum>n) { pop_seqstack(l,s,&i); i++; } else } } while(i==l->last+1) { flag=pop_seqstack(l,s,&i); i++; if(flag==0) printf("-------------------------------------------\n执行完毕"); } } } int main() { int n; seqlist *l; printf("请输入背包体积n的大小，n=?"); scanf("%d",&n); l=init_seqlist(); knapsk(n,l); return 1; } 题目3 农夫过河问题的求解 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西 全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫 才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会 吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而 狼不吃白菜。请求出农夫将所有的东西运过河的方案。 2.实现提示 求解这个问题的简单方法是一步一步进行试探，每一步搜索所有可能的选择 ，对前一步合适的选择后再考虑下一步的各种方案。要模拟农夫过河问题，首先 需要对问题中的每个角色的位置进行描述。可用4位二进制数顺序分别表示农夫、 狼、白菜和羊的位置。用0表在南岸，1表示在北岸。例如，整数5 (0101)表示农 夫和白菜在南岸，而狼和羊在北岸。 现在问题变成：从初始的状态二进制0000(全部在河的南岸)出发，寻找一种 全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸)为最终目 标。总状态共16种(0000到1111)，(或者看成16个顶点的有向图)可采用广度优先或深度优先的搜索策略---得到从0000到1111的安全路径。 以广度优先为例：整数队列---逐层存放下一步可能的安全状态；Visited[16]数组标记该状态是否已访问过，若访问过，则记录前驱状态值---安全路径。 最终的过河方案应用汉字显示出每一步的两岸状态。 3 程序代码 #include #include #include #define MAX 20 int a[MAX][4]; // 0 ：狼，1：羊，2：菜，3：农夫，value：0：本岸，1:对岸 int b[MAX]; //b[]+1记录每一步农夫的什么 char *name[] = { "空手", "带狼", "带羊", "带菜" }; void search(int iStep) { int i; if (a[iStep][0] + a[iStep][1] + a[iStep][2] + a[iStep][3] == 4) { for (i = 0; i < iStep; i++) { if (a[i][3] == 0) { printf("农夫%s到对岸\n", name[b[i] + 1]); } else { printf("农夫%s回本岸\n", name[b[i] + 1]); } } printf("\n"); printf("\n"); return; } for (i = 0; i < iStep; i++) { if (memcmp(a[i], a[iStep], sizeof(a[i])) == 0) //已经找过 { return; } } if (a[iStep][1] != a[iStep][3] && (a[iStep][2] == a[iStep][1] || a[iStep][0] == a[iStep] [1])) //危险 { return; } for (i = -1; i <= 2; i++) { b[iStep] = i; memcpy(a[iStep + 1], a[iStep], sizeof(a[iStep + 1])); a[iStep + 1][3] = 1 - a[iStep + 1][3]; //农夫过河 if (i == -1) //空手回 { search(iStep + 1); } else if (a[iStep][i] == a[iStep][3]) //不空手回 { a[iStep + 1][i] = a[iStep + 1][3]; search(iStep + 1); } } } int main() { search(0); return 0; } 4 程序结果 题目4 教学计划编制问题 1.问题描述 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业 开设的课程都是固定的，而且课程在开设时间的安排必须满足先修关系。 每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门 课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。 2.基本要求 (1)输入参数包括：学期总数，一学期的学分上限，每门课的课程号 (固定占3位的字母数字串)、学分和直接先修课的课程号。 (2)允许用户指定下列两种编排策略之一：一是使学生在各学期中的 学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。 (3)若根据给定的条件问题无解，则报告适当的信息；否则，将教学 计划输出到用户指定的文件中。计划的表格格式自行设计。 3、实现提示： 可设学期总数不超过12，课程总数小于100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。 3.测试数据 学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01 到C12，学分顺序为2，3，4，3，2，3，4，4，7，5，2，3。先修关系见 下图。 4，程序代码 #include #include #include #include #include #include #include #include #include #include // 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE #define MAX_NAME 10 /* 顶点字符串的最大长度*/ #define MAXCLASS 100 int Z=0; int X=0; int xqzs,q=1,xfsx; typedef int InfoType; typedef char VertexType[MAX_NAME]; // 字符串类型 /* 图的邻接表存储表示p163 */ #define MAX_VERTEX_NUM 100 typedef enum{DG,DN,UDG,UDN}GraphKind; /* {有向图,有向网,无向图,无向网} */ typedef struct ArcNode { int adjvex; /* 该弧所指向的顶点的位置*/ struct ArcNode *nextarc; /* 指向下一条弧的指针*/ InfoType *info; /* 该弧相关信息的指针（网的权值指针*/ }ArcNode; /* 表结点*/ typedef struct { VertexType data; /* 顶点信息*/ ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针*/ }VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点*/ typedef struct { AdjList vertices,verticestwo; int vexnum,arcnum; /* 图的当前顶点数和弧数*/ int kind; /* 图的种类标志*/ }ALGraph; /* 图的邻接表存储的基本操作*/ int LocateVex(ALGraph G,VertexType u) { /* 初始条件: 图G存在,u和G中顶点有相同特征*/ /* 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */ int i; for(i=0;i if(strcmp(u,G.vertices[i].data)==0) return i; return -1; } Status CreateGraph(ALGraph *G) { /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图) * / int i,j,k; VertexType va,vb; ArcNode *p; printf("请输入教学计划的课程数: "); scanf("%d",&(*G).vexnum); printf("请输入课程先修关系的边数: "); scanf("%d",&(*G).arcnum); printf("请输入%d个课程号(%d个字符):\n",(*G).vexnum,MAX_NAME); for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量（头结点）*/ { scanf("%s",(*G).vertices[i].data); (*G).vertices[i].firstarc=NULL; } printf("请输入%d个课程的学分值(%d个字符):\n",(*G).vexnum,MAX_NAM E); for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量*/ { scanf("%s",(*G).verticestwo[i].data); } printf("请顺序输入每条弧的弧尾和弧头(以空格作为间隔):\n"); for(k=0;k<(*G).arcnum;++k) /* 构造表结点链表*/ { scanf("%s%s",va,vb); i=LocateVex(*G,va); j=LocateVex(*G,vb); p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->info=NULL; p->nextarc=(*G).vertices[i].firstarc; /* 插在表头*/ (*G).vertices[i].firstarc=p; } return OK; } void Display(ALGraph G) { /* 输出图的邻接矩阵G ,即输出相关的信息（把输入进去的整理后都输出来）*/ int i; ArcNode *p; switch(G.kind) { case DG: printf("有向图\n"); } printf("%d个顶点：\n",G.vexnum); for(i=0;i printf("%s ",G.vertices[i].data); printf("\n%d条弧(边):\n",G.arcnum); for(i=0;i { p=G.vertices[i].firstarc; while(p) { printf("%s→%s ",G.vertices[i].data,G.vertices[p->adjvex].data); p=p->nextarc; } printf("\n"); } } void iiiiiiFindInDegree(ALGraph G,int indegree[]) { /* 求顶点的入度，算法调用*/ int i; ArcNode *p; for(i=0;i indegree[i]=0; /* 赋初值*/ for(i=0;i { p=G.vertices[i].firstarc; while(p) { indegree[p->adjvex]++; p=p->nextarc; } } } void FindInDegree(ALGraph G,int indegree[]) { /* 求顶点的入度，算法调用*/ int i,j; ArcNode *p; for(i=0;i indegree[i]=0; /* 赋初值*/ for(i=0;i { for(j=0;j { p=G.vertices[j].firstarc; while(p) { if(p->adjvex==i) indegree[p->adjvex]++; p=p->nextarc; } } } } typedef int SElemType; /* 栈类型*/ /*栈的顺序存储表示*/ #define STACK_INIT_SIZE 10 /* 存储空间初始分配量*/ #define STACKINCREMENT 2 /* 存储空间分配增量*/ typedef struct SqStack { SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */ SElemType *top; /* 栈顶指针*/ int stacksize; /* 当前已分配的存储空间，以元素为单位*/ }SqStack; /* 顺序栈*/ /* 顺序栈的基本操作p47 */ Status InitStack(SqStack *S) { /* 构造一个空栈S */ (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!(*S).base) exit(OVERFLOW); /* 存储分配失败*/ (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; return OK; } Status StackEmpty(SqStack S) { /* 若栈S为空栈，则返回TRUE，否则返回FALSE */ if(S.top==S.base) return TRUE; else return FALSE; } Status Pop(SqStack *S,SElemType *e) { /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ if((*S).top==(*S).base) return ERROR; *e=*--(*S).top; return OK; } Status Push(SqStack *S,SElemType e) { /* 插入元素e为新的栈顶元素*/ if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间*/ { (*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREME NT)*sizeof(SElemType)); if(!(*S).base) exit(OVERFLOW); /* 存储分配失败*/ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; } *((*S).top)++=e; return OK; } typedef int pathone[MAXCLASS]; typedef int pathtwo[MAXCLASS]; //拓扑排序的算法p182 Status TopologicalSort(ALGraph G) { /* 有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK, */ /* 否则返回ERROR。*/ int i,k,j=0,count,indegree[MAX_VERTEX_NUM]; SqStack S; pathone a; pathtwo b; ArcNode *p; FindInDegree(G,indegree); /* 对各顶点求入度indegree[0..vernum-1] */ InitStack(&S); /* 初始化栈*/ for(i=0;i if(!indegree[i]) Push(&S,i); /* 入度为0者进栈*/ count=0; /* 对输出顶点计数*/ while(!StackEmpty(S)) { /* 栈不空*/ Pop(&S,&i); a[i]=*G.vertices[i].data; b[i]=*G.verticestwo[i].data; printf("课程%s→学分%s ",G.vertices[i].data,G.verticestwo[i].data); /* 输出i号顶点并计数*/ ++count; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { /* 对i号顶点的每个邻接点的入度减1 */ k=p->adjvex; if(!(--indegree[k])) /* 若入度减为0,则入栈*/ Push(&S,k); } } printf("\n"); if(count {printf("Error!此有向图有回路!\n"); return ERROR; } else { printf("Right!为一个拓扑序列。\n"); } while(q<=xqzs) { int C=0; if(X<=G.arcnum) { while(C<=xfsx) { C+=*G.verticestwo[Z].data; ++Z; } printf("第%d个学期应学课程:",q); while(X<=Z) { printf("%s ",G.vertices[X].data); ++X; } cout< q++; } else { cout<<"课程编制已经完成！"< return OK; } } return OK; } void main() { ALGraph f; printf("教学计划编制问题的求解过程:\n"); printf("请输入学期总数:"); scanf("%d",&xqzs); printf("请输入学期的学分上限:"); scanf("%d",&xfsx); CreateGraph(&f); //构造图 Display(f); TopologicalSort(f); } 试验总结 通过本次实验,使我认识了更多的关于数据结构的知识,也使我学到了更多的知识,而且在做的过程中遇到了一些问题,通过与同学的讨论得到了顺利的解决,加深了同学之间的友谊! 实验1: Prolog语言程序设计 人工智能（AI）语言是一类适应于人工智能和知识工程领域的、具有符号处理和逻辑推理能力的计算机程序设计语言。能够用它来编写求解非数值计算、知识处理、推理、规划、决策等具有智能的各种复杂问题。 Prolog是当代最有影响的人工智能语言之一，由于该语言很适合表达人的思维和推理规则，在自然语言理解、机器定理证明、专家系统等方面得到了广泛的应用，已经成为人工智能应用领域的强有力的开发语言。 尽管Prolog语言有许多版本，但它们的核心部分都是一样的。Prolog的基本语句仅有三种，即事实、规则和目标三种类型的语句，且都用谓词表示，因而程序逻辑性强，方法简捷，清晰易懂。另一方面，Prolog是陈述性语言，一旦给它提交必要的事实和规则之后，Prolog就使用内部的演绎推理机制自动求解程序给定的目标，而不需要在程序中列出详细的求解步骤。 一、实验目的 1、加深学生对逻辑程序运行机理的理解。 2、掌握Prolog语言的特点、熟悉其编程环境。 3、为今后人工智能程序设计做好准备。 二、实验内容 1、编写一个描述亲属关系的Prolog程序，然后再给予出一些事实数据，建立一个小型演绎数据库。 提示：可以以父亲和母亲为基本关系（作为基本谓词），再由此来描述祖父、祖母、兄弟、姐妹以及其他所属关系。 2、编写一个路径查询程序，使其能输出图中所有路径。 提示：程序中的事实描述了下面的有向图，规则是图中两节点间通路的定义。 e 3、一个雇主在发出招聘广告之后，收到了大量的应聘申请。为了从中筛选出不量的候选人，该雇主采用下列判据：申请者必须会打字、开车，并且住在伦敦。 （a）用Prolog规则表述这个雇主的选择准则。 （b）用Prolog事实描述下列申请者的情况： 史密斯住在剑桥，会开车但不会打字。 布朗住在伦敦，会开车也会打字。 简住在格拉斯哥，不会开车但会打字。 埃文斯住在伦敦，会开车也会打字。 格林住在卢顿，会开车也会打字。 （c）要求Prolog提供一个候选人名单。 4、实现递归谓词remove(X,Y,Z),它用于从表Y中除去所有整型数X的倍数值后得到新表Z。例如，对于询问 remove(2,[3,4,5,6,7,8,9,10],Z). 的回答为： Z=[3,5,7,9] 三、实验建议 1、首先运行Prolog安装目录中PROGRAM目录下的示例程序，对Prolog功能有一个感性认识。 （1）HANOI．PRO 实现汉诺塔演示的程序。 程序运行界面如图所示。 数学模型实验—实验报告6 学院：工商学院专业：电气二类（计算机）姓名：辛文辉尚磊张亨 学号：___ 2012484019 2012484091 2012484055 ____ 实验时间：__ 3.18 ____ 实验地点：b3 一、实验项目： Matlab程序设计 安全渡河问题可以看成一个多步决策过程。每一步，即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人员(商人随从各几人)作出决策，在保证安全的前提下(两岸的商人数都不比随从数少)，在有限步内使人员全部过河。用状态(变量)表示某一岸的人员状况，决策(变量)表示船上的人员状况，可以找出状态随决策变化的规律。问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步的决策，达到渡河的目的。 此类智力问题经过思考，可以拼凑出一个可行方案。但是，我们现在希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。 二、实验目的和要求 a.了解Matlab程序设计有关基本操作 b.掌握有关程序结构 三、实验内容 允许的状态向量 0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 0 11 1 11 2 11 3 11 4 11 5 11 6 11 7 11 8 11 9 11 10 允许的决策向量: 0 1 0 2 0 3 0 4 0 5 0 6 1 0 1 1 2 0 2 1 2 2 3 0 3 1 3 2 3 3 4 0 4 1 4 2 5 0 5 1 6 0 过河步骤： 第1步：0商5仆过河，0商1仆返回 第2步：5商1仆过河，1商1仆返回 第3步：3商3仆过河，1商1仆返回 第4步：3商3仆过河，1商1仆返回 第5步：3商3仆过河，完成 过河过程中状态变化： 步骤此岸商此岸仆方向彼岸商彼岸仆 1 11 6 ==> -8 -3 郑州轻工业学院 课程设计任务书 题目农夫过河 专业、班级计算机科学与技术 学号姓名 主要内容： 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不能吃白菜。要求给出农夫将所有的东西运过河的方案。基本要求: 编写求解该问题的算法程序，并用此程序上机运行、调试，屏幕显示结果，能结合程序进行分析。 主要参考资料: 数据结构严蔚敏 完成期限：2012/6/21 指导教师签名： 课程负责人签名： 年月日 郑州轻工业学院 本科 数据结构课程设计总结报告 设计题目：农夫过河 学生姓名： 系别：计算机与通信工程学院 专业：计算机科学与技术 班级：计算机科学与技术 学号： 指导教师： 2012年6 月21 日 一，设计题目 问题描述： 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不能吃白菜。要求给出农夫将所有的东西运过河的方案。 二，运行环境（软、硬件环境） VC6.0 Windows7系统 三，算法设计的思想 对于这个问题，我们需要先自动生成图的邻接矩阵来存储，主要方法是先生成各种安全状态结点，存放在顶点向量中；再根据判断两个结点间状态是否可以转换来形成顶点之间的所有边，并把它们保存在邻接矩阵中。在建立了图的邻接矩阵存储结构后，利用递归深度优先搜索求出从顶点（0，0，0，0）到顶点（1，1，1，1）的一条简单路径，这样做只能搜到一种合理方法，因为深度优先搜索遍历一个图的时候每一个结点只能被访问一次。 四，算法的流程图 要写算法的流程图，必须要先很了解自己的函数结构，我先在纸上手动的把整个过程在纸上画一遍，了解它的大体流程，然后把各个函数给分开，下面是我自己根据我的代码中画的各个函数画的流程图，希望老师满意。 主函数的流程图： 计算机科学与技术1341901301 陈敏 实验一：知识表示方法 一、实验目的 状态空间表示法是人工智能领域最基本的知识表示方法之一，也是进一步学习状态空间搜索策略的基础，本实验通过牧师与野人渡河的问题，强化学生对知识表示的了解和应用，为人工智能后续环节的课程奠定基础。 二、问题描述 有n个牧师和n个野人准备渡河，但只有一条能容纳c个人的小船，为了防止野人侵犯牧师，要求无论在何处，牧师的人数不得少于野人的人数(除非牧师人数为0)，且假定野人与牧师都会划船，试设计一个算法，确定他们能否渡过河去，若能，则给出小船来回次数最少的最佳方案。 三、基本要求 输入：牧师人数(即野人人数)：n；小船一次最多载人量：c。 输出：若问题无解，则显示Failed，否则，显示Successed输出一组最佳方案。用三元 组(X 1, X 2 , X 3 )表示渡河过程中的状态。并用箭头连接相邻状态以表示迁移过程：初始状态-> 中间状态->目标状态。 例：当输入n=2，c=2时，输出：221->110->211->010->021->000 其中：X 1表示起始岸上的牧师人数；X 2 表示起始岸上的野人人数；X 3 表示小船现在位置(1表 示起始岸，0表示目的岸)。 要求：写出算法的设计思想和源程序，并以图形用户界面实现人机交互，进行输入和输出结果，如： Please input n: 2 Please input c: 2 Successed or Failed?: Successed Optimal Procedure: 221->110->211->010->021->000 四、算法描述 深圳大学实验报告 课程名称：算法分析与复杂性理论 实验项目名称：八皇后问题 学院：计算机与软件学院 专业：软件工程 指导教师：杨烜 报告人：学号：班级：15级软工学术型实验时间：2015-12-08 实验报告提交时间：2015-12-09 教务部制 一．实验目的 1.掌握选回溯法设计思想。 2.掌握八皇后问题的回溯法解法。 二．实验步骤与结果 实验总体思路： 根据实验要求，通过switch选择八皇后求解模块以及测试数据模块操作，其中八皇后模块调用摆放皇后函数模块，摆放皇后模块中调用判断模块。测试数据模块主要调用判断模块进行判断，完成测试。用一维数组保存每行摆放皇后的位置，根据回溯法的思想递归讨论该行的列位置上能否放置皇后，由判断函数Judge()判断，若不能放置则检查该行下一个位置。相应结果和过程如下所示（代码和结果如下图所示）。 回溯法的实现及实验结果： 1、判断函数 代码1： procedure BTrack_Queen(n) //如果一个皇后能放在第K行和X(k)列，则返回true，否则返回false。 global X(1:k);integer i,k i←1 while i 人工智能上机实验报告 学号：姓名：所在系：信息学院班级： 实验名称：实验日期2016年12月3日 实验指导教师实验机房A401 ------------------------------------------------------------------------------------------------------ 1.实验目的： (1)在掌握状态空间搜索策略的基础上，理解知识表示的方法。 (2)能够应用知识表示方法，解决实际问题 2. 实验内容： (1)M-C问题描述 有n个牧师和n个野人准备渡河，但只有一条能容纳c个人的小船，为了防止野人侵犯牧师，要求无论在何处，牧师的人数不得少于野人的人数(除非牧师人数为0)，且假定野人与牧师都会划船，试设计一个算法，确定他们能否渡过河去，若能，则给出小船来回次数最少的最佳方案。 3．算法设计（编程思路或流程图或源代码） #include 农夫过河问题状态图及程序 一、问题需求分析 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。问题是他面前只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。另外，因为狼能吃羊，而羊爱吃白菜，所以农夫不能留下羊和白菜或者狼和羊单独在河的一边，自己离开。请问农夫该采取什么方案才能将所有的东西运过河呢？ 二、算法选择 求解这个问题的最简单的方法是一步一步进行试探，每一步都搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。 用计算机实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first) 搜索，另一种是深度优先(depth_first) 。 广度优先： u 广度优先的含义就是在搜索过程中总是首先搜索下面一步的所有可能状态，然后再进一步考虑更后面的各种情况。u 要实现广度优先搜索，一般都采用队列作为辅助结构。把下一步所有可能达到的状态都列举出来，放在这个队列中， 然后顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里……。 u 由于队列的操作遵循先进先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各情况的处理。 三、算法的精化 要模拟农夫过河问题，首先需要选择一个对问题中每个角色的位置进行描述的方法。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。例如用0表示农夫或者某东西在河的南岸，1表示在河的北岸。因此整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。 四、算法的实现 完成了上面的准备工作，现在的问题变成： 从初始状态二进制0000(全部在河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸) 为最终目标，并且在序列中的每一个状态都可以从前一状态通过农夫（可以带一样东西）划船过河的动作到达。 逻辑学教授的3个得意门生ABC，前一晚在酒吧喝多了，结果第二天3人集体迟到。教授说：“作为对你们迟到的惩罚，你们3人必须比其他同学多做一道作业，完成了这道作业才可以离开教室。”这道附加的作业是一道帽子题，教授给每人戴了顶帽子，帽子不是红色就是白色，不是白色就是红色。每人都能看见其他2人帽子的颜色，却不能看见自己帽子的颜色。每人都看到其他2人帽子的颜色后，每思考5分钟为一轮，谁猜出自己帽子的颜色了就可以说出来并离开。教授还说：“你们3人中至少有1人戴了红色帽子。” 第一轮下来，A说：“我没猜出来。”B说“我也没猜出来”C说：“我也猜不出。” 第二轮下来，还是没人能猜出自己帽子的颜色。 第三轮，3人都猜出了自己帽子的颜色。 问：ABC三人头顶都是什么颜色的帽子？然后用谓词逻辑写出推理过程。 最一般合一及归结反演相关 已知w={P(f(x,g(A,y)),z), P(f(x,z),z)，求MGU 令δ0=ε，w0=w，因w中含有两个表达式，因此δ0不是最一般合一 差异集D0={g(A,y)/z} δ1=δ0oD0={g(A,y)/z} w1={P(f(x,g(A,y)),g(A,y)), P(f(x,g(A,y)),g(A,y)) w1中仅含有一个表达式，所以δ1就是最一般合一。 证明G是否是F1、F2的逻辑结论。 F1:(?x)(P(x)→(Q(x)∧R(x))) F2:(?x)(P(x)∧S(x)) G: (?x)(S(x)∧R(x)) F1: ?P(x)∨(Q(x)∧R(x)) ? (?P(x)∨Q(x)) ∧ (?P(x)∨R(x)) F2: P(x)∧S(x) ?G: ?(?x)(S(x)∧R(x)) ? (?x)(?(S(x)∧R(x))) ? ?S(x)∨?R(x) 子句集： 1 ?P(x)∨Q(x) 2 ?P(x)∨R(x) 3 P(x) 4 S(x) 5 ?S(x)∨?R(x) 其中2与3规约，4与5归结，其结果再归结得到空子句，证明G是F1与F2的结论。 农夫过河问题 (1)农夫每次只能带一样东西过河 (2)如果没有农夫看管，狼吃羊，羊吃菜 要求： 设计一个过河方案，使得农夫、狼、羊、菜都能过河，画出相应的状态空间图。 四元组S表示状态，即S＝(农夫，狼，羊，菜) 用0表示在左岸，1表示在右岸 初始S=(0，0，0，0) 目标G=(1，1，1，1) 数据结构实验报告 ——实验四农夫过河的求解本实验的目的是进一步理解顺序表和队列的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 一、【问题描述】 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请求出农夫将所有的东西运过河的方案。 二、【数据结构设计】 求解这个问题的简单的方法是一步一步进行试探，每一步搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。 要模拟农夫过河问题，首先需要对问题中每个角色的位置进行描述。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。用0表示农夫或者某东西在河的南岸，1表示在河的北岸。例如整数5(其二进制表示为0101)表示农夫和白菜在河的南岸，而狼和羊在北岸。 现在问题变成：从初始状态二进制0000(全部在河的南岸)出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸)为最终目标，并且在序列中的每一个状态都可以从前一状态到达。为避免瞎费功夫，要求在序列中不出现重复的状态。 实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first)搜索， 另一种是深度优先(depth_first)搜索。本书只介绍在广度优先搜索方法中采用的数据结构设计。 广度优先就是在搜索过程中总是首先搜索下面一步的所有可能状态，再进一步考虑更后面的各种情况。要实现广度优先搜索，可以使用队列。把下一步 《数学模型实验》实验报告 姓名：王佳蕾学院：数学与信息科 学学院 地点：主楼402 学号：055专业：数学类时间：2017年4 月16日 实验名称： 商人和仆人安全渡河问题的matlab实现 实验目的： 1.熟悉matlab基础知识，初步了解matlab程序设计； 2.研究多步决策过程的程序设计方法； 3.（允许）状态集合、（允许）决策集合以及状态转移公式的matlab表示；实验任务： 只有一艘船，三个商人三个仆人过河，每一次船仅且能坐1-2个人，而且任何一边河岸上仆人比商人多的时候，仆人会杀人越货。怎么在保证商人安全的情况下，六个人都到河对岸去，建模并matlab实现。 要求：代码运行流畅，结果正确，为关键语句加详细注释。 实验步骤： 1.模型构成 2.求决策 3.设计程序 4.得出结论（最佳解决方案） 实验内容： （一）构造模型并求决策 设第k次渡河前此岸的商人数为xk，随从数为yk，k=1,2,...，xk，yk=0,1,2,3.将二维向量sk=（xk，yk）定义为状态，安全渡河条件下的状态集合称为允许状态集合，记作S，S 对此岸和彼岸都是安全的。 S={(x,y)|x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2} 设第k次渡船上的商人数为uk，随从数vk，将二维变量dk=（uk，vk）定义为决策，允许决策集合记为D,由小船的容量可知， D={(u,v)|1<=u+v<=2,u,v=0,1,2} k为奇数时，船从此岸驶向彼岸，k为偶数时，船从彼岸驶向此岸，状态sk随决策变量dk的变化规律为sk+1=sk+(-1)^k*dk（状态转移律） 这样制定安全渡河方案归结为如下的多步决策模型： 求决策dk∈D(k=1,2,...,n)，使状态sk∈S，按照转移律，由初始状态s1=（3,3）经有限步n到达状态sn+1=（0,0）。 （二）程序设计 数据结构实验报告 实验名称：实验二——利用栈结构实现八皇后问题 学生姓名： 班级： 班内序号： 学号： 日期：2013年11月21日 1．实验要求 （1）实验目的 通过选择下面五个题目之一进行实现，掌握如下内容： 进一步掌握指针、模板类、异常处理的使用 掌握栈的操作的实现方法 掌握队列的操作的实现方法 学习使用栈解决实际问题的能力 学习使用队列解决实际问题的能力 （2）实验内容 利用栈结构实现八皇后问题。 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。 ①可以使用递归或非递归两种方法实现 ②实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线。 （3）代码要求 ①必须要有异常处理，比如删除空链表时需要抛出异常； ②保持良好的编程的风格： 代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能 ③递归程序注意调用的过程，防止栈溢出 2. 程序分析 2.1 存储结构 栈（递归）： 2.2 关键算法分析 (1)递归 void SeqStack “数据结构与算法综合实验”课程设计报告题目：农夫过河问题 学院计算机科学技术 年级2014级 专业计算机科学与技术 学号20142060 姓名高晗 日期2016年3月30日星期三 成绩 评语 黑龙江大学 计算机科学技术学院、软件学院 《数据结构与算法综合实验》报告 1.系统概述 （1）一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，他要把这些东西全部运到北岸。他面前只有一只小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，但是狼不吃白菜。要求给出农夫将所有东西运过河的方案。 （2）为农夫过河问题抽象数据模型，体会数据模型在求解问题中的重要作用。 （3）掌握顺序表和队列的逻辑结构和存储结构。 2.系统需求分析 (1)针对实现整个过程需要多步，不同步骤中各个事物所处位置不同的情况，可定义一个结构体来实现对四个对象狼、羊、白菜和农夫的表示。对于起始岸和目的岸，可以用0或者1来表示，以实现在程序设计中的简便性。 (2)题目要求给出四种事物的过河步骤，没有对先后顺序进行约束，这就需要给各个事物依次进行编号，然后依次试探，若试探成功，进行下一步试探。这就需要使用循环或者递归算法，避免随机盲目运算且保证每种情况均试探到，不接受非法输入。 (3)题目要求求出农夫带一只羊，一条狼和一颗白菜过河的办法，所以依次成功返回运算结果后，需要继续运算，直至求出结果，即给出农夫的过河方案。输出界面要求具有每一步中农夫所带对象及每步之后各岸的物体，需要定义不同的数组来分别存储上述内容，并使界面所示方案清晰简洁。 (4)实验运行环境为VC++6.0. 3.系统概要设计 (1)数据结构设计 要模拟农夫过河的问题，用四位二进制数顺序分别表示农夫，狼，羊，白菜的位置。用0表示农夫或某种东西在河的南岸，1表示在河的北岸。则问题的初 课程设计第五题 1．题目探讨农夫过河的问题 2.设计思路 （1）农夫由A到B的情况 （1）带走一个动物后，另外的两个物是不是可以相吃 （2）会不会把刚带回来的又带到对岸去 （3）最后一次带的情况比较的特殊，判断最后一次走后是不是所有的都不在了对岸 （2）农夫从B到A的情况 （1）对岸是不是只有一个物体 （2）对岸是不是有两个物体，若是有两个物体的话他们的处理方式不一样，1。两个物体会相克的，则把羊带走，2如果不是的话那么农夫就空着手回去。 3．应该注意的问题 （1）。在最后的一次带走羊的时候，应该加如一个新的判段 （2）。以及在带回羊的时候，我们要对其进行一个标记，不然的话我们就很容易进行死循环里面 （3）以及每一次从A带东西去B的时候，我们都要对他的位置进行标记下 4．咸受 在对一个问题分析的时候，我们应该先把每一种情况给分析出来，要把问题分析得分面一些，最好是不要落下任何的一种情况，这样我们就可以对每一种情况编写相应的代码了。5．源代码 static int sum(int[] a) { int sum = 0; for (int i = 0; i < a.Length; i++) { sum = sum + a[i]; } return sum; } static void Main(string[] args) { string[] wu = new string[4] { "农夫", "狼", "羊", "白菜" }; int[] a = new int[4] { 3, 1, -1, 1 }; int[] b = new int[4] { 0, 0, 0, 0 }; Console.WriteLine(" 关于农夫过河的问题"); int weizhi = 0; do { if (a[0] == 3) { 1．实验要求 【实验目的】 1、进一步掌握指针、模板类、异常处理的使用 2、掌握栈的操作的实现方法 3、掌握队列的操作的实现方法 4、学习使用栈解决实际问题的能力 5、学习使用队列解决实际问题的能力 【实验内容】 利用栈结构实现八皇后问题。 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。 提示： 1、可以使用递归或非递归两种方法实现 2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2. 程序分析 2.1 存储结构 存储结构：栈（递归） 2.2 关键算法分析 【设计思想】 由于八皇后问题，可以分解成算法相同的子问题，所以使用递归的方法 【伪代码】 1、输入皇后个数n 2、k=1 3、判断k是否大于n 3.1 是：打印一组可能 3.2 否：循环行位置1~n 判断该位置是否符合要求，若符合记录q[k]的坐标y值 k+1 重复3 【关键算法】 1、递归 void Queen::Queens(int k,int n) { int i; if(k>n) { Print(n); count(); } else { for(i=1;i<=n;i++) if(Isavailable(i,k)) //判断该行中该位置放置‘皇后’是否符合要求 { q[k]=i; //记录改行中该点的位置 Queens(k+1,n); //放置下一行的‘皇后’ } } } 2、判断皇后放置位置是否符合要求 bool Queen::Isavailable(int i,int k) { int j; j=1; while(j Lab05．队列的操作及应用 【实验目的和要求】 1．掌握队列的顺序表示和链表表示下的基本操作； 2．深入理解深度优先搜索和广度优先搜索的思想并能正确描述其算法； 3．会应用广度优先搜索算法解决较复杂的问题。 【实验内容】 1．编写一个C源程序，其中包含顺序表示的空队列的创建、判断队列是否为空、进队、出队、取队列头部元素等操作。 2．编写一个C源程序，其中包含链表表示的空队列的创建、判断队列是否为空、进队、出队、取队列头部元素等操作。 3. 简述深度优先搜索和广度优先搜索的思想，并给出具体的算法步骤。 4．应用广度优先搜索算法求解农夫过河问题。 【实验仪器与软件】 1．CPU主频在1GHz以上，内存在512Mb以上的PC； 2．VC6.0，Word 2003及以上版本。 实验讲评： 实验成绩： 评阅教师： 2012 年月日 Lab05．队列的操作及应用 一、顺序表示的队列基本操作 1．顺序表示的队列操作基本源程序 #include 研究性学习实验报告 课题名称：有关全息投影的研究 班级：1403班 小组组长：郭嘉昕 小组成员：郭京伟段泽华王捷聪孙泽錡 日期：2015年3月 有关全息投影的实验报告 第一部分 有关实验选材的研究 一、实验设计思想 （1）实验目的 通过对比，研究不同材料对于光线的折射和漫反射的效果，并且在其中寻找效果最佳、性价比高的材料，进行下一步实验。 （2）实验原理 当一束平行的入射光线射到粗糙的表面时，表面会把光线向着四面八方反射，所以入射线虽然互相平行，由于各点的法线方向不一致，造成反射光线向不同的方向无规则地反射，这种反射称之为“漫反射”。 （3）实验方法 从成本方面考虑，先将不同材料做成面积的板状模型和立方体状模型，再将我们的光源设备调节到最高亮度，以最佳效果的角度将画面投射到不同的材料上。在同样暗度的房间里，用高度、距离固定的摄影机进行拍摄，再将不同材料的照片转入Photoshop,通过其内置的亮度数值初步判断不同材料的反射效果。将亮度（p）、材料制作的难易程度(q)以及其它视觉效果(w)三项各10分的标准分数按一定比例绘制出总分数，来选取实验材料。 实验测量表格如下： （4）实验仪器：各种实验材料*1、投影光源（4.7英寸）*1、摄像机*1、Windows电脑（Photoshop软件）*1 二、实验过程记录 （1）实验分工 （2）实验步骤 第一步—确定材料。因为我们是初次进行研究，对于具体的实验材料并不能确定，所以我们进行了解后，一共选取了4种材料： 第二步--选取材料。因为我们进行的实验成本非常有限所以我们必须先走向市场，来查看和询问有些材料是否可以被加工和购买到（具体材料价格请见附录）。将他们的难易程度（q）进行量化，10分为很容易得到，1分为基本不可能得到，以此绘制表格： 第三步—对比亮度。在了解了我们选取的材料的基础上，以节约环保为本，我们购买或借到了这四种材料。并选择在2015年3月8日的晚上，在教室里进行亮度测试。我们先将光源设备调节到最大亮度，拍摄的得到了一张照片，再不断尝试不同的角度，以求能用最好的效果反射光源并拍摄下来。我们将五张照片导入电脑，用Photoshop软件分别查看他们的RGM指数（具体RGM指数请见附录），来进行评分，但因为镜子的超好反射效果，我们改进了我们算法，以分段函数的方式来进行得分评判（p）。 评分结果如下 课程设计题目：农夫过河 一．问题描述 一个农夫带着一只狼、一只羊和一箩白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。过河有以下规则： (1)农夫一次最多能带一样东西（或者是狼、或者是羊、或者是白菜）过河； (2)当农夫不在场是狼会吃羊； (3)当农夫不在场是羊会吃掉白菜。 现在要求为农夫想一个方案，能将3样东西顺利地带过河。从出事状态开始，农夫将羊带过河，然后农夫将羊待会来也是符合规则的，然后农夫将羊带过河仍然是符合规则的，但是如此这般往返，搜索过程便进入了死循环，因此，在这里，采用改进的搜索算法进行搜索。 二．基本要求 (1)为农夫过河问题抽象数据类型，体会数据模型在问题求解中的重要性； (2)要求利用数据结构的方法以及Ｃ＋＋的编程思想来完成问题的综合设 计； (3)在问题的设计中，使用深度优先遍历搜索方式，避免死循环状态； (4)设计一个算法求解农夫过河问题，并输出过河方案； (5)分析算法的时间复杂度。 三．概要设计 (1)数据结构的设计 typedef struct // 图的顶点 { int farmer; // 农夫 int wolf; // 狼 int sheep; // 羊 int veget; // 白菜 }Vertex; 设计Vertex结构体的目的是为了存储农夫、狼、羊、白菜的信息，因为在遍历图的时候，他们的位置信息会发生变化，例如1111说明他们都在河的北岸，而0000说明他们都在河的南岸。 t ypedef struct { int vertexNum; // 图的当前顶点数 Vertex vertex[VertexNum]; // 顶点向量（代表顶点） bool Edge[VertexNum][VertexNum]; // 邻接矩阵. 用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关 }AdjGraph; // 定义图的邻接矩阵存储结构 存储图的方法是用邻接矩阵，所以设计一个简单的AdjGraph结构体是为了储图的顶点数与边数，农夫过河问题我采用的是图的深度优先遍历思想。 (2)算法的设计 深度优先遍历基本设计思想：设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的1/12边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。 程序中的深度优先遍历算法如下： void dfsPath(AdjGraph *graph, int start, int end) // 深度优先搜索从u到v的简单路径 //DFS--Depth First Search { int i = 0; visited[start] = true; //标记已访问过的顶点 if (start == end) N后问题算法 一、实验目的及要求 所要涉及或掌握的知识： 1. 了解皇后相互攻击的条件：如果任意两个皇后在同一行，同一列或同一对角线，则她们相互攻击。 2. 运用迭代的方法实现6皇后问题，求解得到皇后不相互攻击的一个解 3. 在运用迭代的方法实现编程时，要注意回溯点 二、问题描述及实验内容 对6皇后问题求解，用数组c[1…6]来存皇后的位置。c[i]=j表示第i个皇后放在第j列。 最后程序运行的结果是c[1…6]={1,5,8,6,3,7 } 三、问题分析和算法描述 6-QUEENS的算法表示： 输入：空。 输出：对应于6皇后问题的解的向量c[1…6]={1,5,8,6,3,7} 1. for k=1 to 6 2. c[k]=0 //没有放皇后 3. end for 4. flag=false 5. k=1 6. while k>=1 7.while c[k]<=5 8.c[k]=c[k]+1 9.if c为合法着色 then set flag=ture 且从两个while循环退出 10.else if c是部分解 then k=k+1 11.end while 12. c[k]=0 //回溯并c[k]=0 13. k=k-1 14. end while 15. if flag then output c 16. else output “no solution” 四、具体实现 # include *******大学 实验报告| | 实验名称PROLOG语言练习与编程上机实验 课程名称人工智能及应用 | | 专业班级：*******学生姓名：****** 学号：*******成绩： 指导教师：*******实验日期： 一、实验目的及要求 1、熟悉并掌握prolog的编程环境、prolog语言的回溯、递归技术和表处理技 术； 2、运用prolog及其相关技术，编写并调试求解农夫过河和模式搜索问题的程 序。要求实验报告中包括：程序及其注释和说明、程序运行结果。 二、所用仪器、设备 PC台式机和prolog编译软件 三、实验原理 1、prolog本身自带推理机，其回溯、递归技术和表处理技术可简化复杂问 题求解。 2、prolog的跟踪、设断点对于调试程序是非常有用的。 四、求解的问题与程序 农夫过河问题 opposite(s,n). opposite(n,s). safe_goat(X,_,X,_). safe_cabbage(X,_,_,X). safe_goat(F,X,Y,_):-opposite(X,Y). safe_cabbage(F,_,X,Y):-opposite(X,Y). is_peaceful(F,W,G,C):-safe_goat(F,W,G,C),safe_cabbage(F,W,G,C). transform(location(X,W,G,C),location(Y,W,G,C)):-opposite(X,Y). transform(location(X,X,G,C),location(Y,Y,G,C)):-opposite(X,Y). transform(location(X,W,X,C),location(Y,W,Y,C)):-opposite(X,Y). transform(location(X,W,G,X),location(Y,W,G,Y)):-opposite(X,Y). member(X,[X|_]). member(X,[_|T]):-member(X,T). legal_states(location(F0,W0,G0,C0),location(F,W,G,C),States,X):- transform(location(F0,W0,G0,C0),location(F1,W1,G1,C1)), 农夫过河 教学目标 1、知识与能力：通过农夫过河的数学逻辑问的题，探讨研究找到解决问题的办法和养成自己动脑动手的解决问题的能力。 2、过程与方法：通过以角色扮演的形式让学生自己动脑动手寻找答案和探讨解决问题的方法。 3、态度价值观：知道数学有很多有趣的东西，培养爱科学的情感。教师准备 1. 数学课件。 2、做“狼、羊、白菜、农夫”头饰。 3、准备四张纸分别写上“狼、羊、白菜、农夫”。 教学过程 一、谈话导入 介绍我国著名的数学家华罗庚爷爷。 数学家华罗庚生平介绍，主要科学业绩，对数学的贡献等等。介绍华罗庚爷爷的话。“数学本身，也是无穷的美妙，认为数学枯燥，是不正确的，就像站在花园外面，说花园枯燥无味一样，只要你踏进大门，随时会发现数学有许多有趣的东西。”数学并不是几个数字算来算去，它的学问大着呢。下面这道题能引起你的兴趣吗？ 二、创设情境 1、出示数学问题：有一个农夫带一匹狼、一只羊和一棵白菜过河（从河的东岸到西岸）。如果没有农夫看管，则狼要吃羊，羊要吃白菜。 但是船很小，只够农夫带一样东西过河。 2、图片演示。（一条河；一边是对岸；另一边是河岸，有农夫、狼、羊、白菜） 三、探究学习 1、以小组表演形式（演示出河的位置）和讨论形式解题 第一步是什么？必须是什么？（农夫和羊先过河） 第二步是什么？（农夫自己回来） 第三步是什么？ 2、全班学生汇报交流 问题的突破口在——狼与白菜能够共存！农夫、狼、羊、白菜和船组成了这个系统。系统中各要素是一个整体，都依赖农夫过河；最大的问题是“船很小，只够农夫带一样东西过河”和“没有农夫看管，则狼要吃羊，羊要吃白菜”的冲突。我们联系已知条件，做了一系列的分析实验，但是比较其他方案不能实现所有要素都安全过河。最后得出以上方案。 具体描述如下： 第一步：把羊带过河，坐船返回； 第二步：把狼带过河，带羊返回； 第三步：将羊放在这一岸后，带白菜过河； 第四步：坐船返回，把羊带过河。 或者： 第一步：把羊带过河，坐船返回；人工智能实验一指导
商人过河实验报告
农夫过河数据结构
人工智能实验报告
算法实验 递归回溯解八皇后问题
MC牧师过河问题
农夫过河问题状态图及程序
农夫过河问题状态空间表示
农夫过河实验报告――数据结构
数学模型实验商人过河
数据结构实验报告利用栈结构实现八皇后问题
农夫过河实验报告
C# 关于农夫过河的问题
数据结构实验报告——栈(八皇后问题)
LAB05+队列的操作及应用
研究性学习实验报告
农夫过河问题
n皇后问题实验报告
PROLOG实验报告
趣味数学教案—农夫过河
相关主题
文本预览