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