算法智力题
Nico Liao 阿蒙

原文请参见Li-Xiao-Hu的博客

[toc]

二进制问题

毒药问题

问题:有1000个一模一样的瓶子,其中有999瓶是普通的水,有1瓶是毒药。任何喝下毒药的生命都会在一星期之后死亡。现在你只有10只小白鼠和1个星期的时间,如何检验出哪个瓶子有毒药?

首先一共有1000瓶,2的10次方是1024,刚好大于1000, 也就是说,1000瓶药品可以使用10位二进制数就可以表示。

从第一个开始:

  • 第一瓶 : 00 0000 0001
  • 第二瓶 : 00 0000 0010
  • 第三瓶 : 00 0000 0011
  • ……
  • 第999瓶: 11 1111 0010
  • 第1000瓶:11 1111 0011

需要十只老鼠,如果按顺序编号,ABCDEFGHIJ分别代表从低位到高位每一个位。 每只老鼠对应一个二进制位,如果该位上的数字为1,则给老鼠喝瓶里的药。 观察,若死亡的老鼠编号为:ACFGJ,一共死去五只老鼠,则对应的编号为 10 0110 0101, 则有毒的药品为该编号的药品,转为十进制数为:613号。

分金块问题

问题:工人为老板打工,工作七天可以获得一块金子,工人每天可以分得一点金子,老板必须每天发金子,不能多给,也不能少给,把这个金子切两刀,就可以每天给工人发工资,请问怎么切?

切两刀将金子分成三份,1/7、2/7、4/7;

  • 工作第一天 把1/7分给工人;
  • 工作第二天 把2/7分给工人,并要回1/7那块金子,工人有2/7的金子;
  • 工作第三天 把1/7给工人 工人有3/7金子;
  • 工作第四天 把前两块金子要回,给工人4/7的金子 工人有4/7的金子;
  • 工作第五天 把1/7分给工人 工人有5/7的金子;
  • 工作第六天 把2/7分给工人,并要回1/7那块金子,工人有6/7的金子;
  • 工作第七天 把1/7给工人 工人有完整的金子;

扩展:如何给工人发15天的工资?把金块分成1/15、2/15、4/15、8/15。

先手必胜问题

抢 30的必胜策略

问题:抢 30 是双人游戏,游戏规则是:第一个人喊“ 1 ”或“ 2 ”,第二个人要接着往下喊一个或两个数,然后再轮到第一个人。两人轮流进行下去,最后喊 30 的人获胜,问喊数字的最佳策略。

  • 尽量喊3的倍数;

解析: 倒着看,其实,喊 27 时,就决定胜负了。

假设 A 喊了 27,B只能喊 28 或 29 , 下个回合,A 一定可以喊30。也就是说,喊 27 者必胜。

再倒着看,其实喊 24 时,就定胜负了。假设 A 喊了 24 ,B 只能喊 25 或 26 , 下个回合 A 一定能喊 27 。

由于喊 27 者必胜,因此喊 24 者也必胜。

同理可以推出:喊 3 的倍数者必胜。

然后就会发现,这个游戏,谁先喊,谁一定输

100本书,每次能够拿1~5本,怎么拿能保证最后一次是你拿?

如果最后一次是我拿,那么上回合最少剩下6本;

只要保持每个回合结束后都剩下6的倍数,且在这个回合中我拿的书和对方拿的书加起来为6本;

第一次我必须先手拿4本(100 % 6 = 4),这不算在第一回合内。

轮流拿石子

问题1:一共有N颗石子(或者其他乱七八糟的东西),每次最多取M颗最少取1颗,A,B轮流取,谁最后会获胜?(假设他们每次都取最优解)。

答案:简单的巴什博奕: https://www.cnblogs.com/StrayWolf/p/5396427.html

问题2:有若干堆石子,每堆石子的数量是有限的,二个人依次从这些石子堆中拿取任意的石子,至少一个(不能不取),最后一个拿光石子的人胜利。

答案:较复杂的尼姆博弈: https://blog.csdn.net/BBHHTT/article/details/80199541

推理题

掰巧克力问题

问题:一块N * M大小的巧克力,每次掰一块的一行或一列,全部掰成 1 * 1 大小的巧克力需要掰多少次?

  • N * M - 1次;

不管怎么掰,每次只能把一个大块掰成两个小块,即每次掰只能增加1块巧克力; 那么将1块巧克力掰成N * M块小巧克力就需要掰N * M - 1次。

辩论赛问题

问题:1000个人参加辩论赛,1对1进行辩论,淘汰输掉的一方,问需要安排多少场比赛才能角出冠军?

每场辩论赛只能淘汰一个人,要淘汰999个人则需要安排999场比赛。

在24小时里面时针分针秒针可以重合几次

24小时中时针走2圈,而分针走24圈,时针和分针重合24-2=22次, 而只要时针和分针重合,秒针一定有机会重合,所以总共重合22次

N只蚂蚁走树枝,问总距离或者总时间

问题:放N只蚂蚁在一条长度为M树枝上,蚂蚁与蚂蚁之间碰到就各自往反方向走,问总距离或者时间为多少?

参考回答:这个其实就一个诀窍:蚂蚁相碰就往反方向走,可以直接看做没有发生任何事:大家都相当于独立的,A蚂蚁与B蚂蚁相碰后你可以看做没有发生这次碰撞,这样无论是求时间还是距离都很简单了。

旅馆的1元钱问题

问题:有三个人去住旅馆,住三间房,每一间房10元,于是他们一共付给老板30,第二天,老板觉得三间房只需要25元就够了于是叫小弟退回5给三位客人,谁知小弟贪心,只退回每人1,自己偷偷拿了2,这样一来便等于那三位客人每人各花了九元,于是三个人一共花了27,再加上小弟独吞了不2,总共是29。可是当初他们三个人一共付出30那么还有$1呢?

他们所消费的27元里已经包括小弟贪污的2元了,再加退还的3元=30元; 这30元现在的分布是:老板拿25元,伙计拿2元,三人各拿1元,正好!

概率问题

家里有两个孩子,一个是女孩,另一个也是女孩的概率是多少?

1/3

样本空间为(男男)(女女)(男女)(女男)

A=(已知其中一个是女孩)=(女女)(男女)(女男)

B=(另一个也是女孩)=(女女)

于是P(B/A)=P(AB)/P(A)=(1/4)/(3/4)=1/3

一条绳子砍两刀,能构成一个三角形的概率?

设绳子总长为L,分成三段为:x,y,L - x - y; 其中x > 0,y > 0, L - x - y > 0,取值范围如图中蓝***域所示;

又因为任意两边之和要大于第三边,故有如下条件: x + y > L - x - y => y > -x + L / 2; x + (L - x - y) > y => y < L / 2; y + (L - x - y) > x => x < L / 2;

该区域为图中绿域,占蓝域的 四分之一

img

一个圆上随机画两条弦,求相交的概率?

四个点确定两条线,在一个圆上取四个点; 四个点画两条线有三种情况,其中只有一种情况是相交的,故相交概率为 三分之一;

img

犯人猜颜色

问题:一百个犯人站成一纵列,每人头上随机带上黑色或白色的帽子,各人不知道自己帽子的颜色,但是能看见自己前面所有人帽子的颜色.然后从最后一个犯人开始,每人只能用同一种声调和音量说一个字:”黑”或”白”,如果说中了自己帽子的颜色,就存活,说错了就拉出去斩了,说的答案所有犯人都能听见,是否说对,其他犯人不知道,在这之前,所有犯人可以聚在一起商量策略,问如果犯人都足够聪明而且反应足够快,100个人最大存活率是多少?

1、最后一个人如果看到奇数顶黑帽子报“黑”否则报“白”,他可能死

2、其他人记住这个值(实际是黑帽奇偶数),在此之后当再听到黑时,黑帽数量减一

3、从倒数第二人开始,就有两个信息:记住的值与看到的值,相同报“白”,不同报“黑”

99人能100%存活,1人50%能活

火枪手决斗,谁活下来的概率大?

问题:彼此痛恨的甲、乙、丙三个枪手准备决斗。甲枪法最好,十发八中;乙枪法次之,十发六中;丙枪法最差,十发四中。如果三人同时开枪,并且每人每轮只发一枪;那么枪战后,谁活下来的机会大一些?

参考回答: 一般人认为甲的枪法好,活下来的可能性大一些。但合乎推理的结论是,枪法最糟糕的丙活下来的几率最大;

那么我们先来分析一下各个枪手的策略:

如同田忌赛马一般,枪手甲一定要对枪手乙先。因为乙对甲的威胁要比丙对甲的威胁更大,甲应该首先干掉乙,这是甲的最佳策略。

同样的道理,枪手乙的最佳策略是第一枪瞄准甲。乙一旦将甲干掉,乙和丙进行对决,乙胜算的概率自然大很多。

枪手丙的最佳策略也是先对甲。乙的枪法毕竟比甲差一些,丙先把甲干掉再与乙进行对决,丙的存活概率还是要高一些。

我们根据分析来计算一下三个枪手在上述情况下的存活几率:

第一轮:甲射乙,乙射甲,丙射甲。

  • 甲的活率为24%(40% X 60%)
  • 乙的活率为20%(100% - 80%)
  • 丙的活率为100%(无人射丙)

由于丙100%存活率,因此根据上轮甲乙存活的情况来计算三人第二轮的存活几率:

情况1:甲活乙死(24% X 80% = 19.2%) 甲射丙,丙射甲:甲的活率为60%,丙的活率为20%。

情况2:乙活甲死(20% X 76% = 15.2%) 乙射丙,丙射乙:乙的活率为60%,丙的活率为40%。

情况3:甲乙同活(24% X 20% = 4.8%) 重复第一轮。

情况4:甲乙同死(76% X 80% = 60.8%) 枪战结束。

据此来计算三人活率:

  • 甲的活率为(19.2% X 60%) + (4.8% X 24%) = 12.672%
  • 乙的活率为(15.2% X 60%) + (4.8% X 20%) = 10.08%
  • 丙的活率为(19.2% X 20%) + (15.2% X 40%) + (4.8% X 100%) + (60.8% X 100%) = 75.52%

通过对两轮枪战的详细概率计算,我们发现枪法最差的丙存活的几率最大,枪法较好的甲和乙的存活几率却远低于丙的存活几率。

100个奴隶猜帽子颜色

问题:一百个奴隶站成一纵列,每人头上随机带上黑色或白色的帽子,各人不知道自己帽子的颜色,但是能看见自己前面所有人帽子的颜色. 然后从最后一个奴隶开始,每人只能用同一种声调和音量说一个字:”黑”或”白”, 如果说中了自己帽子的颜色,就存活,说错了就拉出去斩了,说的参考回答所有奴隶都能听见。 是否说对,其他奴隶不知道。 在这之前,所有奴隶可以聚在一起商量策略,问如果奴隶都足够聪明而且反应足够快,100个人最大存活率是多少?

1、最后一个人如果看到奇数顶黑帽子报“黑”否则报“白”,他可能死

2、其他人记住这个值(实际是黑帽奇偶数),在此之后当再听到黑时,黑帽数量减一

3、从倒数第二人开始,就有两个信息:记住的值与看到的值,相同报“白”,不同报“黑” 99人能100%存活,1人50%能活

另外,此题还有变种:每个奴隶只能看见前面一个人帽子颜色又能最多存活多少人? 参考回答:增加限制条件后,上面的方法就失效了, 此时只能约定偶数位奴隶说他前一个人的帽子颜色, 奇数奴隶获取信息100%存活,偶数奴隶50几率存活。

水桶问题

水资源无限,3L和5L水桶各一个,怎样取4L的水?

  • 初始时0,5
  • 然后3,2
  • 然后0,2
  • 然后2,0
  • 然后2,5
  • 然后1,4

img

水资源无限,5L和6L水桶各一个,怎样取3L的水?

  • step 1 , 6L水桶装满水倒入5L水桶,余下1L水
  • step 2 , 5L水桶倒空,将6L水桶中剩余的1L水倒入5L水桶
  • step 3 , 6L水桶再次装满水倒入5L水桶,余下2L水
  • step 4 , 5L水桶倒空, 将6L水桶中剩余2L水倒入5L水桶
  • step 5 , 6L水桶再次装满水倒入5L水桶,余下3L水

一个装了10L水的桶,一个7L的空桶,一个3L的空桶,怎样变成2个5L?

  • 初始时为10,0,0;
  • 第二步7,0,3;
  • 然后7,3,0;
  • 然后4,3,3;
  • 然后4,6,0;
  • 然后1,6,3;
  • 然后1,7,2;
  • 然后8,0,2;
  • 然后8,2,0;
  • 然后5,2,3;
  • 然后5,5,0;

舀酒问题:只有两个舀酒的勺子,分别能舀7两和11两酒,如何舀出2两酒?

问题:据说有人给酒肆的老板娘出了一个难题:此人明明知道店里只有两个舀酒的勺子,分别能舀7两和11两酒,却硬要老板娘卖给他2两酒。聪明的老板娘毫不含糊,用这两个勺子在酒缸里舀酒,并倒来倒去,居然量出了2两酒,聪明的你能做到吗?

思路:大勺子装满酒,再倒满小勺,于是大勺子还有4两,倒出小勺的酒,把大勺的4两倒入小勺中,再次在大勺中装满酒,大小勺加起来就是15两,把大勺中的酒倒入小勺中,使小勺装满,于是大勺中还有8两,倒掉小勺中的酒,再次把大勺中的酒倒入小勺中,使小勺装满,于是大勺中还有1两.重复以上动作一次,就可以得到2两酒

  • 初始0,11
  • 然后7,4
  • 然后0,4
  • 然后4,0
  • 然后4,11
  • 然后7,8
  • 然后0,8
  • 然后7,1
  • 然后0,1
  • 然后1,11
  • 然后7,5
  • 然后0,5
  • 然后5,0
  • 然后5,11
  • 然后7,9
  • 然后0,9
  • 然后7,2

计时问题

有一个能计时6分钟的小沙漏和一个能计时8分钟的大沙漏,如何计时10分钟?

  • 两个沙漏同时倒置开始计时,等小沙漏漏完,大沙漏还剩2分钟,这时倒置小沙漏继续计时;
  • 大沙漏漏完小沙漏还剩4分钟,再把大沙漏倒置继续计时;
  • 小沙漏漏完大沙漏还剩4分钟,这时准备工作已经完毕;
  • 等待大沙漏漏完(4分钟)+ 小沙漏(6分钟) = 10分钟。

烧一根绳子需要一个小时,现有若干条相同的绳子,问如何计时15分钟?

  • 点燃绳子A的一头,同时点燃绳子B的两头; 绳子B烧完的时候绳子A还剩一半,此时点燃绳子A的另一头开始计时;
  • 15分钟绳子A烧完。

蜡烛燃烧问题:两根蜡烛,燃烧完都需要1小时,怎么确定15分钟是多久?

  • 点燃第一根的一端,第二根的两端。
  • 第二根烧完代表半小时后,点燃第一根另一端,烧完代表15分钟。

赛马问题

25匹马5条跑道找最快的3匹马,需要跑几次?

参考回答:7

  • 将25匹马分成ABCDE5组,假设每组的排名就是A1>A2>A3>A4>A5,用边相连,这里比赛5次
  • 第6次,每组的第一名进行比赛,可以找出最快的马,这里假设A1>B1>C1>D1>E1 D1,E1肯定进不了前3,直接排除掉
  • 第7次,B1 C1 A2 B2 A3比赛,可以找出第二,第三名

所以最少比赛需要7次;

img

64匹马8条跑道找最快的4匹马,需要跑几次?

参考回答:11

第一步:全部马分为8组,每组8匹,每组各跑一次,然后淘汰掉每组的后四名(需要比赛8场)

img

第二步:取每组第一名进行一次比赛,然后淘汰最后四名所在组的所有马,如下图(需要比赛1场)

img

这个时候总冠军已经诞生,它就是A1,蓝域(它不需要比赛了)。

而其他可能跑得最快的三匹马只可能是下图中的黄域了(A2,A3,A4,B1,B2,B3,C1,C2,D1,共9匹马)

img

第三步:只要从上面的9匹马中找出跑得最快的三匹马就可以了,但是现在只要8个跑道,怎么办?

那就随机选出8匹马进行一次比赛吧(需要比赛一场)

第四步:上面比赛完,选出了前三名,但是9匹马中还有一匹马没跑呢,它可能是一个潜力股啊,那就和前三名比一比吧,这四匹马比一场,选出前三名。最后加上总冠军,跑得最快的四匹马诞生了!!!(需要一场比赛)

最后,一共需要比赛的场次:8 + 1 + 1 + 1 = 11 场

25匹马5条跑道找最快的5匹马,需要跑几次?

参考回答:最少8次最多9次

(1) 首先将25匹马分成5组,并分别进行5场比赛之后得到的名次排列如下:

A组: [A1 A2 A3 A4 A5]

B组: [B1 B2 B3 B4 B5]

C组: [C1 C2 C3 C4 C5]

D组: [D1 D2 D3 D4 D5]

E组: [E1 E2 E3 E4 E5]

其中,每个小组最快的马为[A1、B1、C1、D1、E1]。

(2) 将[A1、B1、C1、D1、E1]进行第6场,选出第1名的马,不妨设 A1>B1>C1>D1>E1. 此时第1名的马为A1。

(3) 将[A2、B1、C1、D1、E1]进行第7场,此时选择出来的必定是第2名的马,不妨假设为B1。因为这5匹马是除去A1之外每个小组当前最快的马。

(3) 进行第8场,选择[A2、B2、C1、D1、E1]角逐出第3名的马。

(4) 依次类推,第9,10场可以分别决出第4,5名的吗。

因此,依照这种竞标赛排序思想,需要10场比赛是一定可以取出前5名的。

仔细想一下,如果需要减少比赛场次,就一定需要在某一次比赛中同时决出2个名次,而且每一场比赛之后,有一些不可能进入前5名的马可以提前出局。

当然要做到这一点,就必须小心选择每一场比赛的马匹。我们在上面的方法基础上进一步思考这个问题,希望能够得到解决。

(1) 首先利用5场比赛角逐出每个小组的排名次序是绝对必要的。

(2) 第6场比赛选出第1名的马也是必不可少的。假如仍然是A1马(A1>B1>C1>D1>E1)。那么此时我们可以得到一个重要的结论:有一些马在前6场比赛之后就决定出局的命运了(下面粉色字体标志出局)。

A组: [A1 A2 A3 A4 A5]

B组: [B1 B2 B3 B4 B5 ]

C组: [C1 C2 C3 C4 C5 ]

D组: [D1 D2 D3 D4 D5 ]

E组: [E1 E2 E3 E4 E5 ]

(3) 第7场比赛是关键,能否同时决出第2,3名的马呢?我们首先做下分析:

在上面的方法中,第7场比赛[A2、B1、C1、D1、E1]是为了决定第2名的马。但是在第6场比赛中我们已经得到(B1>C1>D1>E1),试问?有B1在的比赛,C1、D1、E1还有可能争夺第2名吗? 当然不可能,也就是说第2名只能在A2、B1中出现。实际上只需要2条跑道就可以决出第2名,剩下C1、D1、E1的3条跑道都只能用来凑热闹的吗?

能够优化的关键出来了,我们是否能够通过剩下的3个跑道来决出第3名呢?当然可以,我们来进一步分析第3名的情况?

● 如果A2>B1(即第2名为A2),那么根据第6场比赛中的(B1>C1>D1>E1)。 可以断定第3名只能在A3和B1中产生。

● 如果B1>A2(即第2名为B1),那么可以断定的第3名只能在A2, B2,C1 中产生。

好了,结论也出来了,只要我们把[A2、B1、A3、B2、C1]作为第7场比赛的马,那么这场比赛的第2,3名一定是整个25匹马中的第2,3名。

我们在这里列举出第7场的2,3名次的所有可能情况:

① 第2名=A2,第3名=A3

② 第2名=A2,第3名=B1

③ 第2名=B1,第3名=A2

④ 第2名=B1,第3名=B2

⑤ 第2名=B1,第3名=C1

(4) 第8场比赛很复杂,我们要根据第7场的所有可能的比赛情况进行分析。

① 第2名=A2,第3名=A3。那么此种情况下第4名只能在A4和B1中产生。

● 如果第4名=A4,那么第5名只能在A5、B1中产生。

● 如果第4名=B1,那么第5名只能在A4、B2、C1中产生。

不管结果如何,此种情况下,第4、5名都可以在第8场比赛中决出。其中比赛马匹为[A4、A5、B1、B2、C1]

② 第2名=A2,第3名=B1。那么此种情况下第4名只能在A3、B2、C1中产生。

● 如果第4名=A3,那么第5名只能在A4、B2、C1中产生。

● 如果第4名=B2,那么第5名只能在A3、B3、C1中产生。

● 如果第4名=C1,那么第5名只能在A3、B2、C2、D1中产生。

那么,第4、5名需要在马匹[A3、B2、B3、C1、A4、C2、D1]七匹马中产生,则必须比赛两场才行,也就是到第9场角逐出全部的前5名。

③ 第2名=B1,第3名=A2。那么此种情况下第4名只能在A3、B2、C1中产生。

情况和②一样,必须角逐第9场

④ 第2名=B1,第3名=B2。 那么此种情况下第4名只能在A2、B3、C1中产生。

● 如果第4名=A2,那么第5名只能在A3、B3、C1中产生。

● 如果第4名=B3,那么第5名只能在A2、B4、C1中产生。

● 如果第4名=C1,那么第5名只能在A2、B3、C2、D1中产生。

那么,第4、5名需要在马匹[A2、B3、B4、C1、A3、C2、D1]七匹马中产 生,则必须比赛两场才行,也就是到第9场角逐出全部的前5名。

⑤ 第2名=B1,第3名=C1。那么此种情况下第4名只能在A2、B2、C2、D1中产生。

● 如果第4名=A2,那么第5名只能在A3、B2、C2、D1中产生。

● 如果第4名=B2,那么第5名只能在A2、B3、C2、D1中产生。

● 如果第4名=C2,那么第5名只能在A2、B2、C3、D1中产生。

● 如果第4名=D1,那么第5名只能在A2、B2、C2、D2、E2中产生。

那么,第4、5名需要在马匹[A2、B2、C2、D1、A3、B3、C3、D2、E1]九匹马中 产 生,因此也必须比赛两场,也就是到第9长决出胜负。

总结:最好情况可以在第8场角逐出前5名,最差也可以在第9场搞定。

过河/过桥问题

三人三鬼过桥

问题:有三个人跟三个鬼要过河,河上没桥只有条小船,然后船一次只能渡一个人和一个鬼,或者两个鬼或者两个人,无论在哪边岸上,只有是人比鬼少的情况下(如两鬼一人,三鬼两人,三鬼一人)人会被鬼吃,然而船又一定需要人或鬼操作才能航行(要有人或鬼划船),问,如何安全的把三人三鬼渡过河对岸?

参考回答:

  • 先两鬼过去。在一鬼回来。对面有一鬼。这边有三人两鬼。
  • 再两鬼过去。在一鬼回来。对面有两鬼。这边有三人一鬼。
  • 再两人过去。一人一鬼回来。对面一人一鬼。这边两人两鬼。
  • 最后两人过去。一鬼回来。对面三人。这边三鬼。
  • 剩下的就三个鬼二个过去一个回来在接另外个就OK了。

限时过桥问题

问题:在一个夜晚,同时有4人需要过一桥,一次最多只能通过两个人,且只有一只手电筒,而且每人的速度不同。A,B,C,D需要时间分别为:1,2,5,10分钟。问:在17分钟内这四个人怎么过桥?

总共是17分钟

  • 第一步:A、B过花时间2分钟。
  • 第二步:B回花时间2分钟。
  • 第三步:C、D过花时间10分钟。
  • 第四步:A回花时间1分钟。
  • 第五步:A、B再过花时间2分钟。

最优解问题

猴子搬香蕉

问题:一个小猴子边上有100根香蕉,它要走过50米才能到家,每次它最多搬50根香蕉,(多了就被压死了),它每走1米就要吃掉一根,请问它最多能把多少根香蕉搬到家里。

(提示:他可以把香蕉放下往返的走,但是必须保证它每走一米都能有香蕉吃。也可以走到n米时,放下一些香蕉,拿着n根香蕉走回去重新搬50根。)

答案: 这种试题通常有一个迷惑点,让人看不懂题目的意图。此题迷惑点在于:走一米吃一根香蕉,一共走50米,那不是把50根香蕉吃完了吗?如果要回去搬另外50根香蕉,则往回走的时候也要吃香蕉,这样每走一米需要吃掉三根香蕉,走50米岂不是需要150根香蕉?

其实不然,本题关键点在于:猴子搬箱子的过程其实分为两个阶段,第一阶段:来回搬,当香蕉数目大于50根时,猴子每搬一米需要吃掉三根香蕉。第二阶段:香蕉数《=50,直接搬回去。每走一米吃掉1根。

我们分析第一阶段:假如把100根香蕉分为两箱。一箱50根。

  • 第一步,把A箱搬一米,吃一根。
  • 第二步,往回走一米,吃一根。
  • 第三步,把B箱搬一米,吃一根。

这样,把所有香蕉搬走一米需要吃掉三根香蕉。

这样走到第几米的时候,香蕉数刚好小于50呢? 100-(n*3)<50 && 100-(n-1*3)>50

走到16米的时候,吃掉48根香蕉,剩52根香蕉。这步很有意思,它可以直接搬50往前走,也可以再来回搬一次,但结果都是一样的。到17米的时候,猴子还有49根香蕉。这时猴子就轻松啦。直接背着走就行。

第二阶段:走一米吃一根。

把剩下的50-17=33米走完。还剩49-33=16根香蕉。

高楼扔鸡蛋

问题:有2个鸡蛋,从100层楼上往下扔,以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎,在第10层摔碎了,那么鸡蛋不会摔碎的临界点就是9层。如何用最少的尝试次数,测试出鸡蛋不会摔碎的临界点?

首先要说明的是这道题你要是一上来就说出正确答案,那说明你的智商不是超过160就是你做过这题。所以建议你循序渐进的回答,一上来就说最优解可能结果不会让你和面试官满意。

1.暴力法

举个栗子,最笨的测试方法,是什么样的呢?把其中一个鸡蛋,从第1层开始往下扔。如果在第1层没碎,换到第2层扔;如果在第2层没碎,换到第3层扔…….如果第59层没碎,换到第60层扔;如果第60层碎了,说明不会摔碎的临界点是第59层。

在最坏情况下,这个方法需要扔100次。

2. 二分法

采用类似于 二分查找 的方法,把鸡蛋从一半楼层(50层)往下扔。

如果第一枚鸡蛋,在50层碎了,第二枚鸡蛋,就从第1层开始扔,一层一层增长,一直扔到第49层。

如果第一枚鸡蛋在50层没碎了,则继续使用二分法,在剩余楼层的一半(75层)往下扔……

这个方法在最坏情况下,需要尝试50次。

3.均匀法

如何让第一枚鸡蛋和第二枚鸡蛋的尝试次数,尽可能均衡呢?

很简单,做一个平方根运算,100的平方根是10。

因此,我们尝试每10层扔一次:第1次从10层扔,第2次从20层扔,第3次从30层…一直扔到100层。

这样的最好情况是在第10层碎掉,尝试次数为 1 + 9 = 10次。

最坏的情况是在第100层碎掉,尝试次数为 10 + 9 = 19次。

不过,这里有一个小小的优化点,我们可以从15层开始扔,接下来从25层、35层扔……一直到95层。

这样最坏情况是在第95层碎掉,尝试次数为 9 + 9 = 18次。

4.最优解法

最优解法是反向思考的经典:如果最优解法在最坏情况下需要扔X次,那第一次在第几层扔最好呢?

答案是:从X层扔

假设最优的尝试次数的x次,为什么第一次扔就要选择第x层呢?

这里的解释会有些烧脑,请小伙伴们坐稳扶好:

假设第一次扔在第x+1层:

如果第一个鸡蛋碎了,那么第二个鸡蛋只能从第1层开始一层一层扔,一直扔到第x层。

这样一来,我们总共尝试了x+1次,和假设尝试x次相悖。由此可见,第一次扔的楼层必须小于x+1层。

假设第一次扔在第x-1层:

如果第一个鸡蛋碎了,那么第二个鸡蛋只能从第1层开始一层一层扔,一直扔到第x-2层。

这样一来,我们总共尝试了x-2+1 = x-1次,虽然没有超出假设次数,但似乎有些过于保守。

假设第一次扔在第x层:

如果第一个鸡蛋碎了,那么第二个鸡蛋只能从第1层开始一层一层扔,一直扔到第x-1层。

这样一来,我们总共尝试了x-1+1 = x次,刚刚好没有超出假设次数。

因此,要想尽量楼层跨度大一些,又要保证不超过假设的尝试次数x,那么第一次扔鸡蛋的最优选择就是第x层。

那么算最坏情况,第二次你只剩下x-1次机会,按照上面的说法,你第二次尝试的位置必然是X+(X-1);

以此类推我们可得:

x + (x-1) + (x-2) + … + 1 = 100

这个方程式不难理解:

左边的多项式是各次扔鸡蛋的楼层跨度之和。由于假设尝试x次,所以这个多项式共有x项。

右边是总的楼层数100。

下面我们来解这个方程:

x + (x-1) + (x-2) + … + 1 = 100 转化为 (x+1)*x/2 = 100

最终x向上取整,得到 x = 14

因此,最优解在最坏情况的尝试次数是14次,第一次扔鸡蛋的楼层也是14层。

最后,让我们把第一个鸡蛋没碎的情况下,所尝试的楼层数完整列举出来:

14,27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100

举个栗子验证下:

假如鸡蛋不会碎的临界点是65层, 那么第一个鸡蛋扔出的楼层是14,27,50,60,69。这时候啪的一声碎了。 第二个鸡蛋继续,从61层开始,61,62,63,64,65,66,啪的一声碎了。 因此得到不会碎的临界点65层,总尝试次数是 6 + 6 = 12 < 14 。

leetcode https://leetcode-cn.com/problems/egg-drop-with-2-eggs-and-n-floors/

利用空瓶换饮料,最多喝几瓶

问题:1000瓶饮料,3个空瓶子能够换1瓶饮料,问最多能喝几瓶?

第一种思路:

拿走3瓶,换回1瓶,相当于减少2瓶。但是最后剩下4瓶的时候例外,这时只能换1瓶。所以我们计算1000减2能减多少次,直到剩下4.(1000-4=996,996/2=498)所以1000减2能减498次直到剩下4瓶,最后剩下的4瓶还可以换一瓶,所以总共是1000+498+1=1499瓶。

第二种思路:

  • 1000瓶饮料,3个空瓶子能换1瓶饮料,最多可以喝几瓶?

  • 第一种思维:可以考虑成dp思路

  • 初始情况,3个瓶子时将发生一次交换,因此视为特殊情况

  • 之后每增加两个瓶子又可以再换一瓶

  • 即dp[i] = dp[i - 2] + (i - (i - 2)) + 1

  • 由dp[i - 2]可求得dp[i]

  • (i - (i - 2)),即为当前增加的2瓶饮料(写成这样便于理解)

  • 1即为增加了2个空瓶,之后又可以换一瓶饮料

  • 简化为dp[i] = dp[i - 2] + 2 + 1

复制代码

1
public` `int` `method(``int` `n) {``   ``// n为0/1/2的特殊情况省略了``   ``// 定义dp数组``   ``int``[] dp = ``new` `int``[n + 1];``   ``// 初始状态``   ``dp[0] = 0;``   ``dp[1] = 1;``   ``dp[2] = 2;``   ``for` `(``int` `i = 3; i <= n; i++) {``    ``dp[i] = dp[i - 2] + 2 + 1;``  ``}``   ``return` `dp[n];`` ``}
  • 回归正题

  • 特殊情况:从上面的分析中,留下2个瓶子

  • 剩下998个瓶子相当于每消耗2个瓶子即可获得一瓶,即为499瓶

  • 最后剩下的2个瓶子无法再进行兑换,因此总共为1000 + 499 = 1499

  • 第二种思维:利用借瓶子的思想

  • 因为兑换一瓶饮料需要三个空瓶,这瓶饮料如果是找老板借来的,那么喝完后这个空瓶将会还给他,同时需要附赠给他另外两个空瓶,即每消耗手里两个空瓶就获得一瓶饮料

  • 但是值得注意的是,上面只是一种假设,实际情况老板是不会借给你的,因此我们至少需要保留2个空瓶,这样可以在998个瓶子剩下一个瓶子时,对其进行补足为3个空瓶,从而兑换一瓶新饮料

  • 此时使用998个瓶子进行上述的兑换,将获得499瓶饮料

  • 之前留下的两个瓶子正好无法兑换,最终获得饮料为1000 + 499 = 1499瓶

数字问题

11-22-33-44问题

问题:有8个数,11-22-33-44,将其排列,要求结果满足:两个1之间有一个数,两个2之间有两个数,两个3之间有三个数,两个4之间有四个数。问这个结果是多少?

答案:①4131-2432 ②2342-1314

img
img

给定随机函数,生成别的随机数

问题:给定生成1到5的随机数Rand5(),如何得到生成1到7的随机数函数Rand7()?

思路 :由大的生成小的容易,比如由Rand7()生成Rand5(),所以我们先构造一个大于7的随机数生成函数。 记住下面这个式子:

复制代码

1
RandNN= N( RandN()-1 ) + RandN() ;``// 生成1到N^2之间的随机数``可以看作是在数轴上撒豆子。N是跨度/步长,是RandN()生成的数的范围长度,``RandN()-1的目的是生成0到N-1的数,是跳数。后面+RandN()的目的是填满中间的空隙

比如 Rand25= 5( Rand5()-1 ) + Rand5() 可以生成1到25之间的随机数。我们可以只要1到21(3*7)之间的数字,所以可以这么写

复制代码

1
int` `rand7(){`` ``int` `x=INT_MAX;`` ``while``(x>21){``  ``x=5*(rand5()-1)+rand5();`` ``}`` ``return` `x%7+1;``}

11. 重量问题

乒乓球重量问题:8个乒乓球,其中一个重,有一个秤,问至少几次能够找出重的那个乒乓球

2次,分成3堆,3,3,2。

  • ①称3和3,如果一样重,代表重的在2。
  • ②称2个那一堆的。

  • ①称3和3,不一样重,重的在3里面重的那堆。
  • ②3个里面随便取2个,一样重,第三个重,不一样重,重的那个就是。

盐重量问题:有7克、2克砝码各一个,天平一只,如何只用这些物品五次内将140克的盐分成50、90克各一份?

  • 第一次:先分成70和70
  • 第二次:通过7和2砝码将70分成9和61
  • 第三次:通过9克盐和2砝码将61分成50和11

有一个天平,九个砝码,其中一个砝码比另八个要轻一些,问至少要用天平称几次才能将轻的那个找出来?

需要称2次;

天平一边放三个砝码,哪边轻就在哪边,一样重就在剩下的三个砝码中;

现在已经锁定了三个砝码,天平一边放一个,哪边轻是哪个,一样重就是剩下的那个;

十组砝码每组十个,每个砝码都是10g重,但是现在其中有一组砝码每个都只有9g重,现有一个能显示克数的秤,最少称几次能找到轻的那组?

称一次即可;

将砝码分组编号1~10, 第1组拿1个砝码、第2组拿2个…第10组拿10个,全部放到秤上计算总克数X; Y = (1*10 + 2 * 10 + … + 10 * 10) - X = 550 - X,Y即为轻的那组的编号。

药丸问题:有20瓶药丸,其中19瓶装有1克/粒的药丸,余下一瓶装有1.1克/粒的药丸。给你一台称重精准的天平,怎么找出比较重的那瓶药丸?天平只能用一次;

从药瓶#1取出一粒药丸,从药瓶#2取出两粒,从药瓶#3取出三粒,依此类推。

如果每粒药丸均重1克,则称得总重量为210克(1 + 2 + … + 20 = 20 * 21 / 2 = 210),“多出来的”重量必定来自每粒多0.1克的药丸。

药瓶的编号可由算式(weight - 210) / 0.1 得出。因此,若这堆药丸称得重量为211.3克,则药瓶#13装有较重的药丸。

药丸问题:你有四个装药丸的罐子,每个药丸都有一定的重量,被污染的药丸是没被污染的重量+1.只称量一次,如何判断哪个罐子的药被污染了?

从第一盒中取出一颗,第二盒中取出2 颗,第三盒中取出三颗。

依次类推,称其总量。减去10,多的数字就是药丸罐子序号。

灯泡开关问题

在房里有三盏灯,房外有三个开关,在房外看不见房内的情况,你只能进门一次,你用什么方法来区分那个开关控制那一盏灯?

打开一个开关,过10分钟后关掉开关,并打开另一个开关。进屋确认可知:

  • 亮的灯是由第二次打开的开关控制;
  • 摸上去发热的不发亮的灯是由第一次打开的开关控制
  • 剩下的第三盏灯是由未操作过的开关控制。

一个圆环上有 100 个灯泡,灯泡有亮和暗两种状态。按一个灯泡的开关可以改变它和与它相邻两个灯泡的状态。设计一种算法,对于任意初始状态,使所有灯泡全亮。

将灯泡编号 1 ~ 100

步骤一:将灯泡变为全亮或只剩一个为暗

从 1 循环到 98 ,遇到暗的则按它下一个,使之变亮。循环完毕,1 ~ 98 必然全亮。99 和 100可能为亮亮、暗亮、亮暗、暗暗四种状态。

  • 若为亮亮,皆大欢喜,满足题目要求
  • 暗亮、亮暗,达到只剩一个为暗的状态;
  • 若为暗暗。则按下编号 100 的灯泡,使编号 99 、100 变为亮,编号 1 的灯泡变为暗,从而达到只剩一个为暗的状态。

步骤二:将灯泡变为全暗

由于灯泡环形摆放,我们指定暗的灯泡编号为 1 ,将剩下 99 个亮着的灯泡每 3 个为一组。按下每组中间的灯泡后,使得所有灯泡变为暗。

步骤三:将灯泡变为全亮

将所有灯泡按一下,灯泡变为全亮;

扩展:

对于 N 个灯泡的任意初始状态 ( N > 3 ) ,能否经过若干次操作使得所有灯泡全亮?

答案:N 个灯泡做分类讨论。

  1. N = 3*k+1一定可以。方法与上述步骤相同,在步骤二中可以将3k个亮的灯泡分为k组。
  2. N = 3*k+2一定可以。将上述步骤一目标状态的只剩一个为暗改成剩两个相邻为暗,其余 3 * k 个灯泡分组按即可。因为,对于任意只剩一个为暗的状态,按下该灯泡左右任意一个就可以变成剩两个相邻为暗的状态!
  3. N = 3*k不一定。如果经过上述步骤一可以将灯泡变成全亮的状态则有解;否则,无解。(该结论有待证明)

附:

对于这道题,以下两个状态可以相互转化

大家可以琢磨下,对理解这道题会有帮助。

  1. 全暗 <=> 全亮。全暗和全亮状态可以相互转化,方法就是将每个灯泡按一次。这样每个灯泡都被改变了 3 次状态,使得全暗变为全亮,全亮也可变为全暗。
  2. 剩一个为暗 <=> 剩两个相邻为暗。剩一个为暗时,按下该灯泡左右任意一个,就变成了剩两个相邻为暗的状态;剩两个相邻为暗时,按下第二个暗,便可变成了剩一个为暗的状态。

蓝眼/疯狗/耳光问题

蓝眼睛问题

问题:有个岛上住着一群人,有一天来了个游客,定了一条奇怪的规矩:所有蓝眼睛的人都必须尽快离开这个岛。每晚8点会有一个航班离岛。每个人都看得见别人眼睛的颜色,但不知道自己的(别人也不可以告知)。此外,他们不知道岛上到底有多少人是蓝眼睛的,只知道至少有一个人的眼睛是蓝色的。所有蓝眼睛的人要花几天才能离开这个岛?

有多少个蓝眼睛的人就会花多少天。

  • c=1

假设岛上所有人都是聪明的,蓝眼睛的人四处观察之后,发现没有人是蓝眼睛的。但他知道至少有一人是蓝眼睛的,于是就能推导出自己一定是蓝眼睛的。因此,他会搭乘当晚的飞机离开。

  • c=2

两个蓝眼睛的人看到对方,并不确定c是1还是2,但是由上一种情况,他们知道,如果c = 1,那个蓝眼睛的人第一晚就会离岛。因此,发现另一个蓝眼睛的人仍在岛上,他一定能推断出c = 2,也就意味着他自己也是蓝眼睛的。于是,两个蓝眼睛的人都会在第二晚离岛。

  • c>2

逐步提高c时,我们可以看出上述逻辑仍旧适用。如果c = 3,那么,这三个人会立即意识到有2到3人是蓝眼睛的。如果有两人是蓝眼睛的,那么这两人会在第二晚离岛。因此,如果过了第二晚另外两人还在岛上,每个蓝眼睛的人都能推断出c = 3,因此这三人都有蓝眼睛。他们会在第三晚离岛。

不论c为什么值,都可以套用这个模式。所以,如果有c人是蓝眼睛的,则所有蓝眼睛的人要用c晚才能离岛,且都在同一晚离开。

疯狗问题

问题:有50家人家,每家一条狗。有一天警察通知,50条狗当中有病狗,行为和正常狗不一样。每人只能通过观察别人家的狗来判断自己家的狗是否生病,而不能看自己家的狗,如果判断出自己家的狗病了,就必须当天一枪打死自己家的狗。结果,第一天没有枪响,第二天没有枪响,第三天开始一阵枪响,问:一共死了几条狗?

死了3条(第 几天枪响就有几条)。

从有一条不正常的狗开始,显然第一天将会听到一声枪响。这里的要点是你只需站在那条不正常狗的主人的角度考虑。有两条的话思路继续,只考虑有两条不正常狗的人,其余人无需考虑。通过第一天他们了解了对方的信息。第二天杀死自己的狗。换句话说每个人需要一天的时间证明自己的狗是正常的。有三条的话,同样只考虑那三个人,其中每一个人需要两天的时间证明自己的狗是正常的狗。

耳光问题

问题:一群人开舞会,每人头上都戴着一顶帽子。帽子只有黑白两种,黑的至少有一顶。每个人都能看到其他人帽子的颜色,却看不到自己的。主持人先让大家看看别人头上戴的是什么帽子,然后关灯,如果有人认为自己戴的是黑帽子,就打自己一个耳光。第一次关灯,没有声音。于是再开灯,大家再看一遍,关灯时仍然鸦雀无声。一直到第三次关灯,才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子?

答案:有三个人戴黑帽。

假设有N个人戴黑帽,当N=1时,戴黑帽的人看见别人都为白则能肯定自己为黑。于是第一次关灯就应该有声。可以断定N>1。对于每个戴黑帽的人来说,他能看见N-1顶黑帽,并由此假定自己为白。但等待N-1次还没有人打自己以后,每个戴黑人都能知道自己也是黑的了。所以第N次关灯就有N个人打自己。

  • 本文标题:算法智力题
  • 本文作者:Nico Liao
  • 创建时间:2022-03-24 23:28:30
  • 本文链接:https://www.lzp.zone/2022/03/24/算法智力题/
  • 版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
 评论