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