※ 引述《H45 (!H45)》之铭言： : 深究：k个钱币中有一袋假币(与真币重量不同)，请利用天平秤秤n次找出假币 : ，并说出假币的重量较轻还是重。请问Minimum of n？ : 如何以一个演算法算出这个Minimum of n? 我找到方向了 用 三元树 (3-ary tree) 模拟 往左的 child 是天平往左倾 往右的 child 是天平往右倾 往中的 child 是天平不倾斜 而树的高，就是天平要秤的次数 n 树叶 (leaf) 的数量，就是钱币的数量 k 设 f(x) 表以 3 为底的 logx upper(x) 表 x 无条件进入至整数 则 n >= upper(f(k)) 也就是说 n 的 lower bound 是 upper(f(k)) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.115.205.85