数据结构与算法专题实验实验报告-八皇后-背包问题的求解-农夫过河.docx
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《数据结构与算法专题实验实验报告-八皇后-背包问题的求解-农夫过河.docx》由会员分享,可在线阅读,更多相关《数据结构与算法专题实验实验报告-八皇后-背包问题的求解-农夫过河.docx(18页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上八皇后问题1.问题描述 设在初始状态下在国际象棋的棋盘上没有任何棋子(这里的棋子指皇后棋子)。然后顺序在第1行,第2行第8行上布放棋子。在每一行中共有8个可选择的位置,但在任一时刻棋盘的合法布局都必须满足3个限制条件(1)任意两个棋子不得放在同一行(2)任意两个棋子不得放在同一列上(3)任意棋子不得放在同一正斜线和反斜线上。2.基本要求 编写求解并输出此问题的一个合法布局的程序。3、实现提示: 在第i行布放棋子时,从第1列到第8列逐列考察。当在第i行第j列布放棋子时,需要考察布放棋子后在行方向、列方向、正斜线和反斜线方向上的布局状态是否合法,若该棋子布放合法,再递归求
2、解在第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; /列标记初始化,表示无列冲突 f
3、or(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; /标记,下一次该主
4、对角线上不能放皇后 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=-
5、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-
6、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;
7、 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
8、);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.问题描述 一个农夫带着一只狼、一只羊和一棵白菜,身处河的南岸。他要把这些东西 全部运到北岸。他面前只有一条小船,船只能容下他和一件物品,另外只有农夫 才能撑船。如果农夫在场,则狼不能吃羊,羊不能吃白菜,否则狼会吃羊,羊会 吃白菜,所以农夫不能留下羊和白菜自己离开,也不能留下狼和羊自己离开
9、,而 狼不吃白菜。请求出农夫将所有的东西运过河的方案。2.实现提示 求解这个问题的简单方法是一步一步进行试探,每一步搜索所有可能的选择 ,对前一步合适的选择后再考虑下一步的各种方案。要模拟农夫过河问题,首先 需要对问题中的每个角色的位置进行描述。可用4位二进制数顺序分别表示农夫、 狼、白菜和羊的位置。用0表在南岸,1表示在北岸。例如,整数5 (0101)表示农 夫和白菜在南岸,而狼和羊在北岸。 现在问题变成:从初始的状态二进制0000(全部在河的南岸)出发,寻找一种 全部由安全状态构成的状态序列,它以二进制1111(全部到达河的北岸)为最终目 标。总状态共16种(0000到1111),(或者看
10、成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 sear
11、ch(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 != aiStep
12、3 & (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
13、() search(0); return 0; 4 程序结果题目4教学计划编制问题1.问题描述 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年 限,每学年含两学期,每学期的时间长度和学分上限值均相等。每个专业 开设的课程都是固定的,而且课程在开设时间的安排必须满足先修关系。 每门课程有哪些先修课程是确定的,可以有任意多门,也可以没有。每门 课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。2.基本要求 (1)输入参数包括:学期总数,一学期的学分上限,每门课的课程号 (固定占3位的字母数字串)、学分和直接先修课的课程号。 (2)允许用户指定下列两种编排策略之一:一是使学生
14、在各学期中的 学习负担尽量均匀;二是使课程尽可能地集中在前几个学期中。 (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 #i
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 专题 实验 报告 皇后 背包 问题 求解 农夫 过河
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内