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