【每日一题】- 2021-01-22 - 最少的砝码

Question

【每日一题】- 2021-01-22 - 最少的砝码

azl397985856 opened this issue 3 years ago · 2 comments

azl397985856 commented 3 years ago

如何用尽可能少的砝码称量出 [0, n] 之间的所有重量？（只能在天平的一端放砝码）

Answer 1 · 2021-01-22T08:44:02.000Z

可以使用砝码 [1,2,4,8, ... 2 ^ i] 其中 i 为数组索引, 且i 为满足 2 ^ i <= n 的最大索引，也就是 $\log_{2}n$ 取地板。

代码方面可以直接使用上面的 log 求解即可。如果不能使用内置的 log 函数，也可以使用二分搜索简易实现，具体可参考二分讲义。

Answer 2 · 2021-03-26T12:25:08.000Z

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.