2013314209張協(xié)鎏.docx

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