算法設(shè)計(jì)與分析實(shí)驗(yàn)指導(dǎo)書

1、算法設(shè)計(jì)與分析實(shí) 驗(yàn) 指 導(dǎo) 書東北大學(xué)軟件學(xué)院2012年17東北大學(xué)軟件學(xué)院信息安全專業(yè)算法設(shè)計(jì)與分析實(shí)驗(yàn)?zāi)?錄算法設(shè)計(jì)與分析1實(shí) 驗(yàn) 指 導(dǎo) 書1前 言3實(shí)驗(yàn)要求4實(shí)驗(yàn)1 分治法的應(yīng)用（2學(xué)時）51.實(shí)驗(yàn)?zāi)康?2.實(shí)驗(yàn)類型53.預(yù)習(xí)要求54.實(shí)驗(yàn)基本要求55.實(shí)驗(yàn)基本步驟7實(shí)驗(yàn)2動態(tài)規(guī)劃（2學(xué)時）91.實(shí)驗(yàn)?zāi)康?2.實(shí)驗(yàn)類型93.預(yù)習(xí)要求94.實(shí)驗(yàn)基本要求95.實(shí)驗(yàn)基本步驟10實(shí)驗(yàn)3 回溯法（4學(xué)時）121.實(shí)驗(yàn)?zāi)康?22.實(shí)驗(yàn)類型123.預(yù)習(xí)要求124.實(shí)驗(yàn)基本要求125.實(shí)驗(yàn)基本步驟13前 言算法設(shè)計(jì)與分析是一門面向設(shè)計(jì)，處于計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科核心地位的教育課程。通過對計(jì)算機(jī)算法系統(tǒng)

2、的學(xué)習(xí)，使學(xué)生理解和掌握計(jì)算機(jī)算法的通用設(shè)計(jì)方法，培養(yǎng)對算法的計(jì)算復(fù)雜性正確分析的能力，為獨(dú)立設(shè)計(jì)算法和對算法進(jìn)行復(fù)雜性分析奠定基礎(chǔ)。要求掌握算法復(fù)雜度分析、分治法、動態(tài)規(guī)劃法、貪心法、回溯法、分支限界法等算法的設(shè)計(jì)方法及其分析方法。能將這些方法靈活的應(yīng)用到相應(yīng)的問題中，并且能夠用C+實(shí)現(xiàn)所涉及的算法，并盡量做到低復(fù)雜度，高效率。通過本課程的實(shí)驗(yàn)，使學(xué)生加深對課程內(nèi)容的理解，培養(yǎng)學(xué)生嚴(yán)密的思維能力，運(yùn)用所學(xué)知識結(jié)合具體問題設(shè)計(jì)適用的算法的能力；培養(yǎng)學(xué)生良好的設(shè)計(jì)風(fēng)格，激勵學(xué)生創(chuàng)造新算法和改進(jìn)舊算法的愿望和熱情。希望同學(xué)們能夠充分利用實(shí)驗(yàn)條件，認(rèn)真完成實(shí)驗(yàn)，從實(shí)驗(yàn)中得到應(yīng)有的鍛煉和培養(yǎng)。希望同學(xué)

3、們在使用本實(shí)驗(yàn)指導(dǎo)書及進(jìn)行實(shí)驗(yàn)的過程中，能夠幫助我們不斷地發(fā)現(xiàn)問題，并提出建議，使算法設(shè)計(jì)與分析課程成為對大家有益的課程。實(shí)驗(yàn)要求算法設(shè)計(jì)與分析課程實(shí)驗(yàn)的目的是為了使學(xué)生在課堂學(xué)習(xí)的同時，通過一系列的實(shí)驗(yàn)，使學(xué)生加深理解和更好地掌握算法設(shè)計(jì)與分析課程教學(xué)大綱要求的內(nèi)容。在算法設(shè)計(jì)與分析的課程實(shí)驗(yàn)過程中，要求學(xué)生做到：（1）仔細(xì)觀察調(diào)試程序過程中出現(xiàn)的各種問題，記錄主要問題，做出必要說明和分析。（2）認(rèn)真書寫實(shí)驗(yàn)報告。實(shí)驗(yàn)報告模板見附錄1。（3）遵守機(jī)房紀(jì)律，服從輔導(dǎo)教師指揮，愛護(hù)實(shí)驗(yàn)設(shè)備。（4）實(shí)驗(yàn)課程不遲到。如有事不能出席，所缺實(shí)驗(yàn)一般不補(bǔ)。（5）本實(shí)驗(yàn)采用的開發(fā)環(huán)境為 Microsoft

4、Visual C+ 6.0，同學(xué)在做實(shí)驗(yàn)之前要求熟悉該軟件的使用方法。（6）實(shí)驗(yàn)成績主要從以下幾方面考核：實(shí)驗(yàn)過程態(tài)度，實(shí)驗(yàn)結(jié)果及報告書寫。實(shí)驗(yàn)1 分治法的應(yīng)用（2學(xué)時）1.實(shí)驗(yàn)?zāi)康模?） 理解分治法的思想。（2） 掌握用分治法解決問題2.實(shí)驗(yàn)類型設(shè)計(jì)型3.預(yù)習(xí)要求熟悉Visual C+ 6.0上機(jī)編程調(diào)試的基本方法。掌握教材上分治法的思想，掌握各種排序方法及二分搜索的思想。4.實(shí)驗(yàn)基本要求（1） 仔細(xì)閱讀備選實(shí)驗(yàn)的題目，選擇一個（可選多個）作為此次實(shí)驗(yàn)題目，設(shè)計(jì)的程序要滿足正確性，代碼中有關(guān)鍵的注釋，書寫格式清晰，簡潔易懂，效率較高，利用C的模板，設(shè)計(jì)的程序通用性好，適合各種合理輸入，并能對

5、不合理輸入做出正確的提示。（2） 可供選擇的題目有以下3個：（i） 中位數(shù)問題« 問題描述設(shè)X 0 : n - 1和Y 0 : n 1 為兩個數(shù)組，每個數(shù)組中含有n個已排好序的數(shù)。找出X和Y的2n個數(shù)的中位數(shù)。 « 編程任務(wù) 利用分治策略試設(shè)計(jì)一個O (log n)時間的算法求出這2n個數(shù)的中位數(shù)。« 數(shù)據(jù)輸入由文件input.txt提供輸入數(shù)據(jù)。文件的第1行中有1個正整數(shù)n（n<=200），表示每個數(shù)組有n個數(shù)。接下來的兩行分別是X，Y數(shù)組的元素。 « 結(jié)果輸出 程序運(yùn)行結(jié)束時，將計(jì)算出的中位數(shù)輸出到文件output.txt中。輸入文件示例輸出文

6、件示例input.txtoutput.txt35 15 183 14 2114 « 實(shí)現(xiàn)提示 比較兩個序列的中位數(shù)大小，如果兩個數(shù)相等，則該數(shù)為整個2n個數(shù)據(jù)的中位數(shù)，否則通過比較，分別減少兩個序列的查找范圍，確定查找的起止位置，繼續(xù)查找。（ii） Gray碼問題 « 問題描述Gray碼是一個長度為2n的序列。序列中無相同的元素，每個元素都是長度為n位的串，相鄰元素恰好只有一位不同。用分治策略設(shè)計(jì)一個算法對任意的n構(gòu)造相應(yīng)的Gray碼。 « 編程任務(wù) 利用分治策略試設(shè)計(jì)一個算法對任意的n構(gòu)造相應(yīng)的Gray碼。« 數(shù)據(jù)輸入由文件input.txt提供輸入數(shù)

7、據(jù)n。 « 結(jié)果輸出 程序運(yùn)行結(jié)束時，將得到的所有編碼輸出到文件output.txt中。輸入文件示例輸出文件示例input.txtoutput.txt3000100101010011111101001 « 實(shí)現(xiàn)提示 把原問題分解為兩個子問題，分別對兩個子問題的每個數(shù)組后一位加0和1。（iii）歸并排序« 問題描述目前的網(wǎng)上拍賣系統(tǒng)會顯示很多待拍賣的物品，通常這些系統(tǒng)具有按照某個關(guān)鍵字對打出的廣告進(jìn)行排序列出的功能，并且能夠按照用戶輸入的某個關(guān)鍵字進(jìn)行過慮，找到某些特定的物品。« 編程任務(wù) 定義一個Advertisement類，該類中至少包含該物品的數(shù)量，

8、名稱，聯(lián)系人e-mail，最好有開拍時間及關(guān)閉時間，根據(jù)用戶輸入的關(guān)鍵字比如名稱，mail，時間等，利用非遞歸的歸并排序?qū)λ械膹V告進(jìn)行排序，并列出所有排好序的廣告。« 數(shù)據(jù)輸入由文件input.txt提供輸入的所有廣告信息。程序中由用戶輸入要排序的關(guān)鍵字。 « 結(jié)果輸出 程序運(yùn)行結(jié)束時，排好序的廣告輸出到文件output.txt中，并為每個廣告添加序號。輸入文件示例輸出文件示例input.txtoutput.txtCoat(物品名稱)3（數(shù)量）aSkirt5bCap7cBag12aTitle（用戶輸入按照title排序）1Bag12a2Cap7c3Coat(物品名稱)3（

9、數(shù)量）a4Skirt5b （3） 按照指定的格式書寫實(shí)驗(yàn)報告，實(shí)驗(yàn)報告清晰，但不贅述，字體最大為四號。在實(shí)驗(yàn)結(jié)束一周內(nèi)上交實(shí)驗(yàn)報告。5.實(shí)驗(yàn)基本步驟（1） 選定實(shí)驗(yàn)題目，仔細(xì)閱讀實(shí)驗(yàn)要求，設(shè)計(jì)好輸入輸出，按照分治法的思想構(gòu)思算法，選取合適的存儲結(jié)構(gòu)實(shí)現(xiàn)應(yīng)用的操作。（2） 設(shè)計(jì)的結(jié)果應(yīng)在Visual C+ 實(shí)驗(yàn)環(huán)境下實(shí)現(xiàn)并進(jìn)行調(diào)試。（3） 實(shí)驗(yàn)要有詳細(xì)的測試記錄，包括各種可能的測試數(shù)據(jù)。實(shí) 驗(yàn) 報 告課程名稱：算法設(shè)計(jì)與分析班級：軟件1304 實(shí)驗(yàn)成績：實(shí)驗(yàn)名稱：分治策略學(xué)號：20134726批閱教師簽字：實(shí)驗(yàn)編號：實(shí)驗(yàn)一姓名：趙航實(shí)驗(yàn)日期： 2016年 1月 1 日指導(dǎo)教師：張莉組號：實(shí)驗(yàn)時間

10、： 時 分 時 分一、實(shí)驗(yàn)?zāi)康睦斫夥种畏ǖ乃枷?。掌握用分治法解決問題二、實(shí)驗(yàn)內(nèi)容（i） 中位數(shù)問題« 問題描述設(shè)X 0 : n - 1和Y 0 : n 1 為兩個數(shù)組，每個數(shù)組中含有n個已排好序的數(shù)。找出X和Y的2n個數(shù)的中位數(shù)。 « 編程任務(wù) 利用分治策略試設(shè)計(jì)一個O (log n)時間的算法求出這2n個數(shù)的中位數(shù)。« 數(shù)據(jù)輸入由文件input.txt提供輸入數(shù)據(jù)。文件的第1行中有1個正整數(shù)n（n<=200），表示每個數(shù)組有n個數(shù)。接下來的兩行分別是X，Y數(shù)組的元素。三、實(shí)驗(yàn)環(huán)境WINDOWS7家庭版DEVC+四、問題分析（1） 分析要解決的問題，給出你的

11、思路，可以借助圖表等輔助表達(dá)。設(shè)兩個長度為n的數(shù)列分別為x 0 : n -1和y 0 : n -1,分別找出這兩個數(shù)列的中位數(shù)xi和y j ,二者進(jìn)行比較,根據(jù)比較結(jié)果可以在每個數(shù)列中減少一半的搜索范圍,然后再分別取兩個子數(shù)列的中位數(shù)再比較,再減少搜索范圍,繼續(xù)下去直到找到最后結(jié)果（2） 分析利用你的想法解決該問題可能會有怎樣的時空復(fù)雜度。O（n）（3） 其它（你認(rèn)為需要在此說明的）五、問題解決（1） 根據(jù)對問題的分析，寫出解決辦法。設(shè)兩個長度為n的數(shù)列分別為x 0 : n -1和y 0 : n -1,分別找出這兩個數(shù)列的中位數(shù)xi和y j ,二者進(jìn)行比較,根據(jù)比較結(jié)果可以在每個數(shù)列中減少一半

12、的搜索范圍,然后再分別取兩個子數(shù)列的中位數(shù)再比較,再減少搜索范圍,繼續(xù)下去直到找到最后結(jié)果（2） 描述你在進(jìn)行實(shí)現(xiàn)時，主要的函數(shù)或操作內(nèi)部的主要算法；分析這個算法的時、空復(fù)雜度，并說明你設(shè)計(jì)的巧妙之處，如有創(chuàng)新，將其清晰的表述。int findMedian(int* x, int* y, int n) if(n=1) return *x <= *y? *x:*y; int m=(n-1)/2; int p=m+1; if(n%2!=0) p-; if(*(x+m)=*(y+m) return *(x+m); else if(*(x+m)<*(y+m) return findMedi

13、an(x+p,y,m+1); else return findMedian(x,y+p,m+1);O（n）算法的巧妙之處在于分別找出這兩個數(shù)列的中位數(shù)xi和y j ,二者進(jìn)行比較,根據(jù)比較結(jié)果可以在每個數(shù)列中減少一半的搜索范圍,然后再分別取兩個子數(shù)列的中位數(shù)再比較,再減少搜索范圍,繼續(xù)下去直到找到最后結(jié)果（3） 針對你所選的問題，你認(rèn)為應(yīng)該特別注意哪些方面的處理？比如循環(huán)何時結(jié)束等。分別找出這兩個數(shù)列的中位數(shù)xi和y j ,二者進(jìn)行比較，直到最后的結(jié)果。（4） 你在調(diào)試過程中發(fā)現(xiàn)了怎樣的問題？又做了怎樣的改進(jìn)？在調(diào)試中發(fā)現(xiàn)了編譯不通過，經(jīng)檢查是語法問題。（5） 其它（你認(rèn)為需要在此說明的）六、

14、實(shí)驗(yàn)結(jié)果總結(jié)回答以下問題：（1） 對不同的輸入，該算法都存在哪幾類可能出現(xiàn)的情況，你的測試數(shù)據(jù)完全覆蓋了你所想到的這些情況，測試結(jié)果如何？1、普通 2、數(shù)組中只有一個數(shù) 結(jié)果如下 （2） 算法實(shí)現(xiàn)的復(fù)雜度在問題規(guī)模很大時可以接受嗎？可以（3） 如果不用分治方法還能想到其他的解決方式嗎？和分治相比會有更好的效率嗎？有：將二者放到同一數(shù)組然后排序取中值，效率更低。（4） 所選用的數(shù)據(jù)結(jié)構(gòu)合適嗎？選用數(shù)組，合適。（5） 敘述通過實(shí)驗(yàn)?zāi)銓Ψ种畏椒ǖ睦斫饧澳阏J(rèn)為的分治法的優(yōu)缺點(diǎn)。分治法的優(yōu)點(diǎn)是將大問題拆成小問題來進(jìn)行解決，可以節(jié)約時間。（6） 其它（你認(rèn)為需要在此說明的）六、附錄（1） 如果你對這個實(shí)驗(yàn)

15、還有其他的解決方案或設(shè)想，或?qū)ξ覀兊膶?shí)驗(yàn)方案有什么意見，請?jiān)诖嗣枋?。?） 實(shí)驗(yàn)參考的資料和網(wǎng)址 注：本實(shí)驗(yàn)的考核點(diǎn)主要在問題的分析是否正確，對問題的考慮是否全面，解決方法及程序是否正確，程序代碼是否清晰，是否符合編碼規(guī)范，是否有注釋，測試數(shù)據(jù)是否完整，是否有創(chuàng)新。第 10 頁 共 17 頁實(shí)驗(yàn)2動態(tài)規(guī)劃（2學(xué)時）1.實(shí)驗(yàn)?zāi)康模?） 熟練掌握動態(tài)規(guī)劃思想及教材中相關(guān)經(jīng)典算法。（2） 掌握用動態(tài)規(guī)劃解題的基本步驟，能夠用動態(tài)規(guī)劃解決一些問題。2.實(shí)驗(yàn)類型設(shè)計(jì)型3.預(yù)習(xí)要求掌握動態(tài)規(guī)劃思想，復(fù)習(xí)學(xué)過的有關(guān)動態(tài)規(guī)劃的算法，并設(shè)計(jì)實(shí)驗(yàn)題目的程序。4.實(shí)驗(yàn)基本要求（1） 仔細(xì)閱讀備選實(shí)驗(yàn)的題目，選擇一個

16、（可選多個）作為此次實(shí)驗(yàn)題目，設(shè)計(jì)的程序要滿足正確性，代碼中有關(guān)鍵的注釋，書寫格式清晰，簡潔易懂，效率較高，利用C的模板，設(shè)計(jì)的程序通用性好，適合各種合理輸入，并能對不合理輸入做出正確的提示。（2） 可供選擇的題目有以下2個：(i）找零錢問題（難度系數(shù)為3）« 問題描述設(shè)有n種不同面值的硬幣，各硬幣的面值存于數(shù)組T1:n中?，F(xiàn)要用這些面值的硬幣來找錢，可以實(shí)用的各種面值的硬幣個數(shù)不限。當(dāng)只用硬幣面值T1,T2,Ti時，可找出錢數(shù)j的最少硬幣個數(shù)記為C(i,j)。若只用這些硬幣面值，找不出錢數(shù)j時，記C(i,j)=。 « 編程任務(wù) 設(shè)計(jì)一個動態(tài)規(guī)劃算法，對1jL，計(jì)算出所有的

17、C( n,j )。算法中只允許實(shí)用一個長度為L的數(shù)組。用L和n作為變量來表示算法的計(jì)算時間復(fù)雜性« 數(shù)據(jù)輸入由文件input.txt提供輸入數(shù)據(jù)。文件的第1行中有1個正整數(shù)n（n<=13），表示有n種硬幣可選。接下來的一行是每種硬幣的面值。由用戶輸入待找錢數(shù)j。 « 結(jié)果輸出 程序運(yùn)行結(jié)束時，將計(jì)算出的所需最少硬幣個數(shù)輸出到文件output.txt中。輸入文件示例輸出文件示例input.txtoutput.txt31 2 593 « 實(shí)現(xiàn)提示 首先要建立遞歸關(guān)系，并將分析過程寫在報告中。(ii) 租用游艇問題（難度系數(shù)為4） « 問題描述長江游艇俱

18、樂部在長江上設(shè)置了n個游艇出租站1，2，n。游客可在這些游艇出租站租用游艇，并在下游的任何一個游艇出租站歸還游艇。游艇出租站i到游艇出租站j之間的租金為r(i,j),1£i<j£n。試設(shè)計(jì)一個算法，計(jì)算出從游艇出租站1到游艇出租站n所需的最少租金。 « 編程任務(wù)對于給定的游艇出租站i到游艇出租站j之間的租金為r(i,j),1£i<j£n，編程計(jì)算從游艇出租站1到游艇出租站n所需的最少租金。« 數(shù)據(jù)輸入由文件input.txt提供輸入數(shù)據(jù)。文件的第1行中有1個正整數(shù)n（n<=200），表示有n個游艇出租站。接下來的n-

19、1行是r(i,j),1£i<j£n。 « 結(jié)果輸出程序運(yùn)行結(jié)束時，將計(jì)算出的從游艇出租站1到游艇出租站n所需的最少租金輸出到文件output.txt中。輸入文件示例輸出文件示例input.txtoutput.txt35 15712 « 實(shí)現(xiàn)提示 建立遞歸關(guān)系，然后按照遞歸關(guān)系寫出算法。（3） 按照指定的格式書寫實(shí)驗(yàn)報告，實(shí)驗(yàn)報告清晰，但不贅述，字體最大為四號。在實(shí)驗(yàn)結(jié)束一周內(nèi)上交實(shí)驗(yàn)報告。5.實(shí)驗(yàn)基本步驟（4） 選定實(shí)驗(yàn)題目，仔細(xì)閱讀實(shí)驗(yàn)要求，設(shè)計(jì)好輸入輸出，按照分治法的思想構(gòu)思算法，選取合適的存儲結(jié)構(gòu)實(shí)現(xiàn)應(yīng)用的操作。（5） 設(shè)計(jì)的結(jié)果應(yīng)在Visu

20、al C+ 實(shí)驗(yàn)環(huán)境下實(shí)現(xiàn)并進(jìn)行調(diào)試。（6） 實(shí)驗(yàn)要有詳細(xì)的測試記錄，包括各種可能的測試數(shù)據(jù)。實(shí) 驗(yàn) 報 告課程名稱：算法設(shè)計(jì)與分析班級： 軟件1304實(shí)驗(yàn)成績：實(shí)驗(yàn)名稱：動態(tài)規(guī)劃學(xué)號：20134726批閱教師簽字：實(shí)驗(yàn)編號：實(shí)驗(yàn)二姓名：趙航實(shí)驗(yàn)日期： 2016 年 1 月 5 日指導(dǎo)教師：張莉組號：實(shí)驗(yàn)時間： 時 分 時 分一、實(shí)驗(yàn)?zāi)康氖炀氄莆談討B(tài)規(guī)劃思想及教材中相關(guān)經(jīng)典算法。掌握用動態(tài)規(guī)劃解題的基本步驟，能夠用動態(tài)規(guī)劃解決一些問題。二、實(shí)驗(yàn)內(nèi)容與實(shí)驗(yàn)步驟找零錢問題（難度系數(shù)為3）« 問題描述設(shè)有n種不同面值的硬幣，各硬幣的面值存于數(shù)組T1:n中?，F(xiàn)要用這些面值的硬幣來找錢，可以實(shí)

21、用的各種面值的硬幣個數(shù)不限。當(dāng)只用硬幣面值T1,T2,Ti時，可找出錢數(shù)j的最少硬幣個數(shù)記為C(i,j)。若只用這些硬幣面值，找不出錢數(shù)j時，記C(i,j)=。 « 編程任務(wù) 設(shè)計(jì)一個動態(tài)規(guī)劃算法，對1jL，計(jì)算出所有的C( n,j )。算法中只允許實(shí)用一個長度為L的數(shù)組。用L和n作為變量來表示算法的計(jì)算時間復(fù)雜性« 數(shù)據(jù)輸入由文件input.txt提供輸入數(shù)據(jù)。文件的第1行中有1個正整數(shù)n（n<=13），表示有n種硬幣可選。接下來的一行是每種硬幣的面值。由用戶輸入待找錢數(shù)j。 « 結(jié)果輸出 程序運(yùn)行結(jié)束時，將計(jì)算出的所需最少硬幣個數(shù)輸出到文件output.

22、txt中。輸入文件示例輸出文件示例input.txtoutput.txt31 2 593 « 實(shí)現(xiàn)提示 首先要建立遞歸關(guān)系，并將分析過程寫在報告中。三、實(shí)驗(yàn)環(huán)境操作系統(tǒng)、調(diào)試軟件名稱、版本號，上機(jī)地點(diǎn)，機(jī)器臺號四、問題分析（1） 分析要解決的問題，給出你的思路，可以借助圖表等輔助表達(dá)。問題為找零錢，則應(yīng)該采用遞歸的算法解決問題，一個一個硬幣往上加（2） 根據(jù)分析建立正確的遞歸關(guān)系c(i, j)表示從第1個到第i個硬幣可選，要找的錢數(shù)是j，則出口是（3） 分析利用你的想法解決該問題可能會有怎樣的時空復(fù)雜度。O(n的平方)（4） 其它（你認(rèn)為需要在此說明的）五、問題解決（1） 根據(jù)對問題

23、的分析，寫出解決辦法。采用遞歸的算法解決問題，一個一個硬幣往上加（2） 描述你在進(jìn)行實(shí)現(xiàn)時，主要的函數(shù)或操作內(nèi)部的主要算法；分析這個算法的時、空復(fù)雜度，并說明你設(shè)計(jì)的巧妙之處，如有創(chuàng)新，將其清晰的表述。 int changeCoins(int *T, int n, int v) sort(T,T+n); int *c=new int*n; for(int m=0;m<n;m+) cm=new intv+1; for(int i=0;i<=v;i+) if(i%T0=0) c0i=i/T0; else c0i=INT_MAX; for(int j=1;j<n;j+) for(i

24、nt k=0;k<=v;k+) if(k<Tj) cjk=cj-1k; else cjk=cj-1k<cjk-Tj+1?cj-1k:cjk-Tj+1; return cn-1v; delete c;O(n的平方)（3） 你在調(diào)試過程中發(fā)現(xiàn)了怎樣的問題？又做了怎樣的改進(jìn)？發(fā)現(xiàn)編譯報錯，經(jīng)查是語法問題（4） 寫出用你的測試數(shù)據(jù)按照算法的流程填寫的算法中的存儲結(jié)構(gòu)。（5） 其它（你認(rèn)為需要在此說明的）六、實(shí)驗(yàn)結(jié)果總結(jié)回答以下問題：（1） 法實(shí)現(xiàn)的復(fù)雜度在問題規(guī)模很大時可以接受嗎？可以接受。（2） 如果不用動態(tài)規(guī)劃方法還能想到其他的解決方式嗎？和動態(tài)規(guī)劃相比會有更好的效率嗎？可以用回

25、溯法，效率更高。（3） 所選用的數(shù)據(jù)結(jié)構(gòu)合適嗎？合適（4） 該算法都存在哪幾類可能出現(xiàn)的情況，你的測試完全覆蓋了你所想到的這些情況嗎，測試結(jié)果如何？1、硬幣數(shù)為1 2、普通 3、找不出來 結(jié)果如下（5） 敘述通過實(shí)驗(yàn)?zāi)銓討B(tài)規(guī)劃方法的理解及其優(yōu)缺點(diǎn)優(yōu)點(diǎn)是在分治法的基礎(chǔ)上減少了重復(fù)計(jì)算。（6） 其它（你認(rèn)為需要在此說明的） 六、附錄（1） 如果你對這個實(shí)驗(yàn)還有其他的解決方案或設(shè)想，或?qū)ξ覀兊膶?shí)驗(yàn)方案有什么意見，請?jiān)诖嗣枋?。?） 實(shí)驗(yàn)參考的資料 注：本實(shí)驗(yàn)的考核點(diǎn)主要在問題的分析是否正確，遞歸關(guān)系建立是否正確，對問題的考慮是否全面，解決方法及程序是否正確，程序代碼是否清晰，是否符合編碼規(guī)范，是否有注釋，測試數(shù)據(jù)是否完整，是否有創(chuàng)新。實(shí)驗(yàn)3 回溯法（4學(xué)時）1.實(shí)驗(yàn)?zāi)康模?） 理解回溯法的思想。（2） 掌握一些經(jīng)典的問題解決方法。2.實(shí)驗(yàn)類型設(shè)計(jì)型3.預(yù)習(xí)要求熟悉Visual C+ 6.0上機(jī)編程調(diào)試的基本方法。掌握教材上回溯法的思想。4.實(shí)驗(yàn)基本要求（1） 仔細(xì)閱讀備選實(shí)驗(yàn)的題目，選擇一個（可選多個）作為此次實(shí)驗(yàn)題目，設(shè)計(jì)的程序要滿足正確性，代碼中有關(guān)鍵的注釋，書寫格式清晰，簡潔易懂，效率較高，利用C的模板