"收集各类 trick problems,积少成多,锻炼思维,防止老年痴呆。 虽然这些问题各种奇奇怪怪,但是也是有些门道可循的,转换为数学问题、反证法、逆向思维、找到里头可以 trick 的点。 有时候,虽然解不出答案,但是能把思考过程说出来也是很好的。 2 刀分 7 天工资 Q: 老板有一块金子,恰好是程序员 Zing .."

trick problems

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

收集各类 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: 从后往前考虑


百人开灯

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


烧绳子

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 个那堆的硬币全部翻转一遍即可。

  • 算法
    234 引用 • 144 回帖 • 9 关注
  • 面试

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

    209 引用 • 1142 回帖 • 456 关注
感谢    关注    收藏    赞同    反对    举报    分享
回帖    
请输入回帖内容...