trick problems

本贴最后更新于 2920 天前,其中的信息可能已经东海扬尘

收集各类 trick problems,积少成多,锻炼思维,防止老年痴呆。

虽然这些问题各种奇奇怪怪,但是也是有些门道可循的,转换为数学问题、反证法、逆向思维、找到里头可以 trick 的点。

有时候,虽然解不出答案,但是能把思考过程说出来也是很好的。


2 刀分 7 天工资

Q:老板有一块金子,恰好是程序员 Zing 一周的工资,每天工资一样。老板需要每天向 Zing 支付工资,不得多付,不得拖欠,仅允许对金子切 2 刀。问解决方案。

A:把金子分为 1/7,2/7,4/7。第一天支付 1/7,第二天拿 2/7 换 1/7,第三天再给 1/7,第四天拿 4/7 换 1/7 和 2/7...


海盗分赃问题

Q:5 个海盗抢到 100 个金币,每个一样大。5 人按照顺序提出分配方案,然后所有人表决,半数以上人同意时采用该分配方案,否则将提方案的人丢进大海喂鲨鱼。
前提:海盗的决策都是聪明的,海盗都是贪婪而且残忍的。

A: 从后往前考虑

  • 若前 3 个都被扔到海里,只剩下 4 和 5,4 不可能获得一半以上的票数,那么 4 只有死路一条,因此无论 3 什么提案都要同意。
  • 那么对于 3 来说,干掉 1 和 2 之后,只剩下 3 人,有了自己和 4 那一票,无论自己什么提案都可以通过,因此提出 100,0,0
  • 对于 2 来说,若要使自己的提案通过,还需要拉拢 2 票。因此需要给出的 offer 比 3 的提案更好,因此只能拉拢 4 和 5 两人,98,0,1,1
  • 对于 1 来说,也需要拉拢 2 票,所有最优的提案是 97,0,1,2,0 或 97,0,1,0,2

百人开灯

Q:房间里头有 100 个灯对应 100 个开关,按顺序从 1 到 100 编号,初始全部灯均关闭。门外有 100 个人,按顺序 1 到 100 编号,每个人依次进入,且必须开或关 那些灯的编号可以整除自己编号的开关。问所有人经过后,房间里有哪些灯是亮的。

A:这道题其实是问每个数的因数个数是奇数还是偶数。任意数 n 的因数都是成对出现的,1 和 n,a 和 n/a 等等,但是这其中有一个特殊情况,若 a=n/a 那么因数的个数就变成奇数了。所以房间里 1,4,9,25,36,49,64,81(n^2<=100)是亮的。


5L 和 3L 杯子量 4L 水

Q:只有 5L 和 3L 的无刻度杯子各一个,水无限,要求量出 4L 水

A:思路是 4=3+1,4=5-1

  • 4=3+1:3L 杯子装满,倒到 5L 杯子中,3L 杯子再装满,倒到 5L 杯子直到 5L 杯子满,此时 3L 杯子中剩下 1L 水。把 5L 杯子里的水倒掉,3L 杯子中的 1L 倒入 5L 杯子中,3L 杯子再装满,倒到 5L 杯子中。
  • 4=5-1:5L 杯子装满,倒到 3L 杯子中直到 3L 杯子满,此时 5L 杯子中剩下 2L,3L 杯子中的水倒掉,把 5L 杯子中的 2L 水倒到 3L 杯子中,5L 杯子水装满,然后往 3L 杯子倒水直到 3L 杯子满。

烧绳子

Q:两根燃烧速度不均匀的绳子,但是烧完均 60 分钟,要求计时 30 分钟和 45 分钟。

A:30 分钟:一根绳子两头同时点着,烧尽即为 30 分钟。45 分钟,第一个绳子两头同时点着,同时第二根绳子点着一头,当第一根绳子烧尽的时候把第二根绳子另一头也点上,第二根绳子烧尽即为 45 分钟。


兔子试毒药

Q:有 1000 瓶药水,其中只有 1 瓶是毒药,兔子喝毒药 1 天后才会死,问最少用几只兔子能找到那瓶毒药?

A:2^9<1000<2^10,因此最少 10 只兔子可以试出毒药。解决方法是,将 10 只兔子进行编号 10 到 1 表示 2 进制从高位到低位,将 1000 瓶药水进行编号 1 到 1000。将药水编号转化为 2 进制,哪些位置上为 1,喂给对应的兔子,如 7 号药水 2 进制是 0000000111 ,喂给 1、2、3 号兔子。1 天后,观察哪些兔子死了,将死亡兔子位置设为 1,转换为 10 进制则是对应的毒药。若只有 1、2、3 号兔子死亡,则 0000000111=7 号药水有毒。


拿球问题

Q:现在有 100 各球,甲乙两人轮流拿球,每人每次只能拿 1-5 个球,拿到最后一个球为胜者。若甲先拿球,有办法保证甲一定获胜吗?如果有甲应该如何拿。

A:从后往前推,若甲拿到第 94 个球,则无论已如何拿,甲总能拿到第 100 个球。为了保证拿到第 94 个球,甲必须保证拿到第 88 个球。以此类推,甲必须拿到第(100-n*6)个球。因此为了获胜,甲第一次需要拿 4 个球,之后每次根据乙拿 x 个,甲再拿(6-x)即可。


青蛙跳楼梯

Q:有 100 阶楼梯,小青蛙一次能跳 1 阶、2 阶或 3 阶。求问小青蛙恰好跳到第 100 阶,有多少种跳法?

A:这道题用动态规划解决,定义 d[i]=n 为跳到第 i 阶有 n 种方法。则有:对于 i=100,小青蛙可以先跳到 99 阶,再跳 1 阶到 100;也可以跳到 98 阶,再跳 2 阶到 100(不能跳 1+1,因为会和 99 重复);也可以跳到 97 阶,再跳 3 阶到 100。d[i]=d[i-1]+d[i-2]+d[i-3]

Q:现在小青蛙长成大青蛙了,大青蛙可以一次跳 1、2、3、...、n 阶楼梯,求问大青蛙有多少种方法跳 n 阶。

A:对于这道题再用动态规划就把问题复杂化了。转化一种思路。总共 n 阶楼梯,第 n 阶肯定要到达,那么剩下的 n-1 阶,每一阶大青蛙可能落到也可能跳过(0 或 1),可以当作一个 n-1 位的 2 进制数,因此很直接的有 2^(n-1)种可能。


天堂与地狱

Q:你来到一个天堂和地狱的岔路口,但是不知道哪边是通往天堂哪边通往低于。岔路口有两个人,都直到路往何方,但是其中一个只有说实话,一个只会说假话,你并不认识他们,你可以向两人问相同的问题,若要去天堂,该如何问?

A:你可以这么问“若我问另外一个人地狱怎么走,他会指哪条路?”。无论问哪个人,都会指向同一条路,且这条路就是通向天堂的路。True and False = False and True = False


硬币问题

Q:有 25 个硬币,其中 10 个正面朝上,你被蒙住眼睛,也无法通过手摸出正反面。要求你将硬币分为两堆。使两堆硬币正面朝上的个数一样。

A:将硬币分成两堆分别为 15 和 10。15 个硬币中正面朝上有 a 个,10 个硬币中正面朝上有 b 个,背面朝上有 c 个。则有 a+b=b+c=10。即 a=c,15 个中正面朝上的硬币个数=10 个中背面朝上的硬币个数,因此只需要把 10 个那堆的硬币全部翻转一遍即可。

  • 算法
    388 引用 • 254 回帖 • 22 关注
  • 面试

    面试造航母,上班拧螺丝。多面试,少加班。

    324 引用 • 1395 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...