有很多問題初看很棘手，但經過仔細的分析，可以得出一些顯然的結論。

比如下面這個問題： 平面內有上千個點，用一個半徑為R的圓去覆蓋，最多能覆蓋多少點？

很多程序員最暴力的思想就是枚舉，當然，利用計算機枚舉確實是一種很有效的方法，特別是在數據很小的情況下，不過對于上述問題，如何枚舉？枚舉圓的位置嗎？

確實可以枚舉圓的位置，如果不經過思考的話可以再二維正交系內枚舉每個點為圓心，然后判斷這個圓能覆蓋多少圓，最后結果取最大。這個確實是一種方法，不過枚舉圓心如何操作？圓心的位置是連續的，不一定是整點這種離散位置。 在數據量小并且精度要求不高的情況下，直接枚舉圓心位置不失為一種好方法。 不過稍微分析一下，可以得出這樣一個結論，最優解的圓，也就是覆蓋點最短的R半徑圓，圓上一定有2個點。

假設最優解的圓上沒有2個點，如上圖，那么通過微量的平移操作，可以使圓接觸平面上的2個點，并且園內的點數不會減少，它的結果不會比圓上沒有2個點的情況差，因為只要求最多覆蓋多少點，我們可以枚舉任意2個點，這樣這個半徑為R的圓的位置就確定了（在這2點中垂線上，2中情況），再判斷下這個圓能覆蓋多少點，兩兩點枚舉后取最大，這是一個O(n^3)的算法，1秒內出結果，已經比較高效了。

所以很多時候我們可以分析出最優解是滿足哪種情況的，然后利用計算機特性枚舉最優解，逆向思維解決問題。

2.動態規劃思想

  動態規劃是一種非常高效的方法，這個編程里面非常非常常見的，不會搜索和動態規劃，基本就不會編程。如果能夠把一個大的問題劃分成若干同類型的小問題，小問題又可以劃分為更小的問題，直到問題程度小到一眼就能看出來。 這樣的例子相當多，著名的快速排序就是這種思想，而且利用遞歸的寫法，很容易實現這種思想。 經典的動態規劃還有很多，最長上升子序列，背包問題等等。

如果還有同學不明白動態規劃，看下面這一段C語言代碼，相信能體會到一些。

/****************** 
Author: lxgsbqylbk 
Function : Get the factorial of integer n (n>=0) 
n!= 
1   n==0 
n*(n-1)!  n>0 
****/ 
int F(int n) 
{ 
    return n?n*F(n-1):1; 
} 

3.排序思想

  排序是一個很重要的步驟，有很多問題通過排序預處理后可以更加方便的解決，比如有很多張鈔票，面值不同，從中選出m張使它們價值最大，一個做法當然是對著些鈔票按照面值從大到小排序，然后取錢m張就行了。 很多時候，上述的動態規劃需要對變量按照一定規則排序后才能操作，有一定順序了之后，問題一般更容易解決。

  說到排序，不得不說到貪心算法。 貪心算法就是如果整個大問題要到達一個最優解，在構成大問題的小問題中每次取最優的，大問題就能到達最優情況，當然，這種策略需要經過證明正確性后才能實現。 很多貪心過程前也要有排序的工作，比如著名的Kruscal最小生成樹算法，要先對邊進行排序，所以排序是個很重要的過程，以至于它被收錄到各種語言的庫函數中，可以方便的被用戶調用。

4.二分，三分。

前幾天聽同學說，現在8K已經招不到會寫二分的程序員了，當然這句話有夸張的成分啦，^-^ 可見二分在程序設計中的常用性。

其實這個可以并列到枚舉算法那中，只是這種枚舉效率很高，很多地方比如SQL數據庫里面的查找方式就是二分，二分枚舉，三分枚舉，時間復雜度都是對數級的，在程序設計中是相當高效的算法。

二分的條件：數據的單調性。 比如在一組從小到大排序的數中尋找數x 這樣就可以二分枚舉 每次可以把范圍縮小一半，無論數據多大，就算超出int類型，都能很快找出來。

比如求函數8*x^4 + 7*x^3 + 2*x^2 + 3*x + 6 == K 在區間[0,100]的解 由于這個函數在[0,100]是單調遞增的，所以二分是個不錯的選擇。

三分的條件: 數據的有凸性。

比如求函數6*x^7 + 8*x^6 + 7*x^3 + 5*x^2 - K*x 在區間[0,100]的最小值

這個函數在[0,100]是一個先減后增(或者完全單調，主要看K)的函數，所以三分求解。

當然這個問題可以轉換為二分，將函數求導，二分其在0的位置即可，這個涉及到高等數學，不贅述了。

具體過程可以去查資料 二分前一般也需要排序操作的。

5.隨機算法

很多時候在要解決的問題沒有任何思路，枚舉數據量又太大的情況下，可以使用一些隨機算法。

  常見的隨機算法，蟻群算法，模擬退火等等。

  簡單說說模擬退火（后面我打算專門寫一篇模擬退火的隨筆）

  比如平面內有成千上萬個點，要在平面選一個圓，覆蓋所有點，問最小的半徑是多少？

第一次接觸這個問題的時候我有想到一種做法（不敢保證正確）：

  根據1 還是可以得出結論，最優情況圓上面一定有2個點，否則的話可以把圓繼續縮小平移，使它上面有2個點，結果更優。

所以枚舉任意2個點，圓心一定在這2點中垂線上，這里是對的。 然后假設這個圓心在在中垂線上移動，如果滿足要求，包圍了所有點。

那么我猜測這個圓在移動過程中半徑先減小后增大。(感覺而已，未證明，也未測試，太麻煩了。) 這里可以使用上述的三分枚舉，因為半徑函數是下凸性的。

我上面這個方法正確性先不說，復雜度是有一點的，枚舉2點，再三分。O(n^2*logV) 當然，數據很小的情況下，比如只有幾千個點的話，結果秒出，數據大了，效率降低了。

這里說一下模擬退火的思想。 大概依照一個這樣的理論，假設現在有1個位置pos,如果最優解圓心位置在pos上面，那么如果往pos下面搜，搜到的圓心一定比在pos的位置時候大。

依照這個理論，我們就可以現在平面內隨機生成一些點，然后貪心的隨機移動它們，直到達到一定程度停止。這個算法在時間復雜度上是O(n)的 正確性很高，運行也相當的快。

6.最后一個問題轉化

  有的時候遇到問題，不能立即想出策略，這個時候嘗試下將這個問題轉化為常見的模型，利用常見模型和經典的算法解決它。

  最常見的還是一些圖論上的問題，將實際問題轉化為流網絡或者二分圖。

原文鏈接：http://www.cnblogs.com/lxglbk/archive/2012/08/22/2650125.html

【編輯推薦】