考虑n位二进制数，有多少个数中不存在两个相邻的1

考虑n位二进制数，有多少个数中不存在两个相邻的1

一、二进制数模式考虑n位二进制数，有多少个数中不存在两个相邻的1。例如，3位数中有5个数符合这一要求：000、001、010、100、101。

　　1、试找出其中的规律

　　2、请给出完整代码实现(参数输入代码可略)

　　3、试证明你找到的规律是正确的

　　二、对象速查表假设需要实现一个对象速查表，具体的要求如下：

　　1.该表中将保存大量(几千万个)对象地址(指针)，以下称为记录

　　2.支持频繁查询一个指针是否记录在表中3.支持频繁添加和删除记录请尝试给出几种可能的实现方式，并对其运行效率作出比较。对你认为最优的方案给出主要部分伪代码。

　　三、迷宫给定一个迷宫，它除了墙之外，还有门和钥匙。其中，钥匙和门放在不同的地方，并为双射关系(一扇门只对应一把钥匙，反之亦同)。

　　1、给定一个没有门的迷宫，以及起点和终点，请给出最短路径;

　　2、给定有门和钥匙的迷宫、起点和终点，请给出一条路径;

　　3、给定有门和钥匙的迷宫、起点和终点，请给出最短路径;请给出上述算法思路，和主要部分伪代码。

　　四、软件设计

　　请从以下几个命题中任选一个，以自己熟悉的方式给出该软件的尽可能详细的设计： 

　　类似Winzip的压缩软件(压缩算法不需要设计) 

　　一个简单的绘图程序(类似Windows画笔)

　　一个多线程下载客户端(协议可以使用HTTP/FTP或自拟)