数据结构与算法专题实验实验报告_八皇后_背包问题求解_农夫过河.
时间：2020-11-21 13:11:32 来源：勤学考试网 本文已影响 人 
八皇后问题
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 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 main()
{
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<<"种状态为："<<endl;
for(Line=0;Line<8;Line++)
{
for(Column=0;Column<8;Column++)
cout<<Queen[Line][Column]<<" ";
cout<<endl;
}
cout<<endl;
getchar();
}
/*如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置*/
Queen[i][Column]='*';
a[Column]=0;
b[i-Column+7]=0;
c[i+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 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
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的安全路径。
以广度优先为例：整数队列---逐层存放下一步可能的安全状态；Visited[16]数组标记该状态是否已访问过，若访问过，则记录前驱状态值---安全路径。
最终的过河方案应用汉字显示出每一步的两岸状态。
3 程序代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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<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 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<G.vexnum;++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_NAME);
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<G.vexnum;++i)
printf("%s ",G.vertices[i].data);
printf("\n%d条弧(边):\n",G.arcnum);
for(i=0;i<G.vexnum;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<G.vexnum;i++)
indegree[i]=0; /* 赋初值 */
for(i=0;i<G.vexnum;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<G.vexnum;i++)
indegree[i]=0; /* 赋初值 */
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;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+STACKINCREMENT)*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<G.vexnum;++i) /* 建零入度顶点栈S */
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<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.verticestwo[Z].data;
++Z;
}
printf("第%d个学期应学课程:",q);
while(X<=Z)
{
printf("%s ",G.vertices[X].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);
}
试验总结
通过本次实验,使我认识了更多的关于数据结构的知识,也使我学到 了更多的知识,而且在做的过程中遇到了一些问题,通过与同学的讨论得到了顺利的解决,加深了同学之间的友谊!
