八皇后問題可以說是一道相當經典的演算法題目,以西洋棋為背景,如何在一個8x8的棋盤上擺放八個皇后的棋子,讓任何一個皇后無法吃掉其中一個皇后,也是就是任何一個皇后的橫行、縱行、斜線上都不會出現其它的皇后,後來八皇后問題也被衍生為N皇后問題…
Dynamic Programmin的經典應用除了斐波那契數之外,還有背包問題、最短路徑問題、河內塔、LCS等等,那麼我們就試著用Dynamic Programming來解…
在認識動態規劃之前先來理解Divide and Conquer(分治法)吧!Divide and Conquer是一種演算法,執行的步驟如下
回溯法是暴力破解法的一種,在列出各種可能的組合時,如果遇到不符合條件的就不再繼續向下查找,而是回到上層繼續尋找其他可能,聽起來有點抽象,可以想像有很多條岔路可以做選擇,不過已經知道有些岔路不會得到我們需要的結果,就沒有必要繼續往下找,而是折返到上個路口…
利用將資料切一半的方式來做搜尋,舉例來說,如果要從數字1–100猜終極密碼,如果採用線性搜尋法就是一個一個問?是1嗎?是2嗎?…依序猜下去,很不幸的數字剛好是99就需要猜99次,但如果用二分搜尋法就會是先判斷數字是否大於50…
貪婪演算法(英語:greedy algorithm),又稱貪心演算法,是一種在每一步選擇中都採取在當前狀態下最好或最佳(即最有利)的選擇,從而希望導致結果是最好或最佳的演算法。(引用自wikipedia)
線性搜尋法可以說是最容易理解的搜尋演算法了, 相信大家都有過類似的經驗在圖書館想在在書架上要找一本書"湯姆歷險記"…
列舉法又稱為窮舉法,簡單來說就是把所有可能發生的狀況都列出來,再根據問題提供的條件,從中找出符合條件的解答,也就是所謂的暴力破解法,優點是簡單直觀,缺點就是當問題的範圍很廣,執行時間會等比上升,因此不適合拿來解範圍過於廣泛的題目。
heap sort的原理是採用max heap這種資料結構來做排序,max heap是一種binary tree,每個節點都會比自己的子節點還大,因此根節點會是最大值,讓我們先來理解如何實作一個max…
Merge Sort採用分治法(Divide and Conquer)的方式來處理排序的問題,簡單介紹一下分治法執行的步驟如下: