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

精选优质文档-倾情为你奉上八皇后问题1.问题描述 设在初始状态下在国际象棋的棋盘上没有任何棋子（这里的棋子指皇后棋子）。然后顺序在第1行，第2行第8行上布放棋子。在每一行中共有8个可选择的位置，但在任一时刻棋盘的合法布局都必须满足3个限制条件（1）任意两个棋子不得放在同一行（2）任意两个棋子不得放在同一列上（3）任意棋子不得放在同一正斜线和反斜线上。2.基本要求 编写求解并输出此问题的一个合法布局的程序。3、实现提示： 在第i行布放棋子时，从第1列到第8列逐列考察。当在第i行第j列布放棋子时，需要考察布放棋子后在行方向、列方向、正斜线和反斜线方向上的布局状态是否合法，若该棋子布放合法，再递归求解在第i+1行布放棋子；若该棋子布放不合法，移去这个棋子，恢复布放该棋子前的状态，然后再试探在第i行第j+1列布放棋子。4 程序代码#include<iostream.h>#include<stdio.h>static 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;Line<8;Line+) aLine=0; /列标记初始化，表示无列冲突 for(Column=0;Column<8;Column+) QueenLineColumn='*' /主、从对角线标记初始化，表示没有冲突 for(Line=0;Line<15;Line+) bLine=cLine=0; qu(0); return 0;void qu(int i) int Column; for(Column=0;Column<8;Column+) if(aColumn=0&&bi-Column+7=0&&ci+Column=0) /如果无冲突 QueeniColumn='Q' /放皇后 aColumn=1; /标记，下一次该列上不能放皇后 bi-Column+7=1; /标记，下一次该主对角线上不能放皇后 ci+Column=1; /标记，下一次该从对角线上不能放皇后 if(i<7) qu(i+1); /如果行还没有遍历完，进入下一行 else /否则输出 /输出棋盘状态 int Line,Column;cout<<"第"<<+QueenNum<<"种状态为："<<endl; for(Line=0;Line<8;Line+) for(Column=0;Column<8;Column+) cout<<QueenLineColumn<<" " cout<<endl; cout<<endl;getchar(); /*如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置*/ QueeniColumn='*' aColumn=0; bi-Column+7=0; ci+Column=0; 5 程序结果题目2 背包问题的求解1.问题描述 假设有一个能装入总体积为T的背包和n件体积分别为w1,w2,wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+wm=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 datamaxsize;seqlist; /定义顺序表结构体typedef struct int top; int sum; int datamaxsize;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->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(i<=l->last) push_seqstack(l,i,s); if(s->sum=n) printf("-n可行的解是:"); for(t=0;t<=s->top;t+) printf("%d ",l->datas->datat); printf("n"); pop_seqstack(l,s,&i); i+; else if(s->sum>n) 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 <stdio.h> #include <stdlib.h> #include <string.h> #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<string.h> #include<ctype.h> /是在调用字符函数时，在源文件中包含的头文件。 #include<malloc.h> #include<limits.h> / INT_MAX等 #include<stdio.h> / EOF(=Z或F6),NULL #include<stdlib.h> / atoi()52 #include<io.h> / eof() #include<math.h> / floor(),ceil(),abs() #include<process.h> / exit() #include<iostream.h> / 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;i<G.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;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).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;i<G.vexnum;+i) printf("%s ",G.verticesi.data); printf("n%d条弧(边):n",G.arcnum); for(i=0;i<G.vexnum;i+) p=G.verticesi.firstarc; while(p) printf("%s%s ",G.verticesi.data,G.verticesp->adjvex.data); p=p->nextarc; printf("n"); void iiiiiiFindInDegree(ALGraph G,int indegree) /* 求顶点的入度，算法调用 */ int i; ArcNode *p; for(i=0;i<G.vexnum;i+) indegreei=0; /* 赋初值 */ for(i=0;i<G.vexnum;i+) p=G.verticesi.firstarc; while(p) indegreep->adjvex+; p=p->nextarc; void FindInDegree(ALGraph G,int indegree) /* 求顶点的入度，算法调用 */ int i,j; ArcNode *p; for(i=0;i<G.vexnum;i+) indegreei=0; /* 赋初值 */ for(i=0;i<G.vexnum;i+) for(j=0;j<G.vexnum;j+) p=G.verticesj.firstarc; while(p) if(p->adjvex=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无回路,则输出G的顶点的一个拓扑序列并返回OK, */ /* 否则返回ERROR。 */ int i,k,j=0,count,indegreeMAX_VERTEX_NUM; SqStack S; pathone a; pathtwo b; ArcNode *p; FindInDegree(G,indegree); /* 对各顶点求入度indegree0.vernum-1 */ InitStack(&S); /* 初始化栈 */ for(i=0;i<G.vexnum;+i) /* 建零入度顶点栈S */ if(!indegreei) Push(&S,i); /* 入度为0者进栈 */ count=0; /* 对输出顶点计数 */ while(!StackEmpty(S) /* 栈不空 */ Pop(&S,&i); ai=*G.verticesi.data; bi=*G.verticestwoi.data; printf("课程%s学分%s ",G.verticesi.data,G.verticestwoi.data); /* 输出i号顶点并计数 */ +count; for(p=G.verticesi.firstarc;p;p=p->nextarc) /* 对i号顶点的每个邻接点的入度减1 */ k=p->adjvex; if(!(-indegreek) /* 若入度减为0,则入栈 */ Push(&S,k); printf("n"); if(count<G.vexnum) printf("Error!此有向图有回路!n"); return ERROR; else printf("Right!为一个拓扑序列。n"); while(q<=xqzs) int C=0; if(X<=G.arcnum)while(C<=xfsx)C+=*G.verticestwoZ.data; +Z; printf("第%d个学期应学课程:",q); while(X<=Z) printf("%s ",G.verticesX.data); +X; cout<<endl; q+; else cout<<"课程编制已经完成！"<<endl; return OK; return OK;void main() ALGraph f; printf("教学计划编制问题的求解过程:n"); printf("请输入学期总数:"); scanf("%d",&xqzs); printf("请输入学期的学分上限:"); scanf("%d",&xfsx); CreateGraph(&f); /构造图 Display(f); TopologicalSort(f);试验总结通过本次实验,使我认识了更多的关于数据结构的知识,也使我学到 了更多的知识,而且在做的过程中遇到了一些问题,通过与同学的讨论得到了顺利的解决,加深了同学之间的友谊!专心-专注-专业