算法設(shè)計與分析實驗指導(dǎo)書bfm

《算法設(shè)計與分析》實驗指導(dǎo)書運算機學(xué)院信息安全系畢方明本書是為配合《算法分析與設(shè)計實驗教學(xué)大綱》而編寫的上機指導(dǎo)，其目的是使學(xué)生消化理論知識，加深對教學(xué)內(nèi)容的理解，尤其是一些算法的實現(xiàn)及其應(yīng)用，培育學(xué)生獨立編程和調(diào)試程序的能力，使學(xué)生對算法的分析與設(shè)計有更深刻的熟悉。上機實驗一般應(yīng)包括以下幾個步驟：（1） 、預(yù)備好上機所需的程序。手編程序應(yīng)書寫整齊，并經(jīng)人工檢查無誤后才能上機。（2） 、上機輸入和調(diào)試自己所編的程序。一人一組，獨立上機調(diào)試，上機時出現(xiàn)的問題，最好獨立解決。（3） 、上機結(jié)束后，整理出實驗報告。實驗報告應(yīng)包括：題目、程序清單、運行結(jié)果、對運行情形所作的分析。本書共分階段4個實驗，每一個實驗有大體題和提高題。大體題必需完成，提高題按照自己實際情形進行取舍。題目不限定如下題目，可按照自己興趣愛好做一些與實驗內(nèi)容相關(guān)的其他題目，如動態(tài)計劃法中的圖象緊縮，回溯法中的人機對弈等。其具體要求和步驟如下：實驗一分治與遞歸（4學(xué)時）大體題一：大體遞歸算法一、 實驗?zāi)康呐c要求1、 熟悉C/C++語言的集成開發(fā)環(huán)境；2、 通過本實驗加深對遞歸進程的理解二、 實驗內(nèi)容：掌握遞歸算法的概念和大體思想，分析并掌握“整數(shù)劃分”問題的遞歸算法。三、 實驗題任意輸入一個整數(shù)，輸出結(jié)果能夠用遞歸方式實現(xiàn)整數(shù)的劃分。四、 實驗步驟理解算法思想和問題要求；編程實現(xiàn)題目要求；上機輸入和調(diào)試自己所編的程序;驗證分析實驗結(jié)果；整理出實驗報告。大體題二：棋盤覆蓋問題一、實驗?zāi)康呐c要求一、 掌握棋盤覆蓋問題的算法；二、 初步掌握分治算法二、 實驗題：盤覆蓋問題：在一個2kX2k個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格之外的所有方格，且任何2個L型骨牌不得重疊覆蓋。三、 實驗提示voidchessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt=tile++,<m[k].s)k=i;}returnk;提高題一：用貪婪算法求解最小生成樹、實驗要求與目的1、 熟悉貪婪算法的大體原理與適用范圍。2、 利用貪婪算法編程，求解最小生成樹問題。二、實驗內(nèi)容1、 任選一種貪婪算法(Prim或Kruskal)，求解最小生成樹。對算法進行描述和復(fù)雜性分析。編程實現(xiàn)，并給出測試實例提高題二：汽車加油問題一、實驗?zāi)康呐c要求一、 掌握汽車加油問題的算法；二、 進一步掌握貪婪算法；二、 實驗題一輛汽車加滿油后能夠行駛N千米。旅途中有若干個加油站。若要使沿途的加油次數(shù)最少，設(shè)計一個有效的算法，指出應(yīng)在那些加油站停泊加油。并證明你的算法能產(chǎn)生一個最優(yōu)解。三、 實驗提示把兩加油站的距離放在數(shù)組中，a[1..n]表示從起始位置開始跑，通過n個加油站，a[k]表示第k-1個加油站到第k個加油站的距離。汽車在運行的進程中若是能跑到下一個站則不加油，不然要加油。（算法略）實驗四回溯算法和分支限界法（2學(xué)時）大體題一：符號三角形問題一、實驗?zāi)康呐c要求一、 掌握符號三角形問題的算法；二、 初步掌握回溯算法；二、實驗題圖下面都是“-”。下圖是由14個“+”和14個“-”組成的符號三角形。2個同號下面都是“+”，2個異號下面都是“-”。++-+-+++----+-+++-在一般情形下，符號三角形的第一行有n個符號。符號三角形問題要求對于給定的n,計算有多少個不同的符號三角形，使其所含的“+”和“-”的個數(shù)相同。三、實驗提示voidTriangle::Backtrack(intt){if((count>half)||(t*(t-1)/2-count>half))return;if(t>n)sum++;elsefor(inti=0;i<2;i++){pEg；count+=i;for(intj=2;j<=t;j++){p[j][t-j+1]=p[j-1][t-j+1]Ap[j-1][t-j+2];count+=p[j][t-j+1];}Backtrack(t+1);for(intj=2;j<=t;j++)count-=p[j][t-j+1];count-=i;}}大體題二：0—1背包問j、實驗?zāi)康呐c要求、掌握0—1背包問題的回溯算法;、進一步掌握回溯算法；二、實驗題：給定n種物品和一背包。物品i的重量是wi,其價值為vi,背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大？三、實驗提示template<classTypew,classTypep>TypepKnap<Typew,Typep>::Bound(inti){n)。旅行路徑前綴1的開銷為0，即cc=0，而且，rcost=n&&i=1時MinOut。在程序中，bestc給出了當(dāng)前能找到的最少的花費值。初始時，由于沒有找到任何旅行路徑，因此bestc的值被設(shè)為NoEdge。旅行商問題的最小花費分枝定界算法templateTAdjacencyWDigraph::BBTSP(intv[]){s++;H.Insert(E);}elsedelete[];}else{Insert(N);}}//結(jié)束可行的孩子delete[];}//對本節(jié)點的處置結(jié)束try{(E);}//取下一個E-節(jié)點catch(OutOfBounds){break;}//沒有未處置的節(jié)點}if(bestc==NoEdge)returnNoEdge;//沒有旅行路徑//將最優(yōu)路徑復(fù)制到v[1:n]中for(i=0;i<n;i++)v[i+1]=；while(true){//釋放最小堆中的所有節(jié)點delete[];try{(E);}catch(OutOfBounds){break;}}returnbestc;提高題二：用回溯法求解跳馬問題、實驗要求與目的1、掌握回溯法的大體原理。2、利用回