算法設(shè)計(jì)與分析試驗(yàn)報(bào)告

1、實(shí)驗(yàn)報(bào)告題目實(shí)驗(yàn)一遞歸與分治策略一、實(shí)驗(yàn)?zāi)康? .加深學(xué)生對(duì)分治法算法設(shè)計(jì)方法的基本思想、基本步驟、基本方法的理解與掌握；2 .提高學(xué)生利用課堂所學(xué)知識(shí)解決實(shí)際問(wèn)題的能力；3 .提高學(xué)生綜合應(yīng)用所學(xué)知識(shí)解決實(shí)際問(wèn)題的能力。二、實(shí)驗(yàn)內(nèi)容設(shè)計(jì)一個(gè)遞歸和分治算法，找出數(shù)組的最大元素，找出x在數(shù)組A中出現(xiàn)的次數(shù)。三、實(shí)驗(yàn)要求(1)用分治法求解問(wèn)題；(2)再選擇自己熟悉的其它方法求解本問(wèn)題；(3)上機(jī)實(shí)現(xiàn)所設(shè)計(jì)的所有算法；四、實(shí)驗(yàn)過(guò)程設(shè)計(jì)(算法設(shè)計(jì)過(guò)程)1 .設(shè)計(jì)一個(gè)遞歸算法，找出數(shù)組的最大元素。2 .設(shè)計(jì)一個(gè)分治算法，找出x在數(shù)組A中出現(xiàn)的次數(shù)。3 .寫(xiě)一個(gè)主函數(shù)，調(diào)用上述算法。五、實(shí)驗(yàn)結(jié)果分析(分析

2、時(shí)空復(fù)雜性，設(shè)計(jì)測(cè)試用例及測(cè)試結(jié)果)時(shí)間復(fù)雜性：最好情況下，O(n)最壞情況下：O(nlog(n)空間復(fù)雜性分析：O(n)六、實(shí)驗(yàn)體會(huì)通過(guò)寫(xiě)遞歸與分治策略實(shí)驗(yàn)，更加清楚的知道它的運(yùn)行機(jī)理，分治法解題的一般步驟：(1)分解，將要解決的問(wèn)題劃分成若干規(guī)模較小的同類問(wèn)題；(2)求解，當(dāng)子問(wèn)題劃分得足夠小時(shí)，用較簡(jiǎn)單的方法解決；(3)合并，按原問(wèn)題的要求，將子問(wèn)題的解逐層合并構(gòu)成原問(wèn)題的解。做實(shí)驗(yàn)重在動(dòng)手動(dòng)腦，還是要多寫(xiě)寫(xiě)實(shí)驗(yàn)，才是硬道理。七、附錄：(源代碼)#include"stdio.h"#defineElemTypeintintcount(ElemTypea,inti,int

3、j,ElemTypex)intk=0,mid;/k用來(lái)計(jì)數(shù)，記錄數(shù)組中x出現(xiàn)的次數(shù)if(i=j)if(ai=x)k+;returnk;elsemid=(i+j)/2;k+=count(a,i,mid,x);k+=count(a,mid+1,j,x);returnk;ElemTypeMaxitem(ElemTypea,intn)ElemTypemax=an-1,j;if(n=1)max=an-1;returnmax;elsej=Maxitem(a,n-1);if(j>max)max=j;returnmax;)voidmain(void)(ElemTypea=1,5,2,7,3,7,4,8,

4、9,5,4,544,2,4,123;ElemTypeb;ElemTypex;intn;b=Maxitem(a,15);printf("數(shù)組的最大元素為dn",b);printf("輸入想要計(jì)數(shù)的數(shù)組元素：n");scanf("%d",&x);n=count(a,0,14,x);printf("%d在數(shù)組中出現(xiàn)的次數(shù)為%d次n",x,n);實(shí)驗(yàn)二動(dòng)態(tài)規(guī)劃一一求解最優(yōu)問(wèn)題一、實(shí)驗(yàn)?zāi)康? .加深學(xué)生對(duì)動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)方法的基本思想、基本步驟、基本方法的理解與掌握；2 .提高學(xué)生利用課堂所學(xué)知識(shí)解決實(shí)際問(wèn)題的能力；

5、3 .提高學(xué)生綜合應(yīng)用所學(xué)知識(shí)解決實(shí)際問(wèn)題的能力。二.實(shí)驗(yàn)內(nèi)容根據(jù)實(shí)驗(yàn)?zāi)康囊蠛蛯?shí)驗(yàn)條件，由學(xué)生運(yùn)用所學(xué)知識(shí)，自行選擇最優(yōu)問(wèn)題，自己設(shè)計(jì)算法，自行編程實(shí)現(xiàn)、自行對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，自行完成實(shí)驗(yàn)項(xiàng)目報(bào)告的撰寫(xiě)等。在教師的指導(dǎo)下，最大限度發(fā)揮學(xué)生資助學(xué)習(xí)的積極性，為后續(xù)專業(yè)課的學(xué)習(xí)打下堅(jiān)實(shí)基礎(chǔ)。三.實(shí)驗(yàn)要求(1)用動(dòng)態(tài)規(guī)劃思想求解最優(yōu)問(wèn)題;(2)再選擇自己熟悉的程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)所有算法;(3)分析所設(shè)計(jì)的算法的時(shí)間/空間復(fù)雜性。四.實(shí)驗(yàn)過(guò)程設(shè)計(jì)(算法設(shè)計(jì)過(guò)程)實(shí)驗(yàn)3.3。先在a,b數(shù)組中選a0和b0開(kāi)始，然后分別計(jì)算在以a0和b0開(kāi)始的總的時(shí)間，再比較哪個(gè)最短。五.實(shí)驗(yàn)結(jié)果分析六.實(shí)驗(yàn)體會(huì)始終覺(jué)得

6、用代碼寫(xiě)著比用筆直接計(jì)算要難點(diǎn)，不過(guò)代碼解決的事一類問(wèn)題，只需要輸數(shù)據(jù)就可以。所以還是代碼好，不過(guò)要有好的邏輯思維和方法，才能寫(xiě)出好的七.附錄：(源代碼)#include"stdio.h"#include"iostream.h"#include"string.h"voidmain()voidsf(inta,intb,intn);inta100,b100,n,i;printf("請(qǐng)輸入需要完成的作業(yè)數(shù)量：");scanf("%d",&n);printf("請(qǐng)輸入A組機(jī)器完成作業(yè)對(duì)

7、應(yīng)的時(shí)間：");for(i=0;i<n;i+)scanf("%d",&ai);printf("請(qǐng)輸入B組機(jī)器完成作業(yè)對(duì)應(yīng)的時(shí)間：");for(i=0;i<n;i+)scanf("%d",&bi);f(a,b,n);voidf(inta,intb,intn)intmax(inta,intb);inti,j,d,low,high,k,A,B,v100;for(i=0;i<n;i+)for(j=0;j<n;j+)if(ai<aj)d=ai;ai=aj;aj=d;d=bi;bi=bj;b

8、j=d;for(i=0;i<n;i+)low=i;high=i;while(ai=ai+1)i+;high=i;if(low!=high)for(k=low;k<=high;k+)for(j=k;j<=high;j+)if(bk<bj)d=bk;bk=bj;bj=d;)for(i=0;i<n;i+)(A=0;B=0;j=0;while(j<=i)(A=A+aj;j+;)while(j<n)(B=B+bj;j+;)vi=max(A,B);)i=1;d=v0;while(i<n)(if(vi<d)(d=vi;)i+;)printf("

9、最短作業(yè)時(shí)間為:%dn",d);)intmax(inta,intb)(if(a>b)(returna;)elsereturnb;實(shí)驗(yàn)三貪心算法一一“0/1背包”及“有限期作業(yè)調(diào)度”一、實(shí)驗(yàn)?zāi)康? .進(jìn)一步理解算法設(shè)計(jì)的基本步驟及各步的主要內(nèi)容、基本要求2 .加深對(duì)貪婪法算法設(shè)計(jì)方法的理解與應(yīng)用3 .掌握將算法轉(zhuǎn)化為計(jì)算機(jī)上機(jī)程序的方法4 .培養(yǎng)學(xué)生應(yīng)用所學(xué)知識(shí)解決實(shí)際問(wèn)題的能力。二.實(shí)驗(yàn)內(nèi)容(1)給定n種物品和一個(gè)背包。物品I的重量是w"其價(jià)值為pi,背包的容量為M。應(yīng)如何選擇裝入背包的物品(每件物品可以全裝也可以只裝一部分)，使得裝入背包中物品的總價(jià)值最大？(2)給

10、定n個(gè)作業(yè)j1,j2，jn。對(duì)每個(gè)作業(yè)ji，有一個(gè)與之聯(lián)系的限期dj>0和收益Pi>0,dj,pi均為整數(shù)，1&I&n。對(duì)作業(yè)ji，只有在限期di內(nèi)完成，才能得到收益Pi。假定只有一臺(tái)處理機(jī)為這批服務(wù)業(yè)服務(wù)，處理機(jī)每次只能處理一個(gè)作業(yè)，并且完成一作業(yè)需一個(gè)單位時(shí)間。所謂一個(gè)可行解，是這批作業(yè)的一個(gè)子集J,J中每一作業(yè)均能在限期di內(nèi)完成。調(diào)度的總收益是子集J中各作業(yè)收益之和。具有最大收益的的可行解和為最優(yōu)解。如何求其最優(yōu)解？三.實(shí)驗(yàn)要求(1)設(shè)計(jì)用貪婪法求解“背包問(wèn)題”及“帶有限期的計(jì)算機(jī)作業(yè)調(diào)度問(wèn)題”的算法；(2)上機(jī)實(shí)現(xiàn)所設(shè)計(jì)的算法；（3）分析所設(shè)計(jì)的算法的時(shí)間

11、/空間復(fù)雜性。四.實(shí)驗(yàn)過(guò)程設(shè)計(jì)（算法設(shè)計(jì)過(guò)程）后面人的等到時(shí)間等于前面人的服務(wù)時(shí)間，要總的等待時(shí)間最短，就要前面的服務(wù)時(shí)間最短，就需要先讓服務(wù)時(shí)間段的人先進(jìn)行服務(wù)。1 .先按原來(lái)的順序服務(wù)時(shí)間服務(wù)，得到一個(gè)等待時(shí)間2 .升序排列后，得到一個(gè)等待時(shí)間五.結(jié)果分析*工:存習(xí)歸尊機(jī).作蛆整法mbugM法，w的昌后昌ke士毫列的yanXi擘IW¥2026064/?:5s2旬六.實(shí)驗(yàn)體會(huì)后面人的等到時(shí)間等于前面人的服務(wù)時(shí)間，要總的等待時(shí)間最短，就要前面的服務(wù)時(shí)間最短，就需要先讓服務(wù)時(shí)間段的人先進(jìn)行服務(wù)。這是總的實(shí)驗(yàn)思路。貪心算法就是要盡可能的提高效率，得到想要的效益。七.附錄（源代碼）#inc

12、lude"stdio.h"#include"iostream.h"#include"string.h"main()inti,j,n,a100,d=0,k=0;printf("請(qǐng)輸入顧客的總?cè)藬?shù)：")；scanf("%d",&n);printf("依次輸入每個(gè)顧客的服務(wù)時(shí)間：");for(i=0;i<n;i+)scanf("%d",&ai);for(i=0;i<n;i+)(d=0;for(intj=0；j<i；j+)(d=d

13、+aj;/第j個(gè)人的等待時(shí)間)k=k+d;/總的等待時(shí)間)printf("此時(shí)等待的總時(shí)間為：%dn",k);for(i=0;i<n;i+)(for(intj=i;j<n;j+)(if(ai>aj)(d=ai;ai=aj;aj=d;)printf("按升序排列后的數(shù)組為：");for(i=0;i<n;i+)printf("%d",ai);k=0;for(i=0;i<n;i+)(d=0;for(intj=0;j<i;j+)(d=d+aj;)k=k+d;)printf("n此時(shí)等待的總時(shí)間為：

14、%dn",k);)實(shí)驗(yàn)四回溯法一一“N皇后”問(wèn)題一、實(shí)驗(yàn)?zāi)康? .掌握能用回溯法求解的問(wèn)題應(yīng)滿足的條件；2 .加深對(duì)回溯法算法設(shè)計(jì)方法的理解與應(yīng)用；3 .鍛煉學(xué)生對(duì)程序跟蹤調(diào)試能力；4 .通過(guò)本次實(shí)驗(yàn)的練習(xí)培養(yǎng)學(xué)生應(yīng)用所學(xué)知識(shí)解決實(shí)際問(wèn)題的能力。2 .實(shí)驗(yàn)內(nèi)容由N2個(gè)方塊排成N行N列的正方形，稱為N元棋盤(pán)，在N元棋盤(pán)上放置N個(gè)皇后，如果某兩個(gè)皇后位于N元棋盤(pán)的同一行或同一列或同一斜線(斜率為土)上，則稱它們?cè)诨ハ喙?，試設(shè)計(jì)算法找出使N個(gè)皇后互不攻擊的所有布局。3 .實(shí)驗(yàn)要求(1)用回溯法算法設(shè)計(jì)方法求解N元皇后問(wèn)題(2)找出N皇后問(wèn)題的互不攻擊的所有解(3)皇后數(shù)N由鍵盤(pán)動(dòng)態(tài)輸入(

15、4)上機(jī)實(shí)現(xiàn)所設(shè)計(jì)的算法；(5)分析所設(shè)計(jì)的算法的時(shí)間/空間復(fù)雜性。四.實(shí)驗(yàn)過(guò)程設(shè)計(jì)(算法設(shè)計(jì)過(guò)程)(1)分析N皇后問(wèn)題的約束條件，并將其顯示化，選擇存儲(chǔ)結(jié)構(gòu)建立相應(yīng)的數(shù)學(xué)模型；(2)根據(jù)所建立的數(shù)學(xué)模型，設(shè)計(jì)求解該問(wèn)題的粗略算法；(3)對(duì)所設(shè)計(jì)的粗略算法求精，得具體算法；(4)在C/C+/VC+下實(shí)現(xiàn)所設(shè)計(jì)的算法；(5)分屏顯示結(jié)果；(6)分析運(yùn)行結(jié)果的正確性；(7)進(jìn)行算法效率分析；(8)課后寫(xiě)出實(shí)驗(yàn)報(bào)告。五.實(shí)驗(yàn)結(jié)果和分析'學(xué)習(xí)V十菖機(jī)作業(yè)、售法Debug，肖去cxe"輸入n皇后n值士44燈向yjdu&hn孕車aAs-L12e第第咋為為t24133142cont

16、inue.六.實(shí)驗(yàn)體會(huì)解n后問(wèn)題主要在于可行解，一個(gè)一個(gè)的試，(t)能走通就往(t+1)下走，走不通就倒回去(t-1)換條走，再不行再回走。就要不停的嘗試，不停的回溯，直到找全可行解，或者一個(gè)也沒(méi)有就停止。還有重要的事約束條件，兩個(gè)皇后不能在同行同列或者斜線上。七.附錄(源代碼)#include"stdio.h"#include"iostream.h"#include"string.h"#include<cmath>intn;intx100;intsum=0;intk=1;intnQueen(intnn)n=nn;voidbacktrack(intt);for(inti=0;i<=n;i+)xi=0;backtrack(1);returnsum;intplace(intk)for(intj=1;j<k;j+)(if(abs(k-j)=abs(xj-xk)|(xj=xk)(return0;return1;voidbacktrack(intt)(i