數(shù)據(jù)結構與算法分析實驗報告.doc

數(shù)據(jù)結構與算法分析實驗報告學院：電信學院班級：計算機06學號：xxx姓名：xxx小組成員：xxx2011年12月20日實驗四 八皇后問題1、問題描述 設在初始狀態(tài)下，在國際象棋的棋盤上沒有任何棋子（這里的棋子指皇后棋子）。然后順序在第1行，第2行第8行上布放棋子。在每一行中共有8個選擇的位置，但在任一時刻棋盤的合法布局都必須滿足3個限制條件（1）任意兩個棋子得放在同一行（2）任意兩個棋子不得放在同一列上（3）任意棋子不得放在同一正斜線和反斜線上。2、基本要求 編寫求解并輸出此問題的一個合法布局的程序。3、實現(xiàn)提示 在第i行布放棋子時，從第1列到第8列逐列考察。當在第i行第j列布放棋子時，需要考察布放棋子后在行方向列方向正斜線和反斜線方向上的布局狀態(tài)是否合法，若該棋子布放合法，再遞歸求解在第i+1行布放棋子；若該棋子布放不合法，移去這個棋子，恢復布放該棋子前的狀態(tài)，然后再試探在第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(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）個人按順時針方向圍坐一圈，每人持有一個正整數(shù)密碼。開始時任意給出一個報數(shù)上限m，從第一個人開始順時針方向自1起報數(shù)，報到m時停止報數(shù)，報 m的人出列，將他的密碼作為新的m值，從在他順時針方向上的下一個人起重新自1報數(shù)；如此下去，直到所有人全部出列為止。2、基本要求設計一個程序模擬此過程，給出出列人的編號序列。3、實現(xiàn)提示 可考慮不帶頭指針的單鏈表結構。4、測試數(shù)據(jù) N=7，其個人的密碼依次為：3,1,7,2,4,8,4. 初始報數(shù)上限值m=20。解：編寫程序如下：#includeclass Nodepublic:int number,data;Node *next;Node(int a,int b)number=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-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請輸入人數(shù)amount;cout請依次輸入其密碼endl;for(int i=0;id;p=new Node(i+1,d);a.add(p);cout請輸入起始數(shù)d;cout*endl;a.out(d);return 1;運行結果如下：算法分析：S1：創(chuàng)建一個鏈表，表頭指向表尾，形成一個環(huán)；S2：從頭結點即尾結點的下一個結點，開始報數(shù)，若所報的數(shù)小于d，i+，直至