算法設(shè)計與分析試驗報告

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

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

3、j,ElemTypex)intk=0,mid;/k用來計數(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("輸入想要計數(shù)的數(shù)組元素：n");scanf("%d",&x);n=count(a,0,14,x);printf("%d在數(shù)組中出現(xiàn)的次數(shù)為%d次n",x,n);實驗二動態(tài)規(guī)劃一一求解最優(yōu)問題一、實驗?zāi)康? .加深學(xué)生對動態(tài)規(guī)劃算法設(shè)計方法的基本思想、基本步驟、基本方法的理解與掌握；2 .提高學(xué)生利用課堂所學(xué)知識解決實際問題的能力；

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

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

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

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

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

12、lude"stdio.h"#include"iostream.h"#include"string.h"main()inti,j,n,a100,d=0,k=0;printf("請輸入顧客的總?cè)藬?shù)：")；scanf("%d",&n);printf("依次輸入每個顧客的服務(wù)時間：");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個人的等待時間)k=k+d;/總的等待時間)printf("此時等待的總時間為：%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此時等待的總時間為：

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

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

16、inue.六.實驗體會解n后問題主要在于可行解，一個一個的試，(t)能走通就往(t+1)下走，走不通就倒回去(t-1)換條走，再不行再回走。就要不停的嘗試，不停的回溯，直到找全可行解，或者一個也沒有就停止。還有重要的事約束條件，兩個皇后不能在同行同列或者斜線上。七.附錄(源代碼)#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