用動態規劃解決問題:零壹背包問題(0/1 Knapsack Problem) 2020 年 8 月 4 日 Magic Len 研究分享、Go、Java、NodeJS、Rust、演算法 一個背著背包的小偷闖空門偷東西,他必須趁屋主回來之前把有價值的物品塞進包包內帶走。考慮到小偷自身的行動力,背包能裝的物品總重量有限,小偷要如何選擇物品才能獲得最高的總價值? 繼續閱讀 01背包問題、Dynamic Programming、Knapsack、動態規劃、背包問題、零壹背包問題
用動態規劃解決問題:找零錢問題(Coin Change Problem) 2020 年 7 月 28 日 Magic Len 研究分享、Go、Java、NodeJS、Rust、演算法 許多人認為身上如果帶太多的零錢會讓行動變得不方便,因此會希望商店店員在找零錢的時候能夠以最少的硬幣數來找,而不是全部都用1元塞給我們。 繼續閱讀 Dynamic Programming、動態規劃、找零錢問題
用動態規劃解決問題:基本觀念(有重疊子問題的問題) 2020 年 7 月 21 日 Magic Len 研究分享、Go、Java、NodeJS、Rust、演算法 動態規劃(Dynamic Programming,簡稱DP)是一種解決問題的技巧,主要被用來優化那些「記不住自己過去曾解出來的答案所以只好重複再解」的演算法,讓它們可以「記憶」已經找出來的答案,從而不斷利用,以大大降低時間複雜度(從指數級降到線性)。 繼續閱讀 Dynamic Programming、動態規劃、爬樓梯問題、買東西問題、費氏數列、貼磁磚問題、重疊子問題
如何用程式進行質因數分解和尋找最大公因數與最小公倍數? 2020 年 7 月 9 日 Magic Len 研究分享、Go、Java、NodeJS、數學邏輯、Rust、演算法 若正整數a除以正整數b可以整除,則稱b為a的因數(Factor),a為b的倍數(Multiple),1是所有正整數最小的因數,任意正整數最大的因數就是該正整數本身。若a同時是x和y的因數,則稱a是x和y的公因數(Common Divisor),如果a是x和y的公因數中最大的一個,則稱a是x和y的最大公因數(Greatest Common Divisor,簡稱GCD)。若a同時是x和y的倍數,則稱a... 繼續閱讀 Binary GCD algorithm、Euclidean algorithm、二元GCD演算法、最大公因數、最小公倍數、歐幾里得演算法、質因數分解、輾轉相除法
電腦是怎麼進行四則運算的?前序式、中序式、後序式又是什麼? 2020 年 6 月 18 日 Magic Len 研究分享、Go、Java、NodeJS、Rust、演算法 我們從小學習算術的時候便知道「四則(加、減、乘、除)運算」的規則,也就是「先乘除、後加減,以及括號先算」。那麼如果我們要撰寫一個可以支援算式輸入且能夠按照四則運算規則求出結果的程式,該怎麼做呢? 繼續閱讀 Normal Polish Notation、Polish Notation、Reverse Polish Notation、中序式、前序式、四則運算、後序式、深度優先搜尋
費氏搜尋(Fibonacci Search)演算法,運用費氏數列的搜尋演算法 2020 年 5 月 28 日 Magic Len 研究分享、Go、Java、NodeJS、Rust、演算法 費氏搜尋(Fibonacci Search)演算法有點像是二元搜尋(Binary Search)演算法,同樣是在一個已排序好的陣列中搜尋元素,但是它在移動陣列索引值時是去參考費氏數列(Fibonacci Sequence),而不是像二元搜尋法那樣總是去取索引的中間值。也由於費氏搜尋法在移動陣列索引值時只需要進行加減運算,不需乘、除法,因此它適合被用在不擅長處理乘、除法的CPU上。 繼續閱讀 Fibonacci Search、Search Algorithm、二元搜尋樹、搜尋演算法、費布那西搜尋法、費氏搜尋、費氏數、費氏數列、費氏樹
深度優先搜尋(DFS)和廣度優先搜尋(BFS)演算法,實用的節點搜尋法 2019 年 10 月 10 日 Magic Len 研究分享、Rust、演算法 圖(graph)是由節點(node)和邊(edge)組合而成的非線性結構,如果我們想要從其中的一個節點開始,走訪到其有直接或是間接連接的其它所有節點,可以依靠深度優先搜尋法(DFS, Depth-first Search)或是廣度優先搜尋法(BFS, Breadth-first Search)來達成。 繼續閱讀 BFS、Breadth-first Search、DFS、Depth-first Search、Search Algorithm、廣度優先搜尋、搜尋演算法、深度優先搜尋
基數排序(Radix Sort)演算法,可以依據多個鍵值來排序的演算法 2019 年 5 月 30 日 Magic Len 研究分享、Go、Java、NodeJS、Rust、演算法 基數排序(Radix Sort)演算法是可以利用多個鍵值來排序資料的演算法。排序還需要多個鍵值?有時候當然會需要啦!像是要排序檔案時,可以先依照檔案名稱排序後,再依照檔案大小來排,如此一來,整體上來看這些檔案,會是以檔案大小來排序,而相同檔案大小的檔案則是會依照檔案名稱來排序。基數排序法可以將整數的各個位數當作是鍵值,來進行線性時間的排序,比起會依照k(要排序的資料可能的值的數量)愈大而愈吃空間的... 繼續閱讀 Radix Sort、Sorting Algorithm、基數排序、排序演算法
桶排序(Bucket Sort)演算法,利用運算式將資料分類、排序後,再合併起來的排序演算法 2019 年 5 月 26 日 Magic Len 研究分享、Go、Java、NodeJS、Rust、演算法 桶排序(Bucket Sort)演算法是先將大量資料分類成少量資料後,再進行排序的演算法。可以透過簡單的運算式來完成資料的分類,在最好的情況之下,資料可以被完全打散,此時的時間複雜度就會是一個線性時間。 繼續閱讀 Bucket Sort、Sorting Algorithm、排序演算法、桶排序
寫程式的基本功:搜尋演算法(Search Algorithm) 2019 年 5 月 22 日 Magic Len 研究分享、演算法 這裡所稱的搜尋(Search),是指在一個已排序好或是尚未排序好的集合中,將指定元素的鍵值(key)或是索引值(index)搜尋出來,或者是給定某個條件,在集合中搜索出符合該條件的資料。在集合內搜尋元素的方法當然不會只有一種,而不同方法搜尋資料的難易度、速度和其它特性自然也會有所不同。搜尋演算法(Search Algorithm)就是搜尋資料的方法,目前已知的方法有很多,在這篇文章中將會整理本站所... 繼續閱讀 Search Algorithm、字串搜尋、字串搜尋演算法、寫程式的基本功、搜尋演算法