Quant 头脑风暴，39个球，4次称重找出其中的缺陷球。。。。。。。。。。。。。。。。

gaohannk 发表于 2021-08-11 12:21:50
前提是知道缺陷球是轻还是重

这前提跟“12个球称3次”一样

gaohannk 发表于 2021-08-11 12:21:50
前提是知道缺陷球是轻还是重

不需要知道缺陷球轻重

flyrainbow 发表于 2021-08-11 14:05:34
我一直不知道考这种题到底有啥意义。

没意义，period。

授人以鱼不如授人以渔
【bilibili】经典的“12枚硬币称量问题”（上）

南宫狗剩 发表于 2021-8-12 17:20
授人以鱼不如授人以渔
【bilibili】经典的“12枚硬币称量问题”（上）

非常经典！下期的视频，明确说明了39枚是很好的练习，一会我按照他说的做做

1: 13, 13, 13
2: 4, 4, 5
3: 1, 1, 2/2, 2, 1
4: 1, 1/不用测

就是一个n层的三叉树最多能容纳多少个节点的问题

楼主推荐你一题叫pig poison. 这不是经典算法题，跟quant有什么关系

得知道缺陷球轻重啊。要不然还是需要5次。

rxrx 发表于 2021-8-11 11:18
我觉得是不是可以这样
第一次：分成3个13，称其中2个，这样可以找出缺陷球在哪个13里
第二次：把13分成4+ ...

在第二次称的时候，如过能确定缺陷球在五个球里，那就应该分成2 2 1这样的
第三次就是称2 和 2，如果等，则不需要第四次了，剩下那个1就是缺陷球
如果不等，第四次该怎么称呢？这里感觉少了个条件啊，就是那个缺陷球是偏轻还是偏重呢？如果不确定的话，好像四次是搞不定的。

两种办法，动态规划和编号法，编号法类似于100个小老鼠喝毒药那个，四次之后就出来四位数编号就得了

动态规划就简单了，经典算法，网上去搜通解思路就得了

楼上还有问这题有啥意义？当然要觉得整个算法这种东西都没意义就不说了。。。

另外，友情提醒楼主，你的公式只适用于这个小球问题
通解是信息论

Log(78) / log(3)

39个球 log39 ，不知道是轻是重，所以log2
总信息需要是log78
然后天平可以提供 左右平 三种结果 ，每次提供log3

那么需要多少次就是 这俩相除 然后向上取整 4 次