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

{

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(\请依次输入个物品的大小，输入0结束。\\n-------------------------------------------\\n\ scanf(\ while(x!=0) {

l->data[l->last]=x; l->last++;

scanf(\ }

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(\可行的解是:\ for(t=0;t<=s->top;t++)

printf(\\ printf(\

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(\执行完毕\ } } }

int main() {

int n; seqlist *l;

printf(\请输入背包体积n的大小，n=?\ scanf(\ 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 #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 {