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。
……
阅读全文