《数据结构与算法专题实验实验报告-八皇后-背包问题的求解-农夫过河》由会员分享，可在线阅读，更多相关《数据结构与算法专题实验实验报告-八皇后-背包问题的求解-农夫过河（18页珍藏版）》请在金锄头文库上搜索。
1、八皇后问题1.问题描述 设在初始状态下在国际象棋的棋盘上没有任何棋子（这里的棋子指皇后棋子）。然后顺序在第1行，第2行第8行上布放棋子。在每一行中共有8个可选择的位置，但在任一时刻棋盘的合法布局都必须满足3个限制条件（1）任意两个棋子不得放在同一行（2）任意两个棋子不得放在同一列上（3）任意棋子不得放在同一正斜线和反斜线上。2.基本要求 编写求解并输出此问题的一个合法布局的程序。3、实现提示： 在第i行布放棋子时，从第1列到第8列逐列考察。当在第i行第j列布放棋子时，需要考察布放棋子后在行方向、列方向、正斜线和反斜线方向上的布局状态是否合法，若该棋子布放合法，再递归求解在第i+1行布放棋子；若
2、该棋子布放不合法，移去这个棋子，恢复布放该棋子前的状态，然后再试探在第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;C
3、olumn8;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+
4、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;
5、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-
6、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
7、 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=
8、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(全部在
