2013314209張協(xié)鎏.docx

Foshan University數(shù)據(jù)結(jié)構(gòu)與算法期末實驗題 學 院： 電子與信息工程學院 專 業(yè)： 13計算機科學與技術(shù)2班 學 號： 2013314209 學生姓名： 張協(xié)鎏 二 一 五 年 一 月一、題目：卡片問題 等級B一、問題描述有一疊n張卡片，從上到下依次編號為1n，從最上面的一張開始按如下的順序進行操作：把最上面的第一張卡片拿掉，把下一張卡片放在這一疊卡片的最下面；再把最上面的第一張卡片拿掉，把下一張卡片放在這一疊卡片的最下面；依次重復(fù)這樣做，直到手中剩下一張卡片。當n=500時，請按拿走卡片的順序，列出每次拿掉的卡片數(shù)字。二、算法的基本思想新建循環(huán)隊列;向循環(huán)隊列中插入元素;依次刪除隊頭元素,將隊尾指針賦予新的隊頭元素的值,對隊頭指針后移;將剩余的最后一個元素輸出;1. 數(shù)據(jù)結(jié)構(gòu)定義typedef struct /定義循環(huán)隊列QElemtype *base; int front;int rear;SqQueue;SqQueue Q;QElemtype e,x;2. 各模塊之間的調(diào)用關(guān)系主函數(shù) void main()定義循環(huán)隊列指針SqQueue *p= &Q初始化循環(huán)隊列InitQueue(p)調(diào)用入隊操作EnQueue(p,x)調(diào)用出隊操作DeQueue(p)調(diào)用隊列順序改變操作kapian（p）三、 測試數(shù)據(jù)四、源程序#include#include #define ERROR -1#define OK 1#define n 10000typedef int QElemType;typedef struct QElemType *base; int front; int rear;SqQueue;SqQueue Q;int InitQueue(SqQueue *Q)/構(gòu)造一個空隊列Q Q-base=(QElemType*)malloc(n+1)*sizeof(QElemType); if(!Q-base) return ERROR; Q-front=Q-rear=0; return OK;int EnQueue(SqQueue *Q,QElemType x)/插入元素X為新的隊尾元素 if(Q-rear+1)%(n+1)=Q-front) return ERROR; Q-baseQ-rear=x; Q-rear=(Q-rear+1)%(n+1); return OK;int DeQueue(SqQueue *Q,QElemType &x)/刪除隊頭元素,用X返回其值 x=Q-baseQ-front; if(Q-front=Q-rear) return ERROR;Q-front=(Q-front+1)%(n+1); return OK;int kapian(SqQueue *Q) Q-baseQ-rear=Q-baseQ-front; Q-front=(Q-front+1)%(n+1); Q-rear=(Q-rear+1)%(n+1); return OK;void main()int i,m,s;printf(請輸入卡片數(shù)量s=);scanf(%d,&s);printf(卡片取出順序為:n);SqQueue *p= &Q; InitQueue(p); for(i=1;i=s;i+) EnQueue(p,i); while(Q.rear-1)%(n+1)!=Q.front%(n+1) DeQueue(p,m); kapian(p); printf(%4d,m);printf(n);二、題目：約瑟夫問題 等級C一、問題描述問題描述：有N個小孩圍成一圈，從第K個兒童從1開始依次報數(shù)，直到數(shù)到M，數(shù)到M的同學出列，下一個同學再從1開始報數(shù)到M，依次循環(huán)，直到最后剩下一個同學，問最后一個同學是誰。當n=50，k=12時，請按次序列出出列的同學序號。二、算法的基本思想首先設(shè)計實現(xiàn)約瑟夫環(huán)問題的存儲結(jié)構(gòu)。由于約瑟夫環(huán)問題本身具有循環(huán)性質(zhì)，考慮利用循環(huán)鏈表。為了統(tǒng)一對表中任意結(jié)點的操作，循環(huán)鏈表不帶頭結(jié)點。其次，建立一個不帶頭結(jié)點的循環(huán)鏈表并由頭結(jié)點指示。最后，設(shè)計約瑟夫環(huán)問題的算法。1、 先定義一個結(jié)構(gòu)體存儲人員結(jié)點類型和結(jié)點指針類型。再設(shè)計約瑟夫環(huán)問題的算法。2、 以無頭結(jié)點的單循環(huán)鏈表為存儲結(jié)構(gòu)模擬此過程。3、 判斷輸入的總?cè)藬?shù)n是否大于0，是就執(zhí)行下一步，否則返回main（）函數(shù)。4、 創(chuàng)建新結(jié)點，對線性表初始化，并賦值1到n，令最后一個結(jié)點指向第1個結(jié)點。5、 循環(huán)求得前n-1個出隊結(jié)點，輸出其人員編號，并刪除結(jié)點。6、 輸出最后一個人員編號，并刪除最后一個結(jié)點。7、 最后編寫main（）函數(shù)。三、測試數(shù)據(jù)四、源程序#include#define N 100struct child int no; int next;struct child linkN;void main() int i,n,m,s,count,h;/定義變量 printf(輸入圍圈人數(shù)，出圈報數(shù)，開始報數(shù)位置：); scanf(%d,%d,%d,&n,&m,&s);/n是總?cè)藬?shù)，m是出圈號，s是初始報數(shù)位置。 for(i=1;i=n;i+) if(i=n)linki.next=1;/圍成一圈， else linki.next=i+1; linki.no=i; count=0; if(s=1)h=n; else h=s-1; /如果從1號開始報數(shù)，1號的前一位是n號。如果從s開始報數(shù)，s的前一位是s-1號。 printf(出圈順序為：n); while(countn-1)/count是圈外人數(shù)，當count=n-1時，不再執(zhí)行while循環(huán)，圈內(nèi)還剩下一人。 i=0; while(i!=m) h=linkh.next; if(linkh.no)/判斷當前號的值是否已置0， i+; printf(%4d,linkh.no);/依次輸出出圈的人的編號 linkh.no=0; count+; printf(n最后出圈的人的編號：); for(i=1;i=n;i+)/最后出圈的人的編號 if(linki.no!=0) printf(%dn,linki.no);三、題目：數(shù)組效率問題 等級C一、問題描述問題描述：一個整形數(shù)組int a100 保存1-100 現(xiàn)在隨機將其中兩個數(shù)改為0， 找出這兩個數(shù)，要求時間和空間復(fù)雜度盡量小。二、算法的基本思想1、先對數(shù)組進行順序賦值2、然后使用srand(time(NULL)取出隨機的兩個數(shù)字，并對取出的數(shù)值置為0.3、對數(shù)組中的數(shù)字進行排序4、利用相鄰數(shù)字的數(shù)字差可求出隨機取出的數(shù)字。5、最后輸出取出的數(shù)字。三、測試數(shù)據(jù)四、源程序#include#include#includeusing namespace std;int main()srand(time(NULL);int a100,j;for(j=0;j=99;j+)aj=j+1;int k1 = rand()%100;int k2 = rand()%100;while(k1 = k2)k2 = rand()%100;cout刪除的數(shù)字為:ak1,ak2endl;ak1 = 0;ak2 = 0;sort(a, a+100);if(a99 != 100)cout100endl;if(a99 != 100 & a98 = 99)cout99endl;cout通過查找出被刪除的數(shù)字為:endl;for(int i = 0; i =100; i+)if(ai+1 - ai=3)coutai+1-1endl;coutai+1-2endl;break;else if (ai+1 - ai = 2)coutai+1-1n時，表示算法已搜索至一個葉結(jié)點，得到一個新的郵票面值設(shè)計方案x1:n。如果該方案能貼出的最大連續(xù)郵資區(qū)間大于當前已找到的最大連續(xù)郵資區(qū)間maxvalue，則更新當前最優(yōu)值maxvalue和相應(yīng)的最優(yōu)解bestx。當i=n時，當前擴展結(jié)點Z是解空間中的一個內(nèi)部結(jié)點。在該結(jié)點處x1:i-1能貼出的最大連續(xù)郵資區(qū)間為r-1。因此，在結(jié)點Z處，xi的可取值范圍是xi-1+1:r，從而，結(jié)點Z有r-xi-1個兒子結(jié)點。算法對當前擴展結(jié)點Z的每一個兒子結(jié)點，以深度優(yōu)先的方式遞歸的對相應(yīng)的子樹進行搜索。三、測試數(shù)據(jù)四、源程序#include using namespace std; class Stamp friend int MaxStamp(int ,int ,int ); private: int Bound(int i); void Backtrack(int i,int r); int n;/郵票面值數(shù)int m;/每張信封最多允許貼的郵票數(shù)int maxvalue;/當前最優(yōu)值int maxint;/大整數(shù)int maxl;/郵資上界int *x;/當前解int *y;/貼出各種郵資所需最少郵票數(shù)int *bestx;/當前最優(yōu)解; void Stamp:Backtrack(int i,int r) for(int j=0;j=xi-2*(m-1);j+) if(yjm) for(int k=1;k=m-yj;k+) if(yj+kyj+xi-1*k) yj+xi-1*k=yj+k; while(yrn) if(r-1maxvalue) maxvalue=r-1; for(int j=1;j=n;j+) bestxj=xj; return; int *z=new intmaxl+1; for(int k=1;k=maxl;k+) zk=yk; for(j=xi-1+1;j=r;j+) xi=j; Backtrack(i+1,r); for(int k=1;k=maxl;k+) yk=zk; delete z; int MaxStamp(int n,int m,int bestx) Stamp X; int maxint=32767; int maxl=1500; X.n=n; X.m=m; X.maxvalue=0; X.maxint=maxint; X.maxl=maxl; X.bestx=bestx; X.x=new int n+1; X.y=new int maxl+1; for(int i=0;i=n;i+) X.xi=0; for(i=1;i=maxl;i+) X.yi=maxint; X.x1=1;X.y0=0; X.Backtrack(2,1); cout當前最優(yōu)解:; for(i=1;i=n;i+)