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

試驗(yàn)一遞歸與分治策略一、試驗(yàn)?zāi)康募由顚W(xué)生對分治法算法設(shè)計(jì)方法的根本思想、根本步驟、根本方法的理解與把握；提高學(xué)生利用課堂所學(xué)學(xué)問解決實(shí)際問題的力量；提高學(xué)生綜合應(yīng)用所學(xué)學(xué)問解決實(shí)際問題的力量。二、試驗(yàn)內(nèi)容1、a[0:n-1]是已排好序的數(shù)組。請寫二分搜尋算法，使得當(dāng)搜尋元素x不在數(shù)組中時(shí)，返回小于x的最大元素位置i和大于x的最小元素位置jj一樣，x在數(shù)組中的位置。②寫出三分搜尋法的程序。三、試驗(yàn)要求用分治法求解上面兩個(gè)問題；再選擇自己生疏的其它方法求解本問題；上機(jī)實(shí)現(xiàn)所設(shè)計(jì)的全部算法；四、試驗(yàn)過程設(shè)計(jì)〔算法設(shè)計(jì)過程〕1、a[0:n-1]是一個(gè)已排好序的數(shù)組，可以承受折半查找〔二分查找〕算法。假設(shè)搜尋元x與通過二分查找所得最終元素的大小，留意邊界條件，從而計(jì)算出小于x的最大元素的位置i和大于x的最小元素位置j。2、將n個(gè)元素分成大致一樣的三局部，取在數(shù)組ax。假設(shè)x>a[2(n-1)/3]，則只需在數(shù)組a的右三分之一局部中連續(xù)搜尋x。上述兩種狀況不成立時(shí)，則在數(shù)組中間的三分之一局部中連續(xù)搜尋x。五、試驗(yàn)結(jié)果分析二分搜尋法：時(shí)間簡單性：時(shí)間簡單性：二分搜尋每次把搜尋區(qū)域砍掉一半，很明顯時(shí)間簡單度為O(logn)?！瞡代表集合中元素的個(gè)數(shù)〕三分搜尋法：O〔3log3n〕空間簡單度：O〔1〕。六、試驗(yàn)體會看是不夠的還要動手分析一下，這樣才能學(xué)好算法?！苍创a二分搜尋法：#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;}試驗(yàn)二動態(tài)規(guī)劃——求解最優(yōu)問題一、試驗(yàn)?zāi)康募由顚W(xué)生對動態(tài)規(guī)劃算法設(shè)計(jì)方法的根本思想、根本步驟、根本方法的理解與把握；提高學(xué)生利用課堂所學(xué)學(xué)問解決實(shí)際問題的力量；提高學(xué)生綜合應(yīng)用所學(xué)學(xué)問解決實(shí)際問題的力量。二、試驗(yàn)內(nèi)容1ABniAa[i]，假設(shè)由機(jī)器Bb[i]。由于各作業(yè)的特點(diǎn)和機(jī)器的性能關(guān)系，很可能對于某些ia[i]>=b[ij，j!=ia[i]<b[j]。既不能將一個(gè)作業(yè)分2兩臺機(jī)器處理完這n〔從任何一臺機(jī)器開工到最終一臺機(jī)器停工的總的時(shí)間〕。爭論一個(gè)實(shí)例:〔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個(gè)游艇出租站1，2??n。游客可在游艇出租站租用i到游艇出租站j之間的租金r〔i，j〕1<=i<j<=n。設(shè)計(jì)一個(gè)算法，計(jì)算出游艇1到游艇n三、試驗(yàn)要求用動態(tài)規(guī)劃思想求解最優(yōu)問題；再選擇自己生疏的程序設(shè)計(jì)語言實(shí)現(xiàn)全部算法；分析所設(shè)計(jì)的算法的時(shí)間/空間簡單性。四、試驗(yàn)過程設(shè)計(jì)〔算法設(shè)計(jì)過程〕1、對于給定的2臺處理機(jī)AB處理n個(gè)作業(yè)，找出一個(gè)最優(yōu)調(diào)度方案，使2臺機(jī)器處理n個(gè)作業(yè)的時(shí)間最短。2、對于給定的游艇出租站i到游艇出租站j之間的租金為〔，，1<=i<j<=1n五、試驗(yàn)結(jié)果分析獨(dú)立任務(wù)最優(yōu)調(diào)度問題：租用游艇問題：時(shí)間簡單性：獨(dú)立任務(wù)最優(yōu)調(diào)度問題：O(n*Sum)六、試驗(yàn)體會算法才是上上之策。〔源代碼〕獨(dú)立任務(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}項(xiàng)任務(wù)的機(jī)器挨次為：“+result[i]+“時(shí)間為：{1}“,i+1,least[i]);}}}}試驗(yàn)三貪心算法一、試驗(yàn)?zāi)康倪M(jìn)一步理解算法設(shè)計(jì)的根本步驟及各步的主要內(nèi)容、根本要求加深對貪欲法算法設(shè)計(jì)方法的理解與應(yīng)用把握將算法轉(zhuǎn)化為計(jì)算機(jī)上機(jī)程序的方法培育學(xué)生應(yīng)用所學(xué)學(xué)問解決實(shí)際問題的力量。二、試驗(yàn)內(nèi)容1n個(gè)顧客同時(shí)等待一項(xiàng)效勞。顧客i需要的效勞時(shí)間為ti，1<=i<=nn個(gè)顧客的效勞次序才能使總的等待時(shí)間到達(dá)最小？總的等待時(shí)間是每個(gè)顧客等待效勞時(shí)間的綜合。2、一輛汽車加滿油后可行駛n公里。旅途中有假設(shè)干個(gè)加油站。設(shè)計(jì)一個(gè)有效算法，之處應(yīng)在哪些加油站?？考佑?，使沿途加油次數(shù)最少。并證明算法能產(chǎn)生一個(gè)最優(yōu)解。三、試驗(yàn)要求設(shè)計(jì)用貪欲法求解“最優(yōu)效勞次序問題”及“汽車加油問題”的算法；上機(jī)實(shí)現(xiàn)所設(shè)計(jì)的算法；分析所設(shè)計(jì)的算法的時(shí)間/空間簡單性。四、試驗(yàn)過程設(shè)計(jì)〔算法設(shè)計(jì)過程〕12st[]是效勞數(shù)組，st[j]為第jsu[]是求和數(shù)組，su[jj上全部顧客的等待時(shí)間；2、設(shè)加油次數(shù)為k，每個(gè)加油站間距離為a[i]；i=0，1，2，3??n始點(diǎn)到終點(diǎn)的距離小于Ｎ，則加油次數(shù)k=0；始點(diǎn)到終點(diǎn)的距離大于N，①加油站間的距離相等，即ａ[i]=a[j]=L=Nk=n；②加油站間的距離相等，即ａ[i]=a[j]=L>N，則不行能到達(dá)終點(diǎn)；③加油站間的距離相等，即ａ[i]=a[j]=L<N，則加油次數(shù)k=n/N(n%N==0)k=[n/N]+1(n%N！=0)；④加油站間的距離不相等，即ａ[i]！=a[jk五、試驗(yàn)結(jié)果分析最優(yōu)效勞次序問題：時(shí)間簡單度為O(nlogn)汽車加油問題：時(shí)間簡單度為O(n)。六、試驗(yà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];//記錄加油站點(diǎn)Console.WriteLine(“請輸入加油站間距！“);for(inti=0;i<=k;i++){//從始點(diǎn)起，加油站間距Console.Write(“站點(diǎn)間距{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(“汽車不用加油就可到達(dá)終點(diǎn)！“);else{Console.WriteLine(“汽車在旅途中需加{0}次油！“,count);Console.WriteLine(“分別在以下加油站加了油：“);for(inti=0;i<note.Length;i++){if(note[i]!=0){//輸出需加油站點(diǎn)Console.WriteLine(“第“+note[i]+“個(gè)加油站！“);}}}}elseConsole.WriteLine(“汽車無法到達(dá)終點(diǎn)！“);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){//不能到達(dá)目的地return-1;}}for(j=0,s=0;j<k;j++){s+=d[j];if(s>n){//需要加油add++;note[p++]=j;s=d[j];}}returnadd;}}}試驗(yàn)四回溯法一、試驗(yàn)?zāi)康?．把握能用回溯法求解的問題應(yīng)滿足的條件；加深對回溯法算法設(shè)計(jì)方法的理解與應(yīng)用；熬煉學(xué)生對程序跟蹤調(diào)試力量；通過本次試驗(yàn)的練習(xí)培育學(xué)生應(yīng)用所學(xué)學(xué)問解決實(shí)際問題的力量。二、試驗(yàn)內(nèi)容1、設(shè)某一機(jī)器由n個(gè)部件組成，每一種部件都可以從m個(gè)不同的供給商處購得。設(shè)w[i][j]是從供給商j處購得的部件i的重量，c[i][j]是相應(yīng)的價(jià)格。試設(shè)計(jì)一個(gè)算法，給出總價(jià)格不c的最小重量機(jī)器設(shè)計(jì)。2、nnijc[i][j]。試設(shè)計(jì)一個(gè)算法，為每1件不同的工作，并使總費(fèi)用到達(dá)最小。三、試驗(yàn)要求用回溯法算法設(shè)計(jì)方法求解最小重量機(jī)器設(shè)計(jì)問題和工作安排問題；上機(jī)實(shí)現(xiàn)所設(shè)計(jì)的算法；分析所設(shè)計(jì)的算法的時(shí)間/空間簡單性。四、試驗(yàn)過程設(shè)計(jì)〔算法設(shè)計(jì)過程〕1、a.部件有n個(gè)，供給商有m個(gè)，分別用w[i][j]c[i][j]存儲從供給商j處購得的部件i的重量和相應(yīng)價(jià)格，d為總價(jià)格的上限。b.用遞歸函數(shù)backtrack(i)來實(shí)現(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個(gè)人所需的費(fèi)用，用v[j]j個(gè)人是否已安排工作；b.用遞歸函數(shù)backtrack〔i，total〕來實(shí)現(xiàn)回溯法搜尋排列樹〔形式參數(shù)i表示遞歸深n用來掌握遞歸深度，形式參數(shù)totals表示當(dāng)前最優(yōu)總費(fèi)用：total>=s，則不是最優(yōu)解，剪去相應(yīng)子樹，返回到i-1層連續(xù)執(zhí)行；②假設(shè)i>n，則算法搜尋到一個(gè)葉結(jié)點(diǎn)，用s對最優(yōu)解進(jìn)展記錄，返回到i-1層連續(xù)執(zhí)行；③承受for循環(huán)針對n個(gè)人對工作i進(jìn)展安排≤：1>v[j]==1，則第j個(gè)人已安排了工作，找第j+1個(gè)人進(jìn)展安排；2>假設(shè)v[j]==i安排給第j〔即v[j]=1對工作i+1調(diào)用遞歸函數(shù)backtrack〔i+1，total+c[i][j]〕連續(xù)進(jìn)展安排；3>backtrack〔i+1，total+c[i][j]〕調(diào)用完畢后則返回v[j]=0，將工作i對j+1個(gè)人進(jìn)展安排；4>j>n時(shí)，for循環(huán)完畢；i=1時(shí)