第一篇：算法設計與分析學習報告

算法課程學習報告

持續13周的高級算法設計與分析課程結束了。選修了這門課程的同學們即將迎來最后的考試。回顧這半年以來關于這么課程的學習情況，我體會最深的是：不論是從深度還是從廣度上，現在所習的算法比曾經學習的算法難度增加了很多。但是鄧教授極富經驗的教學和詳細的課件，為我的學習提供了很大的方便。可是畢竟我以前的底子不夠厚，基礎不夠勞，在聽課中會出現跟不上教師思路的現象。我也積極的采取措施，爭取處理好這種情況。總體說來，上完算法課，我還是學到了很多東西的。下面我就對所學的內容進行梳理歸納，總結一下我在學習中的體會和研究心得。

算法課程的開課階段，鄧教授為我們簡單介紹了算法，課堂上可能用到的參考資料，以及一些著名的算法方面的書籍，為我的學習提供潛在的工具。我購買了一本教材——《算法導論》。這本書夠厚，夠詳細。但是我一直沒有機會仔細的研讀。我想有一天希望能夠好好讀一下。在介紹算法的課堂上，我還了解了算法相關的一些基本概念，算法的重要性，還有算法的歷史。我印象最深的就是一個叫圖靈的外國人。對計算機科學與技術這個領域做出了圖書貢獻。我個人認為，堪比愛因斯塔發現相對論的貢獻。都揭示了某個領域的本質。開辟的一個領域的發展。對于整個人類來說，他們這類人都是功不可沒的。已經不能簡單的用偉人來形容他們。但是人類社會需要這樣的人，社會需要一些人的推動才能進步。說到這里，我不禁要想，算法到底有什么用，也許答案是簡單的，為了方便寫程序實現系統功能。這只是表面的用途。我覺得最本質的作用是為了社會進步。辯證唯物主義自然觀中有關于科學技術的詳細定義。之所以產生科學技術是為了發揮人的主觀能動性去改造自然。學習和研究算法正是為了讓人在一定的限度內改造自然。我不是在扯，而是在寫算法報告和背自然辯證法資料的時候產生的心得體會，不知道算不算鄧教授要求的心得。介紹完算法歷史以后，就進入的真正的算法設計與分析的學習。首先是算法的定義和時間復雜度等。然后，為了方便以后的課程學習，我學到了一些必要的數學知識，既是為了以后的學習打基礎，也是為了彌補在曾經的學習中的不足。這些數學知識包括生成函數和主定理等。這些數學知識都是連在高等數學里都沒有接觸過的。不知道屬于哪個范疇的數學，反正用兩個字形容就是“厲害”。我學的不亦樂乎，暈頭轉向。

幾堂課后，對算法這一概念有了基本的了解，也對數學知識進行了補強。我們在鄧教授的帶領下，進入了實際的算法技術的學習。一共有六種常用技術：分治法，貪心法，周游法，回溯法，動態規劃法，分支界定法。最先學習的是六種技術之首，應用最廣泛的，分治法。分治法的算法思想真的很神奇，不止分治，這幾種算法常用技術都很神奇，可以將問題的求解進行很大程度上的優化，而且有些還是反人類的想法。對我的智商著實是一個考驗。當然了，算法的學習不只是靠智商的，更要靠辛勤的汗水，即便有時候汗水沒有智商有用，但是你還是要付出汗水。因為這是一種福報。能力有多大，就享有多大的成果。這就好比一個人中了500萬的頭彩。這個人有能力享有這500萬的財富嗎？如果他有足夠很好的駕馭這筆財富的能力，那么在未來，他會讓這筆財富繼續增長，直到達到他的能力的極限情形。如果他沒有駕馭的能力，用不了多久，他就會分崩離析。我的思維再一次被學科外的體會占據了。言歸正傳，我學了很多利用分治法結局的問題，比如尋找最近點對，求數組的第k小元等。這些都是利用分治法解決的。在這之中，出現了平衡的概念，和分治法是密切相關，甚至是不可分的。在這部分

中，最后學習了離散傅立葉變換和快速傅立葉變換。

接下來的學習的算法技術是動態規劃法。這種技術和分治法有很多相同點，最基本的就是都是講問題分解為若干子問題，不同點是分治的子問題是相互獨立的，動態規劃的子問題是重復的，這也決定了，一個用遞歸的計算方式，一個用遞推的計算方式。我也學到了利用動態規劃法解決的很多問題，簡單的如矩陣連成問題，復雜一點的有最長公共子序列問題，最有二分搜索樹和流水作業問題。在這部分知識中，還有一點，就是備忘錄方法，可以說是對動態規劃法的一個完善和改進。

隨著課程的進行，我又學到了集合算法。主要知識點有平攤分析，合并算法，2-3樹，以及一些概念如字典，可并堆和可連接隊列等。需要注意的是這部分留過作業的FIND()和FIND_DEPTH()兩個函數。還有有窮自動機問題。

接下來學習的是隨機算法。應該說這部分內容還是相當重要的，而且應用也非常廣泛。在日常生活中更是隨處可見。舉一個最簡單的例子，當我在看NBA比賽的時候，每節的休息時間都要抽獎，那個隨機顯示的中獎觀眾就是基于隨機算法實現的功能。在這部分內容中，我學到了3個重要的隨機算法：KMP、Monte Carlo和Las Vegas算法的評價和比較。這也是作為作業研究過的。也學習的素數判定隨機算法。這里，要明白Miller-Rabin算法，是Rabin在Miller提出的基礎上，研究出來的很常用的算法。

在課程的最后階段，我學到了RAM和RASP這兩個概念。應該說這部分知識是我學的最不好的地方。算法本質還沒有了解。還需要進一步的研究。最后是NP-C和NP-hard問題。

以上簡單回顧的整個算法過程中學到的知識和自己的一些心得體會。都是一字一字碼出來的。覺悟抄襲。當然，有很多不足也有很多不全面的地方。但是，總的說來還是收貨頗豐的。這也歸功于鄧教授優秀的教學質量。在這里感謝教授的教導，祝春節快樂，身體健康。

第二篇：數據結構算法設計與分析

數據結構算法設計與分析、計算機網絡、計算機組成原理、操作系統原理、編譯原理、數據庫原理及應用、軟件工程、軟件測試等計算機基礎理論課程；

網頁制作、程序設計Java、JSP程序設計、Oracle、XML程序設計、計算機網絡、SSH（Struts+Spring+Hibernate）框架、Java EE程序設計、Ajax程序設計、Linux+PHP+MySQL程序設計、Android手機開發、UML系統分析與設計、性能測試、自動化軟件測試、軟件質量保證、畢業設計及項目綜合實訓等。

數據結構、計算機網絡、計算機組成原理、操作系統原理、編譯原理、數據庫原理及應用、金融學概論、西方經濟學等基礎理論課程；

網頁制作、程序設計Java、JSP程序設計、J2EE程序設計、SQL Server數據庫、Oracle數據庫、Linux操作系統、UML系統分析與設計、軟件工程、XML程序設計、SSH框架、金融市場學、ERP財務管理、管理信息系統、投資銀行學、商業銀行學、國際金融管理、畢業設計及項目綜合實訓等專業課程。

數據結構、計算機網絡、計算機組成原理、操作系統原理、數據庫原理及應用、軟件工程、軟件測試等計算機基礎理論課程；

網頁制作、程序設計Java、JSP程序設計、J2EE程序設計、XML程序設計、Ajax程序設計、SSH框架、Android手機開發、Linux+PHP+MySQL程序設計、SQL Server數據庫、Linux操作系統、UML系統分析與設計、軟件項目管理、行業標準與規范、IT服務管理、IT職業英語、畢業設計及項目綜合實訓等專業課程

第三篇：算法設計與分析學習心得

算法設計與分析學習心得

班級：物聯網1201 姓名：劉瀟 學號：1030612129

一、實驗內容：

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

二、學習掌握：

基本程序描述：

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

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

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

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

動態生成二維數組的程序我認為如果按照規范性，我的方法是中規中矩的，畢竟再向下延伸，生成三維的數組，需要三層的指針來實現。但是就程序的簡化程度和計算機處理時間來說，我認為這樣雙層指針的算法有些太占用內存，畢竟要給行和列各分配n個空間。我通過與同學的交流，我發現可以用1位數組來實現二維的n*n的數組。首先分配n*n的空間，然后通過循環在一行的數據達到n時自動換行。這樣程序得到了一定的簡化，并且減少了一定的內存使用。我認為這種方法是比較貼合實際的。

四.心得體會

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

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

第四篇：算法設計與分析試題1

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

算法設計與分析試題1

一、單選題（每題2分，共40分）1、0518號臺風“達維”過后，要對各個單位捐款救災情況進行分組制表，并進行積分排序，一般使用的專業電子處理軟件有（B）

A、powerpoing B、Excel C、Word D、Visual Basic

2、一位愛好程序設計的同學，想通過程序設計解決“韓信點兵”的問題，他制定的如下工作過程中，更恰當的是（C）

A、設計算法，編寫程序，提出問題，運行程序，得到答案

B、分析問題，編寫程序，設計算法，運行程序，得到答案

C、分析問題，設計算法，編寫程序，運行程序，得到答案

D、設計算法，提出問題，編寫程序，運行程序，得到答案

3、交通警察到達案發現場，一般按照下列哪種思路開展工作（D）

①觀察、分析現場 ②收集必要的信息 ③進行判斷、推理 ④按一定的方法和步驟解決

A、②①③④ B、①③②④ C、③①②④ D、①②③④

4、下面說法正確的是（A）

A、算法+數據結構=程序 B、算法就是程序

C、數據結構就是程序 D、算法包括數據結構

5、下列常量說明中，符合語法的是（D）

A、CONST color=red B、CONST const=10*5

C、CONST xl：=3.9； D、CONST color=”abcd”

精心收集

精心編輯

精致閱讀

如需請下載！

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

6、VB中將兩個字符串連接起來的運算符有：+和&，那么“123”+45結果是（A）

A、168 B、12345 C、”123” D、45

7、字符串”ABCD”和字符串”DCBA”進行比較，如果讓比較的結果為真，應選用關系運算符（B）

A、> B、< C、= D、>=

8、設a，b，c，d，e均為整型變量，且a=13，b=2，c=10，d=3，e=2，則表達式“a-b*c d MOD e”的值是(A)

A、13 B、-7 C、ll D、0

9、已知A，B，C，D是簡單變量，且都已有互不相同的值，執行語句B=8；A=C；D=A；D=B；后，其值相等的變量是（B）

A、A，D B、A，C C、C，B D、B，A

10、結構化程序設計由三種基本結構組成，下面哪個不屬于這三種基本結構（B）

A、順序結構 B、輸入、輸出結構 C、選擇結構 D、循環結構

11、下列結果為真的關系表達式是（C）

A、”A”<100 B、23.5<20 C、23<45 AND 72>8 D、5

12、以下運算符中運算優先級最高的是（D）

A、+ B、OR C、> D、13、整除運算時，若運算量為實數，則先取整，后相除，結果為整型或長整型。下列哪種是整除運算符（D）

A、+ B、Mod C、/ D、精心收集

精心編輯

精致閱讀

如需請下載！

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

14、VB結束程序的運行可以單擊程序窗體的“關閉”按鈕，或單擊VB工具欄上的“結果”按鈕，哪種是“結束”按鈕（B）

A、B、C、D、15、圖標控件屬于哪種基本控件（B）

A、標簽 B、文本框 C、按鈕 D、圖像

16、要交換變量A和B之值，應使用的語句組是(B)

A、A=B；B=C；C=A B、C=A；A=B；B=C

C、A=B；B=A D、C=A；B=A；B=C

17、執行下面的程序段后，x 的值為(A)

x=5

For i=1 To 20 Step 2

x=x+i5

Next i

A、21 B、22 C、23 D、24

18、在窗體上畫一個命令按鈕，然后編寫如下事件過程：

Private Sub Command1_Click()

Dim I as integer,j as integer,x as integer

x=4

For i=1 To 4

For j =1 To 3

x=x+6

Next j

精心收集

精心編輯

精致閱讀

如需請下載！

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

Next i

Print x

End Sub

程序運行后，單擊命令按鈕，程序循環次數是(B)

A、4 B、12 C、3 D、6

19、在窗體上畫一個命令按鈕，然后編寫如下事件過程：

Prevate Sub Command1_Click()

Dim a as integer,b as integer, x as integer

x=0

Do Until x=-1

a = InputBox(“請輸入A的值”)

a = Val(a)

b = InputBox(“請輸入B的值”)

b = Val(b)

x = InputBox(“請輸入x的值”)

x = cint(x)

a = a+b+x

Loop

Print a

End Sub

程序運行后，單擊命令按鈕，依次在輸入對話框中輸入5、4、3、2、1、-1，則輸出結果為(A)

精心收集

精心編輯

精致閱讀

如需請下載！

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

A、2 B、3 C、14 D、15

20、在窗體上畫一個文本框（其中Name屬性為Text1），然后編寫如下事件過程：

Private Sub Form_Load()

Dim i as integer,sum as integer

Text1.Text=“"

For i=1 To 10

Sum=Sum+i

Next i

Text1.caption=Sum

End Sub

上述程序的運行結果是(C)

A、在文本框Text1中輸出55

B、在文本框Text1中輸出0

C、出錯

D、在文本框Text1中輸出不定值

二、多選題（每題2分，共20分）

1、算法描述可以有多種表達方法，下面哪些方法可以描述“水仙花數問題”的算法(ABC)

A、自然語言 B、流程圖 C、偽代碼 D、機器語言

2、程序設計語言的發展經歷哪幾個過程(ABC)

A、機器語言 B、匯編語言 C、高級語言 D、自然語言

精心收集

精心編輯

精致閱讀

如需請下載！

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

3、“閏年問題”的算法可以用哪些語言實現(ABCD)

A、Basic B、Pascal C、C++ D、C 語言

4、算法應該具有哪些重要的特征(ABCD)

A、有窮性 B、確定性 C、輸入、輸出 D、可行性

5、“今有物不知其數，三三數之余二，五五數之余三，七七數之余二，問物幾何？”這個問題屬于(ABD)

A、“韓信點兵問題” B、“鬼谷算法問題” C、“水仙花數問題” D、“閏年問題”

6、編制計算機程序解決問題的過程有：描述問題、算法設計、編寫計算機程序和調試等，其中，對算法描述正確的是(AD)

A、算法是解決問題的步驟

B、解題的步驟是有限的 C、算法就是解題的算式

D、算法是可以被表述和實現

7、以下屬非法用戶自定義標識符（常量和變量命名）的是(ACD)

A、8ad B、ad C、_ad D、const

8、為了便于數據的表示與處理，VB提供哪幾種基本數據類型(ABCD)

A、數值型 B、字符串型 C、布爾型 D、日期型

9、日期型數據專門用來處理日期和時間，哪種屬于日期型數據(AB)

A、#2005/10/23# B、#2005/01/02# C、2005/10/23 D、“2005/1/2”

精心收集

精心編輯

精致閱讀

如需請下載！

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

10、哪些文件屬于某一VB工程中的文件(ABCD)

A、.vbp B、.frm C、.ocx D、.bas

三、判斷題（每題1分，共10分）

1、Visual Basic是美國微軟公司于1991年推出的基于Basic的可視化程序設計語言。（1）

2、一個算法可以被認為是用來解決一個計算問題的工具。（1）

3、一個算法可以用多種程序設計語言來實現。（1）

4、計算機是人制造的，所以，它和人腦解決問題沒有什么區別。（2）

5、字符串型數據是指用‘ ’括起來的一串字符。（2）

6、我們常說的程序設計語言就是程序設計。（2）

7、控件是應用程序的基本元素，與窗體共同構成應用程序的界面。（1）

8、面向對象的程序設計以對象為中心，以事件為過程的執行起點。（1）

9、MsgtBox函數反回值的類型為數值。（1）

10、Ctrl+T能打開屬性窗口。（2）

四、簡答題（每題10分，共30分）

1、說說人類和計算機解決問題的區別？

精心收集

精心編輯

精致閱讀

如需請下載！

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

2、用流程圖描述出“閏年問題”的算法。

算法描述：

輸入年份Y

IF Y能被4整除 THEN

IF Y不能被100整除 THEN

輸出“是閏年”

ELSE

IF Y能被400整除 THEN

輸出“是閏年”

ELSE

輸出“不是閏年”

END IF

END IF

ELSE

輸出“不是閏年”

END IF

精心收集

精心編輯

精致閱讀 如需請下載！

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

3、在“神州號”程序中，我們只判斷了飛船成功飛行的條件。當飛船速度繼續加大時，飛船將達到第二宇宙、第三宇宙速度。。。。（見下表）

試編寫程序，輸入不同的飛船速度，判斷它的各種飛行狀況。

飛船速度（V）單位（km/s）

飛行狀況

7.91<=V<11.19 飛船繞地球似做勻速圓周運動

11.19<=V<16.67 飛船離開地球的控制 ,圍繞太陽轉

V>16.67 飛船掙脫太陽引力飛出太陽系

編程：

精心收集

精心編輯

精致閱讀

如需請下載！

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

方法一：Prevate Sub Command1_Click()

Dim v As Integer

v = InputBox(”請輸入飛船速度的值“)

If(v >= 7.91)And(v <= 11.19)Then

Label1.Caption = ” 飛船繞地球似做勻速圓周運動“

Else

If(v >= 11.19)And(v <= 16.67)Then

Label1.Caption = ” 飛船離開地球的控制,圍繞太陽轉“

Else

If v >= 16.67 Then

Label1.Caption = ” 飛船掙脫太陽引力飛出太陽系“

Else

If v <= 7.91 Then

Label1.Caption = ” 輸入數據錯誤！“

End If

End If

End If

End If

End Sub

方法二：(課本P36)

Private Sub Form_Load()

Dim v As single

精心收集

精心編輯

精致閱讀

如需請下載！

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

v = InputBox(”請輸入飛船速度的值“)

select case v

case is>16.67

Label1.Caption = ”飛船掙脫太陽引力飛出太陽系“

case is >= 11.19

Label1.Caption = ” 飛船離開地球的控制,圍繞太陽轉“

case is <= 7.91

Label1.Caption = ” 飛船離開地球的控制,圍繞太陽轉“

Case else

Label1.Caption = ” 輸入數據錯誤！"

End select

End Sub

精心收集

精心編輯

精致閱讀

如需請下載！

第五篇：算法分析與設計知識點總結

第一章 概述

算法的概念：算法是指解決問題的一種方法或過程，是由若干條指令組成的有窮序列。算法的特征：

可終止性：算法必須在有限時間內終止；

正確性：算法必須正確描述問題的求解過程；

可行性：算法必須是可實施的；

算法可以有0個或0個以上的輸入；

算法必須有1個或1個以上的輸出。

算法與程序的關系：

區別：程序可以不一定滿足可終止性。但算法必須在有限時間內結束；

程序可以沒有輸出,而算法則必須有輸出；

算法是面向問題求解的過程描述，程序則是算法的實現。

聯系：程序是算法用某種程序設計語言的具體實現；

程序可以不滿足算法的有限性性質。

算法描述方式：自然語言，流程圖，偽代碼，高級語言。

算法復雜性分析：

算法復雜性的高低體現運行該算法所需計算機資源（時間，空間）的多少。

算法復雜性度量：

期望反映算法本身性能，與環境無關。

理論上不能用算法在機器上真正的運行開銷作為標準（硬件性能、代碼質量影響）。

一般是針對問題選擇基本運算和基本存儲單位，用算法針對基本運算與基本存儲單位的開銷作為標準。

算法復雜性C依賴于問題規模N、算法輸入I和算法本身A。即C=F(N, I, A)。

第二章遞歸與分治

分治法的基本思想：

求解問題算法的復雜性一般都與問題規模相關，問題規模越小越容易處理。

分治法的基本思想是，將一個難以直接解決的大問題，分解為規模較小的相同子問題，直至這些子問題容易直接求解，并且可以利用這些子問題的解求出原問題的解。各個擊破，分而治之。

分治法產生的子問題一般是原問題的較小模式，這就為使用遞歸技術提供了方便。遞歸是分治法中最常用的技術。

使子問題規模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規模不等的做法要好。

分治法所能解決的問題一般具有以下幾個特征：

該問題的規模縮小到一定的程度就可以容易地解決；

該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質；利用該問題分解出的子問題的解可以合并為該問題的解；

該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。（這條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然也可用分治法，但一般用動態規劃較好。）

遞歸的概念：

直接或間接地調用自身的算法稱為遞歸算法，用函數自身給出定義的函數稱為遞歸函數。

反復應用分治手段，可以使子問題與原問題類型一致而其規模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。

邊界條件與遞歸方程是遞歸函數的二個要素，遞歸函數只有具備了這兩個要素，才能在有限次計算后得出結果。

第三章動態規劃

動態規劃的基本思想：

動態規劃算法與分治法類似，其思想把求解的問題分成許多階段或多個子問題，然后按順序求解各子問題。最后一個階段或子問題的解就是初始問題的解。

分治法求解時，子問題數目太多，從而導致解決原問題需要耗費指數級時間。與分治法不同的是，動態規劃中分解得到的子問題往往不是互相獨立的。

但不同子問題的數目常常只有多項式級。用分治法求解時，有些子問題被重復計算了許多次。

動態規劃的適用條件：

動態規劃法解所能解決的問題一般具有以下兩個基本因素：

一、最優子結構性質

當問題的最優解包含著其子問題的最優解時，稱該問題具有最優子結構性質。

二、重疊子問題性質

遞歸算法求解問題時，每次產生的子問題并不總是新問題，有些子問題被反復計算多次。這種性質稱為子問題的重疊性質。

其它同分治法。

動態規劃問題的特征：

求解的問題是組合優化問題；

求解過程需要多步判斷，從小到大依次求解；

子問題目標函數最優解之間存在依賴關系；

動態規劃算法設計的基本步驟和要素：

基本步驟：

（1）找出最優解的性質，并刻畫其結構特征。（考察是否適合采用動態規劃法。）

（2）遞歸地定義最優值。(建立遞歸式或動態規劃方程)

（3）以自底向上的方式（或以自頂向下的備忘錄方法）計算出最優值。

（4）根據計算最優值時得到的信息，構造最優解。

要素：

最優子結構

重疊子問題

備忘錄（表格）

應用實例分析：

1、矩陣連乘問題：

（1）分析最優解結構：

計算A[i:j]的最優次序所包含的計算矩陣子鏈 A[i:k]和A[k+1:j]的次序也是最優的。矩陣連乘計算次序問題的最優解包含著其子問題的最優解，滿足最優子結構性質。問題的最優子結構性質是該問題可用動態規劃算法求解的顯著特征。

（2）建立遞歸關系；

（3）計算最優值—遞歸求解（遞歸求解最優值復雜度較高的原因是：子問題重復度高)；計算最優值—迭代查表求解

計算最優值—備忘錄求解

（4）構造最優解

第四章貪心法

貪心算法的基本思想：

當一個問題具有最優子結構性質時，可用動態規劃方法求解，但有時會有更簡單有效的方法。

顧名思義，貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。

貪心算法不能對所有問題都得到整體最優解，但對許多問題它能產生整體最優解。在一些情況下，即使貪心算法不能得到整體最優解，其最終結果卻是最優解的很好近似。貪心算法中，較大子問題的解恰好包含了較小子問題的解作為子集，這與動態規劃算法設計中的優化原則本質上是一致的。

動態規劃算法在某一步決定優化函數的最大或最小值時，需要考慮到它的所有子問題的優化函數值，然后從中選出最優的結果；貪心算法的每步判斷時，不考慮子問題的計算結果，而是根據當時情況采取“只顧眼前”的貪心策略決定取舍。

貪心算法的設計要素：

可以用貪心算法求解的問題一般具有2個重要的性質：

1、最優子結構性質：

當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。問題的最優子結構性質是該問題可用動態規劃算法或貪心算法求解的關鍵特征

2、貪心選擇性質：

貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這是貪心算法與動態規劃算法的主要區別。

動態規劃算法通常以自底向上的方式求解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規模更小的子問題。

對于一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優解。

應用實例：

1、活動安排問題：

第五章回溯法

回溯法的基本思想：

回溯法的使用條件：

回溯法適用于搜索問題和優化問題。

回溯法的設計要素：

針對問題定義解空間：

問題解向量

解向量分量取值集合構造解空間樹

兩類典型的解空間樹：

子集樹：當所給的問題是從n個元素的集合S中找出滿足某種性質的子集時，相應的解空間樹稱為子集樹。子集樹通常有2n個葉結點

排列樹：當所給的問題是確定n個元素滿足某種性質的排列時，相應的解空間樹稱為排列樹。排列樹通常有n!個葉結點。

判斷問題是否滿足多米諾性質。

搜索解空間樹，確定剪枝函數。

確定存儲搜索路徑的數據結構。

第六章分支限界法

分支限界法的基本思想：

分支界限法類似與回溯法，也是在問題解空間中搜索問題解的一種算法。

分支界限法與回溯法思想對比：

求解目標：回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優解。

搜索方式的不同：回溯法以深度優先的方式搜索解空間樹，而分支限界法則以廣度優先或以最小耗費優先的方式搜索解空間樹。

在分支限界法中，每一個活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一次性產生其所有兒子結點。在這些兒子結點中，導致不可行解或導致非最優解的兒子結點被舍棄，其余兒子結點被加入活結點表中。

此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續到找到所需的解或活結點表為空時為止。

常見的兩種分支界限法：

隊列式(FIFO)分支限界法：按照隊列先進先出（FIFO）原則選取下一個節點為擴展節點。

優先隊列式分支限界法：按照優先隊列中規定的優先級選取優先級最高的節點成為當前擴展節點。

最大堆：最大效益優先

最小堆：最小耗費優先