数据结构与算法专题实验实验报告-八皇后-背包问题的求解-农夫过河

八皇后问题1.问题描述 设在初始状态下在国际象棋的棋盘上没有任何棋子（这里的棋子指皇后棋子）。然后顺序在第1行，第2行第8行上布放棋子。在每一行中共有8个可选择的位置，但在任一时刻棋盘的合法布局都必须满足3个限制条件（1）任意两个棋子不得放在同一行（2）任意两个棋子不得放在同一列上（3）任意棋子不得放在同一正斜线和反斜线上。2.基本要求 编写求解并输出此问题的一个合法布局的程序。3、实现提示： 在第i行布放棋子时，从第1列到第8列逐列考察。当在第i行第j列布放棋子时，需要考察布放棋子后在行方向、列方向、正斜线和反斜线方向上的布局状态是否合法，若该棋子布放合法，再递归求解在第i+1行布放棋子；若该棋子布放不合法，移去这个棋子，恢复布放该棋子前的状态，然后再试探在第i行第j+1列布放棋子。4 程序代码#include#includestatic char Queen88;static int a8;static int b15;static int c15;static int QueenNum=0; /记录总的棋盘状态数void qu(int i); /参数i代表行int main() int Line,Column; /棋盘初始化，空格为*，放置皇后的地方为 for(Line=0;Line8;Line+) aLine=0; /列标记初始化，表示无列冲突 for(Column=0;Column8;Column+) QueenLineColumn=*; /主、从对角线标记初始化，表示没有冲突 for(Line=0;Line15;Line+) bLine=cLine=0; qu(0); return 0;void qu(int i) int Column; for(Column=0;Column8;Column+) if(aColumn=0&bi-Column+7=0&ci+Column=0) /如果无冲突 QueeniColumn=Q; /放皇后 aColumn=1; /标记，下一次该列上不能放皇后 bi-Column+7=1; /标记，下一次该主对角线上不能放皇后 ci+Column=1; /标记，下一次该从对角线上不能放皇后 if(i7) qu(i+1); /如果行还没有遍历完，进入下一行 else /否则输出 /输出棋盘状态 int Line,Column;cout第+QueenNum种状态为：endl; for(Line=0;Line8;Line+) for(Column=0;Column8;Column+) coutQueenLineColumn ; coutendl; couttop=-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-datas-top=i; /顺序表中第i 个元素，i 入栈 s-sum=s-sum+l-datai; /栈中sum加和！ return 1; int pop_seqstack(seqlist *l,seqstack *s,int *x) /出栈 if(empty_seqstack(s) return 0; else *x=s-datas-top; s-sum=s-sum-l-datas-datas-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-datal-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(ilast) push_seqstack(l,i,s); if(s-sum=n) printf(-n可行的解是:); for(t=0;ttop;t+) printf(%d ,l-datas-datat); printf(n); pop_seqstack(l,s,&i); i+; else if(s-sumn) pop_seqstack(l,s,&i); i+; else i+; 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 农夫过河问题的求解1.问题描述 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西 全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫 才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会 吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而 狼不吃白菜。请求出农夫将所有的东西运过河的方案。2.实现提示 求解这个问题的简单方法是一步一步进行试探，每一步搜索所有可能的选择 ，对前一步合适的选择后再考虑下一步的各种方案。要模拟农夫过河问题，首先 需要对问题中的每个角色的位置进行描述。可用4位二进制数顺序分别表示农夫、 狼、白菜和羊的位置。用0表在南岸，1表示在北岸。例如，整数5 (0101)表示农 夫和白菜在南岸，而狼和羊在北岸。 现在问题变成：从初始的状态二进制0000(全部在河的南岸)出发，寻找一种 全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸)为最终目 标。总状态共16种(0000到1111)，(或者看成16个顶点的有向图)可采用广度优先或深度优先的搜索策略-得到从0000到1111的安全路径。 以广度优先为例：整数队列-逐层存放下一步可能的安全状态；Visited16数组标记该状态是否已访问过，若访问过，则记录前驱状态值-安全路径。 最终的过河方案应用汉字显示出每一步的两岸状态。3 程序代码#include #include #include #define MAX 20 int aMAX4; / 0 ：狼，1：羊，2：菜，3：农夫，value：0：本岸，1:对岸 int bMAX; /b+1记录每一步农夫的什么char *name = 空手, 带狼, 带羊, 带菜 ; void search(int iStep) int i; if (aiStep0 + aiStep1 + aiStep2 + aiStep3 = 4) for (i = 0; i iStep; i+) if (ai3 = 0) printf(农夫%s到对岸n, namebi + 1); else printf(农夫%s回本岸n, namebi + 1); printf(n); printf(n); return; for (i = 0; i iStep; i+) if (memcmp(ai, aiStep, sizeof(ai) = 0) /已经找过 return; if (aiStep1 != aiStep3 & (aiStep2 = aiStep1 | aiStep0 = aiStep1) /危险 return; for (i = -1; i = 2; i+) biStep = i; memcpy(aiStep + 1, aiStep, sizeof(aiStep + 1); aiStep + 13 = 1 - aiStep + 13; /农夫过河 if (i = -1) /空手回 search(iStep + 1); else if (aiStepi = aiStep3) /不空手回 aiStep + 1i = aiStep + 13; 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 / INT_MAX等 #include / EOF(=Z或F6),NULL #include / atoi()52 #include / eof() #include / floor(),ceil(),abs() #include / exit() #include / cout,cin / 函数结果状态代码 #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 VertexTypeMAX_NAME; / 字符串类型 /* 图的邻接表存储表示 p163 */ #define MAX_VERTEX_NUM 100 typedef enumDG,DN,UDG,UDNGraphKind; /* 有向图,有向网,无向图,无向网 */ typedef struct ArcNode int adjvex; /* 该弧所指向的顶点的位置 */ struct ArcNode *nextarc; /* 指向下一条弧的指针 */ InfoType *info; /* 该弧相关信息的指针（网的权值指针 */ ArcNode; /* 表结点 */ typedef struct VertexType data; /* 顶点信息 */ ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */ VNode,AdjListMAX_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;iG.vexnum;+i) if(strcmp(u,G.verticesi.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).verticesi.data); (*G).verticesi.firstarc=NULL; printf(请输入%d个课程的学分值(%d个字符):n,(*G).vexnum,MAX_NAME); for(i=0;i(*G).vexnum;+i) /* 构造顶点向量 */ scanf(%s,(*G).verticestwoi.data); printf(请顺序输入每条弧的弧尾和弧头(以空格作为间隔):n); for(k=0;kadjvex=j; p-info=NULL; p-nextarc=(*G).verticesi.firstarc; /* 插在表头 */ (*G).verticesi.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;iG.vexnum;+i) printf(%s ,G.verticesi.data); printf(n%d条弧(边):n,G.arcnum); for(i=0;iadjvex.data); p=p-nextarc; printf(n); void iiiiiiFindInDegree(ALGraph G,int indegree) /* 求顶点的入度，算法调用 */ int i; ArcNode *p; for(i=0;iG.vexnum;i+) indegreei=0; /* 赋初值 */ for(i=0;iadjvex+; p=p-nextarc; void FindInDegree(ALGraph G,int indegree) /* 求顶点的入度，算法调用 */ int i,j; ArcNode *p; for(i=0;iG.vexnum;i+) indegreei=0; /* 赋初值 */ for(i=0;iG.vexnum;i+) for(j=0;jadjvex=i) indegreep-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+STACKINCREMENT)*sizeof(SElemType); if(!(*S).base) exit(OVERFLOW); /* 存储分配失败 */ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; *(*S).top)+=e; return OK; typedef int pathoneMAXCLASS;typedef int pathtwoMAXCLASS;/拓扑排序的算法p182Status TopologicalSort(ALGraph G) /* 有向图G采用邻接表存储结构。若G无回