百度2014校招笔试题（一）

算法和程序设计题：

1 题意：

一幢大楼的底层有1001根电线，这些电线一直延伸到大楼楼顶，你需要确定底层的1001个线头和楼顶的1001次线头的对应关系。你有一个电池，一个灯泡，和许多很短的电线，你需要上下楼几次才能确定电线接头的对应关系：

2 解答：

注明：这里每次上下楼都带着电池和灯泡，以及每次接口连接，对应接口的之前连接过的线都将拆除，所以下面不再说明。

首先将底层一对接口（这里假设为（buttom1，buttom2））连接起来，然后上楼，根据提供的电池和灯泡的亮灭，确定顶层的一对（这里假设为（top1，top2）），接着将顶层的另一对连接起来（假设为（top3，top4）），然后下底层，确定和（top3，top4）对应的一对（假设为（buttom3，buttom4）），然后将底层的 buttom1和buttom3连接，底层的buttom2和buttom4连接，上楼，分别将确定过的两对交换对接，即依次测试（top1，top4），（top2，top3）或者（top1，top3),(top2,top4)，直接灯泡亮为止即可确定这四个接口的对接关系。这样第一次确定4个接口需要上下楼3次。

然后根据第一次确定的4个接口，在顶层分别和剩余的接口中的其中四个接口连接，下到底层，和第一次确定四个接口一样，即可确定8个接口。这时确定8根只需要在上面的基础上加1次就可以。接下来就可以确定16个接口，并以此指数增加，从而到2的10次方，即1024，即可全部确定1001个接口，而从2的3次方到2的10次方，共8次.

最后得出第一次确定的3次加上接下来的8次，共需11次即可确定他们的对应关系。

1楼wq19901103wq昨天 23:44

十次的解答：方便描述，不妨设有1024个线头，给楼下电线进行编码，分成5位二进制编码，每种编码有32个线头，（2^5=32,32*32=1024），称为A编码，楼上一样，称为B编码，楼下A编码确定而B编码不确定，楼上相反n第一次上楼前将楼下A编码首位为1的电线头相互链接(两两一组)，然后上楼，对楼上灯泡遍历，凡是曾连有某灯泡并且亮着的线头的A编码首位设为1，其余设为0，然后把所有线拆掉，将楼上B编码首位为1的电线头相互链接。n第二次，下楼，对楼下灯泡遍历，凡是曾连有某灯泡并且亮着的线头的B编码首位设为1，其余设为0，然后把所有线拆掉，将楼上B编码第二位为1的电线头相互链接。n以此类推，上楼5次下楼5次确定所有的A编码和B编码，楼上楼下AB编码均相同的即为对应关系