演算法設計心得體會

一、實驗內容：

這學期的演算法與設計課，老師佈置了這四個問題，分別是貨郎擔問題，動態生成二維陣列，對話方塊下拉列表，排序問題。

二、學習掌握：

基本程式描述：

（1）貨郎擔問題：貨郎擔問題屬於易於描述但難於解決的著名難題之一，至今世界上還有不少人在研究它。貨郎擔問題要從圖g的所有周遊路線中求取具有最小成本的周遊路線，而由始點出發的周遊路線一共有（n一1）！條，即等於除始結點外的n一1個結點的排列數，因此貨郎擔問題是一個排列問題。貨郎擔的程式實現了利用窮舉法解決貨郎擔問題，可以在城市個數和各地費用給定的情況下利用窮舉法逐一計算出每一條路線的費用，並從中選出費用最小的路線，從而求出問題的解。

（2）費用矩陣：費用矩陣的主要內容是動態生成二維陣列。首先由鍵盤輸入自然數，費用矩陣的元素由隨機數產生，並取整，把生成的矩陣存放在二維陣列中，最後把矩陣內容輸出到檔案和螢幕上。它採用分支界限法，分支限界法的基本思想是對包含具有約束條件的最優化問題的所有可行解的解（數目有限）空間進行搜尋。該演算法在具體執行時，把全部可行的解空間不斷分割為越來越小的子集，併為每個子集內的解計算一個下界或上界。動態生成二維n*n的陣列程式利用指標表示陣列的行和列，並逐一分配空間，在輸入n的數值後，系統自動分配空間，生成n*n的陣列，併產生隨機數填充陣列，最後將結果輸入到指定檔案中。

（3）Mfc：在下拉列表框中新增內容程式，在下拉列表對應的函式中利用addstring新增需要的內容。首先定義下拉列表框為ccombox型，並定義其屬性名，利用addstring函式可以任意新增需要的內容。a排序問題:快速排序的執行時間與劃分是否對稱有關，其最壞情況發生在劃分過程中產生的兩個區域分別包含n-1個元素和1個元素的時候。其演算法的時間複雜度為O(n2),在最好的情況下每次劃分的基準恰好為中值，可得其演算法時間複雜度為O(n?n)。演算法的實現和理解和程式碼實現完全是兩回事，想要完全掌握一種演算法，需要動手實踐，用程式碼實現，才能理解透徹，真正掌握。b對話方塊下拉列表：這個專案簡單易懂，輕鬆實現。

三、疑問與總結：

貨郎擔的問題，我認為窮舉法相對比而言是比較初級的方法，費時耗力，適合在練習時選用，但是在實際問題中不建議採用。克魯斯卡爾或者普里姆演算法求取最小生成樹的方法來解決貨郎擔的問題是更適合現實解決問題的。我認為程式可以用switch函式來將函式分成幾個部分更人性化，比如分為解決問題的的選項，輸出結果選項，退出程式選項等。再有就是費用矩陣的值可以從檔案中讀取，而結果也可以直接放在指定檔案中，這樣在實際應用中比較廣泛。

動態生成二維陣列的程式我認為如果按照規範性，我的方法是中規中矩的，畢竟再向下延伸，生成三維的陣列，需要三層的`指標來實現。但是就程式的簡化程度和計算機處理時間來說，我認為這樣雙層指標的演算法有些太佔用記憶體，畢竟要給行和列各分配n個空間。我通過與同學的交流，我發現可以用1位陣列來實現二維的n*n的陣列。首先分配n*n的空間，然後通過迴圈在一行的資料達到n時自動換行。這樣程式得到了一定的簡化，並且減少了一定的記憶體使用。我認為這種方法是比較貼合實際的。

四、心得體會：

在計算機軟體專業中，演算法分析與設計是一門非常重要的課程，很多人為它如痴如醉。很多問題的解決，程式的編寫都要依賴它，在軟體還是面向過程的階段，就有程式=演算法+資料結構這個公式。演算法的學習對於培養一個人的邏輯思維能力是有極大幫助的，它可以培養我們養成思考分析問題，解決問題的能力。

如果一個演算法有缺陷，或不適合某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間複雜性和時間複雜度來衡量。演算法可以使用自然語言、虛擬碼、流程圖等多種不同的方法來描述。計算機系統中的作業系統、語言編譯系統、資料庫管理系統以及各種各樣的計算機應用系統中的軟體，都必須使用具體的演算法來實現。演算法設計與分析是電腦科學與技術的一個核心問題。因此，學習演算法無疑會增強自己的競爭力，提高自己的修為，為自己增彩。