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

試驗一遞歸與分治策略一、試驗?zāi)康募由顚W(xué)生對分治法算法設(shè)計方法的根本思想、根本步驟、根本方法的理解與把握；提高學(xué)生利用課堂所學(xué)學(xué)問解決實際問題的力量；提高學(xué)生綜合應(yīng)用所學(xué)學(xué)問解決實際問題的力量。二、試驗內(nèi)容1、a[0:n-1]是已排好序的數(shù)組。請寫二分搜尋算法，使得當搜尋元素x不在數(shù)組中時，返回小于x的最大元素位置i和大于x的最小元素位置jj一樣，x在數(shù)組中的位置。②寫出三分搜尋法的程序。三、試驗要求用分治法求解上面兩個問題；再選擇自己生疏的其它方法求解本問題；上機實現(xiàn)所設(shè)計的全部算法；四、試驗過程設(shè)計〔算法設(shè)計過程〕1、a[0:n-1]是一個已排好序的數(shù)組，可以承受折半查找〔二分查找〕算法。假設(shè)搜尋元x與通過二分查找所得最終元素的大小，留意邊界條件，從而計算出小于x的最大元素的位置i和大于x的最小元素位置j。2、將n個元素分成大致一樣的三局部，取在數(shù)組ax。假設(shè)x>a[2(n-1)/3]，則只需在數(shù)組a的右三分之一局部中連續(xù)搜尋x。上述兩種狀況不成立時，則在數(shù)組中間的三分之一局部中連續(xù)搜尋x。五、試驗結(jié)果分析二分搜尋法：時間簡單性：時間簡單性：二分搜尋每次把搜尋區(qū)域砍掉一半，很明顯時間簡單度為O(logn)?！瞡代表集合中元素的個數(shù)〕三分搜尋法：O〔3log3n〕空間簡單度：O〔1〕。六、試驗體會看是不夠的還要動手分析一下，這樣才能學(xué)好算法。〔源代碼二分搜尋法：#include<iostream.h>#include<stdio.h>intbinarySearch(inta[],intx,intn){intleft=0;intright=n-1;inti,j;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle]){i=j=middle;return1;}if(x>a[middle])left=middle+1;elseright=middle-1;}i=right;j=left;return0;}intmain{ inta[10]={0,1,2,3,4,5,6,7,8,9};intn=10;intx=9;if(binarySearch(a,x,n))cout<<“找到“<<endl;elsecout<<“找不到“<<endl;return0;}試驗二動態(tài)規(guī)劃——求解最優(yōu)問題一、試驗?zāi)康募由顚W(xué)生對動態(tài)規(guī)劃算法設(shè)計方法的根本思想、根本步驟、根本方法的理解與把握；提高學(xué)生利用課堂所學(xué)學(xué)問解決實際問題的力量；提高學(xué)生綜合應(yīng)用所學(xué)學(xué)問解決實際問題的力量。二、試驗內(nèi)容1ABniAa[i]，假設(shè)由機器Bb[i]。由于各作業(yè)的特點和機器的性能關(guān)系，很可能對于某些ia[i]>=b[ij，j!=ia[i]<b[j]。既不能將一個作業(yè)分2兩臺機器處理完這n〔從任何一臺機器開工到最終一臺機器停工的總的時間〕。爭論一個實例:〔a[1],a[2],a[3],a[4],a[5],a[6]〕=(2,5,7,10,5,2);(b[1],b[2],b[3],b[4],b[5],b[6])=(3,8,4,11,3,4)。2、長江游艇俱樂部在長江上設(shè)置了n個游艇出租站1，2??n。游客可在游艇出租站租用i到游艇出租站j之間的租金r〔i，j〕1<=i<j<=n。設(shè)計一個算法，計算出游艇1到游艇n三、試驗要求用動態(tài)規(guī)劃思想求解最優(yōu)問題；再選擇自己生疏的程序設(shè)計語言實現(xiàn)全部算法；分析所設(shè)計的算法的時間/空間簡單性。四、試驗過程設(shè)計〔算法設(shè)計過程〕1、對于給定的2臺處理機AB處理n個作業(yè)，找出一個最優(yōu)調(diào)度方案，使2臺機器處理n個作業(yè)的時間最短。2、對于給定的游艇出租站i到游艇出租站j之間的租金為〔，，1<=i<j<=1n五、試驗結(jié)果分析獨立任務(wù)最優(yōu)調(diào)度問題：租用游艇問題：時間簡單性：獨立任務(wù)最優(yōu)調(diào)度問題：O(n*Sum)六、試驗體會算法才是上上之策。〔源代碼〕獨立任務(wù)最優(yōu)調(diào)度問題：usingSystem;namespacezydd{classProgram{staticvoidDlrwZydd(int[]a,int[]b,intn,int[]least,string[]result){for(inti=0;i<n;i++){least[i]=99;}intaSum=0,bSum=0;for(inti=0;i<n;i++){aSum+=a[i];bSum+=b[i];}intSum=1+Math.Min(aSum,bSum);int[,]timeA=newint[n,Sum];int[,]timeB=newint[n,Sum];int[,]timeMax=newint[n,Sum];char[,]who=newchar[n,Sum];char[]tempRlt=newchar[n];for(inti=0;i<=a[0];i++){timeA[0,i]=i;if(i<a[0]){

}else{}

timeB[0,i]=b[0];who[0,i]=”b”;timeB[0,i]=0;who[0,i]=”a”;timeMax[0,i]=Math.Max(timeA[0,i],timeB[0,i]);}if(a[0]<=b[0]){}else{}

least[0]=a[0];tempRlt[0]=”a”;least[0]=b[0];tempRlt[0]=”b”;result[0]=newString(tempRlt);for(intk=1;k<n;k++){inttempSum=0;for(inttemp=0;temp<=k;temp++){tempSum+=a[temp];}for(inti=0;i<=tempSum;i++){ timeA[k,i]=i;if(i<a[k]){timeB[k,i]=timeB[k-1,i]+b[k];who[k,i]=”b”;}else{if((timeB[k-1,i]+b[k])<=timeB[k-1,i-a[k]]){}else{}}

timeB[k,i]=timeB[k-1,i]+b[k];who[k,i]=”b”;timeB[k,i]=timeB[k-1,i-a[k]];who[k,i]=”a”;timeMax[k,i]=Math.Max(timeA[k,i],timeB[k,i]);}for(inti=tempSum+1;i<aSum;i++){timeA[k,i]=tempSum;timeB[k,i]=0;}intflag=0;for(inti=0;i<=tempSum;i++){if(timeMax[k,i]>0&&timeMax[k,i]<least[k]){least[k]=timeMax[k,i];flag=i;}}tempRlt[k]=who[k,flag];for(inti=k;i>0&&flag>0;i--){if(tempRlt[i]==”a”){flag-=a[i];tempRlt[i-1]=who[i-1,flag];}if(tempRlt[i]==”b”){tempRlt[i-1]=who[i-1,flag];}}result[k]=newString(tempRlt);}}staticvoidMain(string[]args){constintN=6;int[]a=newint[N]{2,5,7,10,5,2};int[]b=newint[N]{3,8,4,11,3,4};int[]least=newint[N];string[]result=newstring[N];DlrwZydd(a,b,N,least,result);Console.WriteLine;for(inti=0;i<N;i++){Console.WriteLine(“按要求完成前{0}項任務(wù)的機器挨次為：“+result[i]+“時間為：{1}“,i+1,least[i]);}}}}試驗三貪心算法一、試驗?zāi)康倪M一步理解算法設(shè)計的根本步驟及各步的主要內(nèi)容、根本要求加深對貪欲法算法設(shè)計方法的理解與應(yīng)用把握將算法轉(zhuǎn)化為計算機上機程序的方法培育學(xué)生應(yīng)用所學(xué)學(xué)問解決實際問題的力量。二、試驗內(nèi)容1n個顧客同時等待一項效勞。顧客i需要的效勞時間為ti，1<=i<=nn個顧客的效勞次序才能使總的等待時間到達最??？總的等待時間是每個顧客等待效勞時間的綜合。2、一輛汽車加滿油后可行駛n公里。旅途中有假設(shè)干個加油站。設(shè)計一個有效算法，之處應(yīng)在哪些加油站?？考佑停寡赝炯佑痛螖?shù)最少。并證明算法能產(chǎn)生一個最優(yōu)解。三、試驗要求設(shè)計用貪欲法求解“最優(yōu)效勞次序問題”及“汽車加油問題”的算法；上機實現(xiàn)所設(shè)計的算法；分析所設(shè)計的算法的時間/空間簡單性。四、試驗過程設(shè)計〔算法設(shè)計過程〕12st[]是效勞數(shù)組，st[j]為第jsu[]是求和數(shù)組，su[jj上全部顧客的等待時間；2、設(shè)加油次數(shù)為k，每個加油站間距離為a[i]；i=0，1，2，3??n始點到終點的距離小于Ｎ，則加油次數(shù)k=0；始點到終點的距離大于N，①加油站間的距離相等，即ａ[i]=a[j]=L=Nk=n；②加油站間的距離相等，即ａ[i]=a[j]=L>N，則不行能到達終點；③加油站間的距離相等，即ａ[i]=a[j]=L<N，則加油次數(shù)k=n/N(n%N==0)k=[n/N]+1(n%N！=0)；④加油站間的距離不相等，即ａ[i]！=a[jk五、試驗結(jié)果分析最優(yōu)效勞次序問題：時間簡單度為O(nlogn)汽車加油問題：時間簡單度為O(n)。六、試驗體會〔源代碼汽車加油問題：#include<iostream.h>#include<stdio.h>namespaceConsoleApplication1{classProgram{staticvoidMain(string[]args){Console.Write(“請輸入汽車加滿油后可行駛路程：“);intn=Convert.ToInt32(Console.ReadLine);Console.Write(“請輸入途經(jīng)加油站總數(shù)：“);intk=Convert.ToInt32(Console.ReadLine);int[]distance=newint[k+1];//加油站間距int[]note=newint[k];//記錄加油站點Console.WriteLine(“請輸入加油站間距！“);for(inti=0;i<=k;i++){//從始點起，加油站間距Console.Write(“站點間距{0}: “,i+1);distance[i]=Convert.ToInt32(Console.ReadLine);}intcount;//記錄加油次數(shù)Problemp=newProblem;count=p.Greedy(distance,note,n);if(count>=0){if(count==0)Console.WriteLine(“汽車不用加油就可到達終點！“);else{Console.WriteLine(“汽車在旅途中需加{0}次油！“,count);Console.WriteLine(“分別在以下加油站加了油：“);for(inti=0;i<note.Length;i++){if(note[i]!=0){//輸出需加油站點Console.WriteLine(“第“+note[i]+“個加油站！“);}}}}elseConsole.WriteLine(“汽車無法到達終點！“);Console.ReadKey;}}classProblem{publicintGreedy(int[]d,int[]note,intn){inti,j,s,add=0,p=0,k=d.Length;for(i=0;i<k;i++){if(d[i]>n){//不能到達目的地return-1;}}for(j=0,s=0;j<k;j++){s+=d[j];if(s>n){//需要加油add++;note[p++]=j;s=d[j];}}returnadd;}}}試驗四回溯法一、試驗?zāi)康?．把握能用回溯法求解的問題應(yīng)滿足的條件；加深對回溯法算法設(shè)計方法的理解與應(yīng)用；熬煉學(xué)生對程序跟蹤調(diào)試力量；通過本次試驗的練習(xí)培育學(xué)生應(yīng)用所學(xué)學(xué)問解決實際問題的力量。二、試驗內(nèi)容1、設(shè)某一機器由n個部件組成，每一種部件都可以從m個不同的供給商處購得。設(shè)w[i][j]是從供給商j處購得的部件i的重量，c[i][j]是相應(yīng)的價格。試設(shè)計一個算法，給出總價格不c的最小重量機器設(shè)計。2、nnijc[i][j]。試設(shè)計一個算法，為每1件不同的工作，并使總費用到達最小。三、試驗要求用回溯法算法設(shè)計方法求解最小重量機器設(shè)計問題和工作安排問題；上機實現(xiàn)所設(shè)計的算法；分析所設(shè)計的算法的時間/空間簡單性。四、試驗過程設(shè)計〔算法設(shè)計過程〕1、a.部件有n個，供給商有m個，分別用w[i][j]c[i][j]存儲從供給商j處購得的部件i的重量和相應(yīng)價格，d為總價格的上限。b.用遞歸函數(shù)backtrack(i)來實現(xiàn)回溯法搜尋排列樹〔形式參數(shù)i表示遞歸深度。cp>d，則為不行行解，剪去相應(yīng)子樹，返回到i-1層連續(xù)執(zhí)行。cw>=sum，則不是最優(yōu)解，剪去相應(yīng)子樹，返回到i-1層連續(xù)執(zhí)行。i>nsumi-1層連續(xù)執(zhí)行；④用for循環(huán)對部件i從m(1≤jmc.主函數(shù)調(diào)用一次Knapsack(1)sum即為所求最小總重量。2、a.c[i][j]存儲將工作i安排給第j個人所需的費用，用v[j]j個人是否已安排工作；b.用遞歸函數(shù)backtrack〔i，total〕來實現(xiàn)回溯法搜尋排列樹〔形式參數(shù)i表示遞歸深n用來掌握遞歸深度，形式參數(shù)totals表示當前最優(yōu)總費用：total>=s，則不是最優(yōu)解，剪去相應(yīng)子樹，返回到i-1層連續(xù)執(zhí)行；②假設(shè)i>n，則算法搜尋到一個葉結(jié)點，用s對最優(yōu)解進展記錄，返回到i-1層連續(xù)執(zhí)行；③承受for循環(huán)針對n個人對工作i進展安排≤：1>v[j]==1，則第j個人已安排了工作，找第j+1個人進展安排；2>假設(shè)v[j]==i安排給第j〔即v[j]=1對工作i+1調(diào)用遞歸函數(shù)backtrack〔i+1，total+c[i][j]〕連續(xù)進展安排；3>backtrack〔i+1，total+c[i][j]〕調(diào)用完畢后則返回v[j]=0，將工作i對j+1個人進展安排；4>j>n時，for循環(huán)完畢；i=1時