IT思想类智力题

时间:2022-05-01 19:19:14

1、 台阶问题

题目:一个人上台阶可以一次上一个或两个,问这个人上n层的台阶,一共有多少种走法。

本题可以采用递归的方法来设计模型,先从数字的规律入手:假设共有i阶台阶,走完所有的台阶有n种走法,则存在如表6- 3所示。

表6- 3组合情况

i n 组合情况
1 1 {1}
2 2 {1, 1}{2}
 3  3 {1, 1, 1}{1, 2}

{2, 1}

4

5

{1, 1, 1, 1}{1, 1, 2}

{1, 2, 1}

{2, 1, 1}

{2, 2}

n-2 F(n-2)  
n-1 F(n-1)  
n F(n)= F(n-1)+ F(n-2)  

根据递推可以知道,F(n)= F(n-1)+ F(n-2)。此式很熟悉,为常见的Fibonacci数列,此处不再赘述其求解算法。

2、 电线线头问题

题目:在一幢100层大楼下,有21根电线线头分别标有数字1到21。这些电线一直延伸到大楼楼顶,楼顶的线头处标有字母A到U,一共21个字母。此时不知道下面的数字和上面的字母的对应关系,有一个电池,一个灯泡,和许多很短的电线,如何只上下楼一次就能确定电线线头的对应关系?

在下面把2,3连在一起,把4到6全连在一起,把7到10全连在一起,等等,这样就把电线分成了6个“等价类”,大小分别为1,2,3,4,5,6。然后爬到楼顶,测出哪根线和其它所有电线都不相连,哪些线和另外一根相连,哪些线和另外两根相连等等,从而确定出字母A到U各属于哪个等价类。

然后把每个等价类中的第一个字母连在一起,形成一个大小为6的新等价类;再把后5个等价类中的第二个字母连在一起,形成一个大小为5的新等价类;以此类推。再回到楼下,把新的等价类区别出来。此时就知道了每个数字对应了哪一个原等价类的第几个字母,从而解决问题。

3、 蚂蚁相撞问题

题目:在一个等边三角形的三个顶点上各有一只蚂蚁,它们向另一个顶点运动,目标随机(可能为另外两个顶点的任意一个)。问三只蚂蚁不相撞的概率是多少?

1/4。

先取三只蚂蚁中任意一只做研究,它的行动路线可以向另外两个顶点的任意一个移动,然后取第二只蚂蚁,为了要使三只蚂蚁互不相撞,它必须不能与第一只蚂蚁相向而行,所以只有1种行动路线,而它总共有两条线路可供选择,所以它们互不相撞的可能性是1/2。最后取第三只蚂蚁,前面两只蚂蚁的路线都确定好以后,它只能从可选的两条路里面走唯一一条使它们互不相撞的路线,也就是3个蚂蚁做相同方向的绕圈运动,而第三只蚂蚁为了它们互不相撞,选择路线的可能性也是1/2。所以三只蚂蚁不相撞的概率是1/2*1/2=1/4。

还可以换一种思维来进行,以二进制中的0和1来表示蚂蚁的爬行方向,蚂蚁顺时针爬行记为0,逆时针爬行记为1,那么三只蚂蚁的状态可能为000,001,……,110,111 中的任意一个,而且每种状态的概率相等,而在这8种状态中,只有000和111表示可以避免相撞,所以蚂蚁不相撞的概率为1/4。

4、 小老鼠与毒酒问题

题目:有1000桶酒,其中只有1桶有毒,而一旦喝了有毒的酒,毒性就会在1周后发作,现在用小老鼠做实验,要在1周内找出那桶毒酒,问最少需要多少只小老鼠。

10只。因为2的10次方等于1024,所以10只小老鼠最多可以测1024桶酒。

先假设有1024个瓶子,其中只有1瓶毒药。

(1)       将1024个瓶子分成两个512,即512a和512b。从512a的各瓶中,各取1滴水,给1号小老鼠吃。

(2)       将两个512分别分成两个256,即,512a分成了256a、256b,并且512b也分成了256a、256b。从两个256a中,照旧每瓶取一滴,给2号小老鼠吃。

(3)       同样的道理,依次分为4个128a、128b,将a各取一滴,给3号小老鼠吃。

(4)       8个64a、64b,将a各取一滴,给4号小老鼠吃。

(5)       16个32a、32b,将a各取一滴,给5号小老鼠吃。

(6)       32个16a、16b,将a各取一滴,给6号小老鼠吃。

(7)       64个8a、8b,将a各取一滴,给7号小老鼠吃。

(8)       128个4a、4b,将a各取一滴,给8号小老鼠吃。

(9)       256个2a、2b,将a各取一滴,给9号小老鼠吃。

(10)   512个1a、1b,将a各取一滴,给10号小老鼠吃。

然后,经过一周的等待,则可以得出如下结论:

(1)       如果1号小老鼠死,则毒药在512a中;否则,在512b中。

(2)       如果2号小老鼠死,则在256a中;否则,在256b中;同时,根据1的结果,可判定这个256来自512a还是512b。

以此类推,可以唯一地确定这个“1”来自哪里,也就确定了它是第几瓶。

除了以上这种方法外,还可以采用另外一种方法,就是二进制表示的方法,首先,将酒编号为1~1000号,然后将十只小老鼠分别编号为1、2、4、8、16、32、64、128、256、512。

给小老鼠喂酒时,让酒的编号等于小老鼠编号的加和,例如:17号酒喂给1号和16号小老鼠 ,76号酒喂给4号、8号和64号小老鼠,七天后将死掉的小老鼠编号加起来,得到的编号就是有毒的那桶酒。因为对于任何一个小于1024的数,都可以采用前面的唯一一组二进制数(例如:01,10,100,1000,……,1000000000)来表示,所以结论成立。

5、 糖水问题

题目:有5杯水,其中有一杯是糖水,再给你一个空杯子,设计一种方案最多只尝三次,找出这杯糖水。

此题可以使用类似于二分查找的方法进行解答。首先选取其中的3杯水,都倒一点到空杯中,搅拌均匀,然后尝一下,此时杯中水的味道可能出现两种情况:有甜味与无甜味。

如果杯中水有甜味,则表明这3杯水中必有一杯是糖水,此时从这3杯水中选2杯,都到一点到空杯中,搅拌均匀,然后尝一下,如果没有甜味,那么没选中的那一杯就是糖水,如果有甜味,则品尝其中的一杯水就知道哪杯是糖水了。

如果杯中水没有甜味,那就尝一下没有选中的2杯水中的一杯,此时就知道哪杯是糖水了。

6、 握手问题

题目:一对夫妇邀请N-1对夫妇参加聚会(因此聚会上总共有2N人)。每个人都和所有自己不认识的人握了一次手。然后,男主人问其余所有人(共2N-1个人)各自都握了几次手,得到的答案全部都不一样。假设每个人都认识自己的配偶,那么女主人握了几次手?

由于聚会上一共有2N个人,每个人都和所有自己不认识的人握了一次手,所以女主人握手次数只可能是从0到2N-2这2N-1个数。除去男主人外,一共有2N-1个人,因此每个数恰好出现了一次。其中有一个人(0)没有握手,即握手次数为0,有一个人(2N-2)和所有其他的夫妇都握了手,即握手次数为2N-2,而这两个人肯定是一对夫妻,否则后者将和前者握手(从而前者的握手次数不再是0)。除去这对夫妻外,有一个人(1)只与(2N-2)握过手,有一个人(2N-3)和除了(0)以外的其它夫妇都握了手,这两个人肯定是一对夫妻,否则后者将和前者握手(从而前者的握手次数不再是1)。依此类推,直到握过N-2次手的人和握过N次手的人配成一对。此时,除了男主人及其配偶以外,其余所有人都已经配对。根据排除法,最后剩下来的那个握手次数为N-1的人就是女主人了。

7、 飞船处理器问题

题目:一个飞船上,飞船上的计算机有n个处理器。突然,飞船遭遇意外,一些处理器被损坏了。此时知道有超过一半的处理器仍然是好的,同时可以向一个处理器询问另一个处理器是好的还是坏的,好的处理器总是说真话,坏的处理器总是说假话,用n-2次询问找出一个好的处理器。

首先给处理器从1到n进行编号。用符号a->b表示向标号为a的处理器询问处理器b是不是好的。

然后执行1->2,如果1说不是,就把他们俩都去掉,因为如果1是好的,则2是坏的,如果1是坏的,则2是好的,所以能够保证两个处理器一个是好的,一个是坏的,去掉它们两,则剩下的处理器中好的仍然过半),然后从3->4开始继续发问。如果1说2是好的,就继续问2->3,3->4,……直到某一次j说j+1是坏的,把j和j+1去掉,然后问j-1 -> j+2;或者从j+2 -> j+3开始发问,如果前面已经没有j-1了(之前已经被去掉过了)。注意到整个推理过程,始终维护着一个类似于“链”的结构,即前面的每一个处理器都说后面那个是好的。这条链里的所有处理器要么都是好的,要么都是坏的。当这条链越来越长,剩下的处理器越来越少时,总有一个时候这条链超过了剩下的处理器的一半,此时可以肯定这条链里的所有处理器都是好的。或者,越来越多的处理器都被去掉了,链的长度依旧为0,而最后只剩下一个或两个处理器没被问过,那它们一定就是好的了。另外注意到,第一个处理器的好坏从来没被问过,因为最后一个处理器的好坏不可能被问到,因为一旦链长超过剩余处理器的一半,或者最后没被去掉的就只剩这一个了时,就不需要问了,因此询问次数不会超过n-2。

8、 机器人相遇问题

题目:有两个机器人,初始时位于数轴上的不同位置,如何给这两个机器人输入一段相同的程序,使得这两个机器人保证可以相遇。注意,程序只能包含“左移n个单位”、“右移n个单位”,条件判断语句if,循环语句while,以及两个返回Boolean值的函数“在自己的起点处”和“在对方的起点处”,不能使用其它的变量和计数器。

为了保证两个机器人可以相遇,可以将两个机器人刚开始同时以单位速度右移,直到一个机器人走到另外一个机器人的起点处,然后,该机器人以双倍速度追赶对方,这样两个机器人必能相遇。原理如下:假设两个机器人相距x个单元,标记位于左边的机器人为A,位于右边的机器人为B,当A向右移动x个单元到达B的起点处时,此时B也向右移动了x个单元,然后A以两倍的速度追赶元素B,假设花费t时间追赶上B,则满足等式:2*t=1*t+x,则t=x,则在距离B为2x的位置,A追赶上B。

转载:《程序员面试宝典》何昊