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

實(shí)驗(yàn)報(bào)告題目實(shí)驗(yàn)一 遞歸與分治策略一、 實(shí)驗(yàn)?zāi)康?1加深學(xué)生對分治法算法設(shè)計(jì)方法的基本思想、基本步驟、基本方法的理解與掌握； 2提高學(xué)生利用課堂所學(xué)知識解決實(shí)際問題的能力； 3提高學(xué)生綜合應(yīng)用所學(xué)知識解決實(shí)際問題的能力。二、 實(shí)驗(yàn)內(nèi)容設(shè)計(jì)一個(gè)遞歸和分治算法，找出數(shù)組的最大元素，找出x在數(shù)組A中出現(xiàn)的次數(shù)。三、 實(shí)驗(yàn)要求 （1）用分治法求解問題； （2）再選擇自己熟悉的其它方法求解本問題； （3）上機(jī)實(shí)現(xiàn)所設(shè)計(jì)的所有算法；四、 實(shí)驗(yàn)過程設(shè)計(jì)（算法設(shè)計(jì)過程）1. 設(shè)計(jì)一個(gè)遞歸算法，找出數(shù)組的最大元素。2. 設(shè)計(jì)一個(gè)分治算法，找出x在數(shù)組A中出現(xiàn)的次數(shù)。3. 寫一個(gè)主函數(shù)，調(diào)用上述算法。五、 實(shí)驗(yàn)結(jié)果分析（分析時(shí)空復(fù)雜性，設(shè)計(jì)測試用例及測試結(jié)果）時(shí)間復(fù)雜性：最好情況下，O(n)最壞情況下：O(nlog(n)空間復(fù)雜性分析：O(n)六、 實(shí)驗(yàn)體會 通過寫遞歸與分治策略實(shí)驗(yàn)，更加清楚的知道它的運(yùn)行機(jī)理，分治法解題的一般步驟：（1）分解，將要解決的問題劃分成若干規(guī)模較小的同類問題；（2）求解，當(dāng)子問題劃分得足夠小時(shí)，用較簡單的方法解決；（3）合并，按原問題的要求，將子問題的解逐層合并構(gòu)成原問題的解。做實(shí)驗(yàn)重在動手動腦，還是要多寫寫實(shí)驗(yàn)，才是硬道理。七、 附錄：（源代碼）#includestdio.h#define ElemType intint count(ElemType a,int i,int j,ElemType x)int k=0,mid; /k用來計(jì)數(shù)，記錄數(shù)組中x出現(xiàn)的次數(shù)if(i=j)if(ai=x) k+;return k;elsemid=(i+j)/2;k+=count(a,i,mid,x);k+=count(a,mid+1,j,x);return k;ElemType Maxitem(ElemType a,int n)ElemType max=an-1,j;if(n=1)max=an-1;return max;else j=Maxitem(a,n-1); if(jmax) max=j;return max;void main(void)ElemType a=1,5,2,7,3,7,4,8,9,5,4,544,2,4,123;ElemType b;ElemType x;int n;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)二 動態(tài)規(guī)劃求解最優(yōu)問題一、實(shí)驗(yàn)?zāi)康?加深學(xué)生對動態(tài)規(guī)劃算法設(shè)計(jì)方法的基本思想、基本步驟、基本方法的理解與掌握；2提高學(xué)生利用課堂所學(xué)知識解決實(shí)際問題的能力；3提高學(xué)生綜合應(yīng)用所學(xué)知識解決實(shí)際問題的能力。二實(shí)驗(yàn)內(nèi)容根據(jù)實(shí)驗(yàn)?zāi)康囊蠛蛯?shí)驗(yàn)條件，由學(xué)生運(yùn)用所學(xué)知識，自行選擇最優(yōu)問題，自己設(shè)計(jì)算法，自行編程實(shí)現(xiàn)、自行對實(shí)驗(yàn)結(jié)果進(jìn)行分析，自行完成實(shí)驗(yàn)項(xiàng)目報(bào)告的撰寫等。在教師的指導(dǎo)下，最大限度發(fā)揮學(xué)生資助學(xué)習(xí)的積極性，為后續(xù)專業(yè)課的學(xué)習(xí)打下堅(jiān)實(shí)基礎(chǔ)。三實(shí)驗(yàn)要求（1）用動態(tài)規(guī)劃思想求解最優(yōu)問題；（2）再選擇自己熟悉的程序設(shè)計(jì)語言實(shí)現(xiàn)所有算法；（3）分析所設(shè)計(jì)的算法的時(shí)間/空間復(fù)雜性。四實(shí)驗(yàn)過程設(shè)計(jì)（算法設(shè)計(jì)過程）實(shí)驗(yàn)3.3。先在a，b數(shù)組中選a0和b0開始，然后分別計(jì)算在以a0和b0開始的總的時(shí)間，再比較哪個(gè)最短。五實(shí)驗(yàn)結(jié)果分析六實(shí)驗(yàn)體會始終覺得用代碼寫著比用筆直接計(jì)算要難點(diǎn)，不過代碼解決的事一類問題，只需要輸數(shù)據(jù)就可以。所以還是代碼好，不過要有好的邏輯思維和方法，才能寫出好的七附錄：（源代碼）#include stdio.h#include iostream.h#include string.hvoid main()void sf(int a,int b,int n);int a100,b100,n,i;printf(請輸入需要完成的作業(yè)數(shù)量：);scanf(%d,&n);printf(請輸入A組機(jī)器完成作業(yè)對應(yīng)的時(shí)間:);for(i=0;in;i+)scanf(%d,&ai);printf(請輸入B組機(jī)器完成作業(yè)對應(yīng)的時(shí)間:);for(i=0;in;i+)scanf(%d,&bi);f(a,b,n);void f(int a,int b,int n)int max(int a,int b);int i,j,d,low,high,k,A,B,v100;for(i=0;in;i+)for(j=0;jn;j+)if(aiaj)d=ai;ai=aj;aj=d;d=bi;bi=bj;bj=d;for(i=0;in;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(bkbj)d=bk;bk=bj;bj=d;for(i=0;in;i+)A=0;B=0;j=0;while(j=i)A=A+aj;j+;while(jn)B=B+bj;j+;vi=max(A,B);i=1;d=v0;while(in)if(vib)return a;elsereturn b;實(shí)驗(yàn)三 貪心算法“0/1背包”及“有限期作業(yè)調(diào)度”一、實(shí)驗(yàn)?zāi)康?進(jìn)一步理解算法設(shè)計(jì)的基本步驟及各步的主要內(nèi)容、基本要求2加深對貪婪法算法設(shè)計(jì)方法的理解與應(yīng)用3掌握將算法轉(zhuǎn)化為計(jì)算機(jī)上機(jī)程序的方法4培養(yǎng)學(xué)生應(yīng)用所學(xué)知識解決實(shí)際問題的能力。二實(shí)驗(yàn)內(nèi)容（1）給定n種物品和一個(gè)背包。物品I的重量是wi，其價(jià)值為pi，背包的容量為M。應(yīng)如何選擇裝入背包的物品（每件物品可以全裝也可以只裝一部分），使得裝入背包中物品的總價(jià)值最大?（2）給定n個(gè)作業(yè)j1, j2, jn。對每個(gè)作業(yè)ji，有一個(gè)與之聯(lián)系的限期di0和收益pi0， di， pi均為整數(shù)，1In。對作業(yè)ji，只有在限期di內(nèi)完成，才能得到收益pi。假定只有一臺處理機(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ì)用貪婪法求解“背包問題”及“帶有限期的計(jì)算機(jī)作業(yè)調(diào)度問題”的算法；（2）上機(jī)實(shí)現(xiàn)所設(shè)計(jì)的算法；（3）分析所設(shè)計(jì)的算法的時(shí)間/空間復(fù)雜性。四實(shí)驗(yàn)過程設(shè)計(jì)（算法設(shè)計(jì)過程）后面人的等到時(shí)間等于前面人的服務(wù)時(shí)間，要總的等待時(shí)間最短，就要前面的服務(wù)時(shí)間最短，就需要先讓服務(wù)時(shí)間段的人先進(jìn)行服務(wù)。1.先按原來的順序服務(wù)時(shí)間服務(wù)，得到一個(gè)等待時(shí)間2.升序排列后，得到一個(gè)等待時(shí)間五結(jié)果分析六實(shí)驗(yàn)體會后面人的等到時(shí)間等于前面人的服務(wù)時(shí)間，要總的等待時(shí)間最短，就要前面的服務(wù)時(shí)間最短，就需要先讓服務(wù)時(shí)間段的人先進(jìn)行服務(wù)。這是總的實(shí)驗(yàn)思路。貪心算法就是要盡可能的提高效率，得到想要的效益。七附錄（源代碼）#include stdio.h#include iostream.h#include string.hmain()int i,j,n,a100,d=0,k=0;printf(請輸入顧客的總?cè)藬?shù)：);scanf(%d,&n);printf(依次輸入每個(gè)顧客的服務(wù)時(shí)間:);for(i=0;in;i+)scanf(%d,&ai);for(i=0;in;i+)d=0;for(int j=0;ji;j+)d=d+aj;/第j個(gè)人的等待時(shí)間k=k+d;/總的等待時(shí)間printf(此時(shí)等待的總時(shí)間為：%dn,k);for(i=0;in;i+)for(int j=i;jaj)d=ai;ai=aj;aj=d;printf(按升序排列后的數(shù)組為：);for(i=0;in;i+)printf(%d,ai);k=0;for(i=0;in;i+)d=0;for(int j=0;ji;j+)d=d+aj;k=k+d; printf(n此時(shí)等待的總時(shí)間為：%dn,k);實(shí)驗(yàn)四 回溯法“N皇后”問題一、實(shí)驗(yàn)?zāi)康?掌握能用回溯法求解的問題應(yīng)滿足的條件；2加深對回溯法算法設(shè)計(jì)方法的理解與應(yīng)用；3鍛煉學(xué)生對程序跟蹤調(diào)試能力；4通過本次實(shí)驗(yàn)的練習(xí)培養(yǎng)學(xué)生應(yīng)用所學(xué)知識解決實(shí)際問題的能力。二實(shí)驗(yàn)內(nèi)容由N2個(gè)方塊排成N行N列的正方形，稱為N元棋盤，在N元棋盤上放置N個(gè)皇后，如果某兩個(gè)皇后位于N元棋盤的同一行或同一列或同一斜線（斜率為1）上，則稱它們在互相攻擊，試設(shè)計(jì)算法找出使N個(gè)皇后互不攻擊的所有布局。三實(shí)驗(yàn)要求（1）用回溯法算法設(shè)計(jì)方法求解N元皇后問題（2）找出N皇后問題的互不攻擊的所有解（3）皇后數(shù)N由鍵盤動態(tài)輸入（4）上機(jī)實(shí)現(xiàn)所設(shè)計(jì)的算法；（5）分析所設(shè)計(jì)的算法的時(shí)間/空間復(fù)雜性。四實(shí)驗(yàn)過程設(shè)計(jì)（算法設(shè)計(jì)過程）（1）分析N皇后問題的約束條件，并將其顯示化，選擇存儲結(jié)構(gòu)建立相應(yīng)的數(shù)學(xué)模型；（2）根據(jù)所建立的數(shù)學(xué)模型，設(shè)計(jì)求解該問題的粗略算法；（3）對所設(shè)計(jì)的粗略算法求精，得具體算法；（4）在C/C+/VC+下實(shí)現(xiàn)所設(shè)計(jì)的算法；（5）分屏顯示結(jié)果；（6）分析運(yùn)行結(jié)果的正確性；（7）進(jìn)行算法效率分析；（8）課后寫出實(shí)驗(yàn)報(bào)告。五實(shí)驗(yàn)結(jié)果和分析六實(shí)驗(yàn)體會解n后問題主要在于可行解，一個(gè)一個(gè)的試，（t）能走通就往(t+1)下走，走不通就倒回去(t-1)換條走，再不行再回走。就要不停的嘗試，不停的回溯，直到找全可行解，或者一個(gè)也沒有就停止。還有重要的事約束條件，兩個(gè)皇后不能在同行同列或者斜線上。七附錄（源代碼）#include stdio.h#include iostream.h#include string.h#include int n; int x100;int sum=0;int k=1;int nQueen(int nn)n=nn;void backtrack(int t);for(int i=0;i=n;i+)xi=0;backtrack(1);ret