有两道算法题，求思路

liyaobin1234

1.进制数模式
考虑n位二进制数，有多少个数中不存在两个相邻的1。例如，3位数中有5个数符合这一要求：000、001、010、100、101。
1、试找出其中的规律
2、请给出完整代码实现（参数输入代码可略）
3、试证明你找到的规律是正确的

2.对象速查表
假设需要实现一个对象速查表，具体的要求如下：
1.        该表中将保存大量（几千万个）对象地址（指针），以下称为记录
2.        支持频繁查询一个指针是否记录在表中
3.        支持频繁添加和删除记录
请尝试给出几种可能的实现方式，并对其运行效率作出比较。对你认为最优的方案给出主要部分伪代码。

liyaobin1234

求思路啊

gaoping561

对n位二进制数，设所求结果为a(n),对于第n位的值，分为0或者1两种情况：
（1）第n位为0，则有a(n-1)个数
（2）第n位为1，则要满足没有两个相邻位为1的条件，第n-1位为0，有a(n-2)个数
因此，得到结论
    a(n) = a(n-1) + a(n-2)
即满足斐波那契数列的条件。

shimmey

回复 1# liyaobin1234


    第一题gaoping561的回答非常准确
   关于第二题么, 如果对象可以方便计算Hash, 可以寻找一个比较好的Hash值算法来将这些对象指针放到一个数组里面
有相同Hash的就用链表实现. 这样实现的效率取决于Hash算法
   如果不好算Hash的话, 就只能用二叉树实现了. 这样做需要先将那些对象进行排序, 建立一个二叉树.
通过调整树的形状来提高查找与添加, 删除的效率. 这基本上就是自己做个数据库存储算法了. 觉得难度比较大一些

A.com

第一题已经有标准答案了，第二题的话，不知道对象是固定的还是动态的。如果是固定的，一个数组就解决了。
假设是动态的，譬如论坛的在线用户。实现上用数据库才是最简便的。不过既然是考算法，那就复杂了，整个数据库的设计和优化呢。

我说这第二题出的，也太大而无当了吧。

bleakxanadu

第二题用位图。一亿个对象的指针，可以完美地1-1映射到[0, 10e8]中，空间近似10e8 div 8 div 10e6，只占用10+兆空间。

L_kernel

第一个若仅仅是求得个数。这样子就可以了。2^n - (n-1 + n-2 + n-3 + ... + n-n)