数据结构与算法分析实验报告.doc

《数据结构与算法分析实验报告.doc》由会员分享，可在线阅读，更多相关《数据结构与算法分析实验报告.doc（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法分析实验报告学院：电信学院班级：计算机06学号：xxx姓名：xxx小组成员：xxx2011年12月20日实验四 八皇后问题1、问题描述 设在初始状态下，在国际象棋的棋盘上没有任何棋子（这里的棋子指皇后棋子）。然后顺序在第1行，第2行第8行上布放棋子。在每一行中共有8个选择的位置，但在任一时刻棋盘的合法布局都必须满足3个限制条件（1）任意两个棋子得放在同一行（2）任意两个棋子不得放在同一列上（3）任意棋子不得放在同一正斜线和反斜线上。2、基本要求 编写求解并输出此问题的一个合法布局的程序。3、实现提示 在第i行布放棋子时，从第1列到第8列逐列考察。当在第i行第j列布放棋子时，需要考

2、察布放棋子后在行方向列方向正斜线和反斜线方向上的布局状态是否合法，若该棋子布放合法，再递归求解在第i+1行布放棋子；若该棋子布放不合法，移去这个棋子，恢复布放该棋子前的状态，然后再试探在第i行第j列布放旗子。解：编写程序如下：#include#define NUM 8 int aNUM+1;int main()int i,k,flag,not_finish=1,count=0;i=1; a1=1; printf(The possible configuration of 8 queens are: n);while(not_finish)while(not_finish&i=NUM) for(

3、flag=1,k=1;flag&ki;k+) if(ak=ai)flag=0;for(k=1;flag&k1&ai=NUM)ai=1; else if(i=1&ai=NUM)not_finish=0; else ai+; else if(ai=NUM) ai=1;else ai+; else if(+i=NUM)if(ai-1=NUM) ai=1;else ai=ai-1+1; if(not_finish)+count;printf(count-1)%3? %2d: : %2d: ,count);for(k=1;k=NUM;k+) printf( %d,ak);if(aNUM-10）个人按顺时

4、针方向围坐一圈，每人持有一个正整数密码。开始时任意给出一个报数上限m，从第一个人开始顺时针方向自1起报数，报到m时停止报数，报 m的人出列，将他的密码作为新的m值，从在他顺时针方向上的下一个人起重新自1报数；如此下去，直到所有人全部出列为止。2、基本要求设计一个程序模拟此过程，给出出列人的编号序列。3、实现提示 可考虑不带头指针的单链表结构。4、测试数据 N=7，其个人的密码依次为：3,1,7,2,4,8,4. 初始报数上限值m=20。解：编写程序如下：#includeclass Nodepublic:int number,data;Node *next;Node(int a,int b)nu

5、mber=a;data=b;next=0;class Circlepublic:Node *Head,*Tail;Circle()Head=Tail=0;void add(Node *p)if(Head=0)Head=Tail=p;elseTail-next=p;Tail=p;Tail-next=Head;int search(int a)Node *p,*q;int d;p=Head;if(p=p-next)coutnumberendl;return 0;for(int i=1;inext;coutnumberdata;if(i=1)q=p;p=p-next;q-data=p-data;q-

6、number=p-number;Head=q;q-next=p-next;delete p;return d;Head=q-next=p-next;delete p;return d;int out(int a)while(a=search(a);return 1;int main()Circle a;int amount,d;Node *p;cout请输入人数amount;cout请依次输入其密码endl;for(int i=0;id;p=new Node(i+1,d);a.add(p);cout请输入起始数d;cout*endl;a.out(d);return 1;运行结果如下：算法分析：S1：创建一个链表，表头指向表尾，形成一个环；S2：从头结点即尾结点的下一个结点，开始报数，若所报的数小于d，i+，直至所报的数等于d，将报d的结点的number输出，并将其从链表中删掉；S3：继续s2，直至将链表中所有结点输出；S4：此时链表为空，程序结束。时间复杂度为：O(a-1)*d)空间复杂度为：O（2）