Hash
摘要: Hashing定義了一種將字符組成的字符串轉換為固定長度(一般是更短長度)的數值或索引值的方法，稱為散列法，也叫哈希法。由于通過更短的哈希值比用原始值進行數據庫搜索更快，這種方法一般用來在數據庫中建立索引并進行搜索，同時還用在各種解密算法中。
設所有可能出現的關鍵字集合記為U(簡稱全集)。實際發生(即實際存儲)的關鍵字集合記為K（|K|比|U|小得多）。|K|是集合K中元素的個數。
散列方法是使用函數hash將U映射到表T[0..m-1]的下標上（m=O(|U|)）。這樣以U中關鍵字為自變量，以h為函數的運算結果就是相應結點的存儲地址。從而達到在O(1)時間內就可完成查找。
……
閱讀全文
質數判斷算法
摘要: 有人做過這樣的驗算：1^2+1+41=43,2^2+2+41=47,3^2+3+41=53……于是就可以有這樣一個公式：設一正數為n，則n^2+n+41的值一定是一個質數。這個式子一直到n=39時，都是成立的。但n=40時，其式子就不成立了，因為40^2+40+41=1681=41*41。
研究發現質數除2以外都是奇數，而奇數除了【奇數*奇數】(或再加“*奇數”）都是質數。那么用計算機先把【奇數*奇數】(或再加“*奇數”）（比如9，15，21，25，27，33，35，39……）都求出來，再找奇數中上面沒提到的那些數，那些數就是素數。
有近似公式： x 以內質數個數約等于 x / ln(x) .ln是自然對數的意思。準確的質數公式尚未給出。10 以內共 4 個質數。100 以內共 25 個質數。
……
閱讀全文
計算二進制位"1"的個數
摘要: 寫一個函數，返回數字中二進制位為'1'的個數。
方法1：分別判斷各個位
方法2：循環中直接計算1的數量
方法3：并行計算的
PS：
這些方法是計算二進制形式1的個數，如果用來判斷一個數是否是2的整數次冪，可以用這些方法，但是對此還有更好的方法，就是 A xor (A-1) == 0。
閱讀全文
01背包問題的貪婪算法
摘要: 0/1背包問題有好幾種貪婪策略，每個貪婪策略都采用多步過程來完成背包的裝入，在每一步過程中利用貪婪準則選擇一個物品裝入背包。
1、從剩余的物品中，選出可以裝入背包的價值最大的物品。利用這種規則，價值最大的物品首先被裝入（假設有足夠容量），然后是下一個價值最大的物品，如此繼續下去。這種策略不能保證得到最優解。例如，n=2, weight=[100, 10, 10], prize=[20, 15, 15], count=105。當利用價值貪婪準則時，獲得的解為x= [1, 0, 0]，這種方案的總價值為20。而最優解為[0, 1, 1]，其總價值為30。
……
閱讀全文