第三章-蠻力法課件

算法分析與設計

AnalysisandDesignofComputerAlgorithms第三章蠻力法BruteForce.蠻力法就像寶劍不是撬棍一樣，科學也很少使用蠻力?！狤dwardLytton認真做事常常是浪費時間?！猂obertByrne蠻力法是一種簡單直接地解決問題的方法，常常直接基于問題的描述和所涉及的概念定義。

2.蠻力法的優(yōu)點可以用來解決廣闊領域的問題對于一些重要的問題，它可以產生一些合理的算法解決問題的實例很少時，它讓你花費較少的代價可以解決一些小規(guī)模的問題可以作為其他高效算法的衡量標準3.教學內容選擇排序和冒泡排序順序查找和蠻力字符串匹配最近對核凸包問題的蠻力算法窮舉查找要求掌握蠻力法的基本思想，了解排序和查找問題的蠻力算法。

4.選擇排序A[min]

5.冒泡排序算法BubbleSort(A[0..n-1])//該算法用冒泡排序對數(shù)組A[0..n-1]排序//輸入：一個可排序的數(shù)組A//輸出：非降序排列的數(shù)組fori0ton-2doforj0ton-2-idoifA[j+1]<A[j]swapA[j]andA[j+1]

6.順序查找

7.蠻力字符串匹配

8.蠻力字符串匹配Θ(n+m)=Θ(n)

9.最近對問題

10.凸包問題定義對于平面上的一個點集合（有限或無限），如果以集合中任意兩點P和Q為端點的線段都屬于這個集合，則這個集合是凸的。定義一個點集合S的凸包是包含S的最小凸集合。

11.凸包問題定理任意包含n>2個點（不共線）的集合S的凸包是以S中的某些點為頂點的凸多邊形。凸包問題是為一個n個點的集合構造凸包的問題。極點：對于任何一集合中的點為端點的線段來說，它們不是這種線段的中點。對于一個n個點集合中的兩個點Pi和Pj，當且僅當該集合中的其他點都位于穿過這兩點的直線的同一邊時它們的連線是該集合凸包邊界的一部分。直線方程：ax+by=ca=y2-y1,b=x1-x2,c=x1y2-y1x2

12.窮舉查找旅行商問題

13.窮舉查找背包問題

14.窮舉查找分配問題N個任務分配給n個人，任務j分配給人i的成本是C[I,j]

15.小結蠻力法是一種簡單直接地解決問題的方法，通常直接基于問題的描述和所涉及的概念定義。蠻力法的主要優(yōu)點是它廣泛的適用性和簡單性；它的主要缺點是大多數(shù)蠻力算法的效率都不高。除了相關問題的一些規(guī)模非常小的實例，窮舉查找法幾乎是不實用的。

16.習題3.2-10找詞游戲.習題3.2-11海戰(zhàn)游戲.習題3.4-9幻方幻方是我國古代的一種智力游戲，它是在N×N的矩陣方格中填入1...N2

的正整數(shù)，使得其每行每列及對角線的和相等。很明顯，這個和對某一階幻方是一個定值。設此值為SN，則不難解出：SN=

N2·(N2+1)/2N=N·(N2+1)/2。.外延法(由巴謝提出)構造奇階幻方.H·Coxeter構造幻方的方法首先在正方形最上面一行的正中間的小方格內填寫1，然后到它的左上方的小格內填寫下一個數(shù)(