「数理逻辑」| 德·梅齐利亚克砝码！
2020-12-07 本文已影响0人
彭旭锐
前言
- 在计算机面试中，逻辑类题目是规模以上互联网公司的必考题。由于题目花样百出，准备难度较大，题海战术可能不是推荐的做法。
- 在这个系列里，我将精选十道非常经典的逻辑题，希望能帮助你找到解题思路 / 技巧。如果能帮上忙，请务必点赞加关注，这真的对我非常重要。
系列文章
【持续更新】
1. 德·梅齐利亚克砝码
1.1 题目描述
给定一台天平，至少要几个砝码，可以称出 1g ~ 40g 这 40 个重量？
这个问题等同于 “德·梅齐利亚克砝码”问题：
一位商人有一个 40 磅的砝码，由于跌落在地而碎成4 块。后来，称得每块碎片的重量都是整磅数，而且可以用这 4 块来称从 1 ~ 40 磅之间的任意整数磅的重物。（引用自法国数学家 G.B.德·梅齐里亚克）
问这 4 块砝码碎片各重多少？
1.2 解题关键
- 1、砝码的和与差
假设有 m 和 n 两个砝码（m > n），除了可以称出 m+n 的重量外，还可以称出 m-n 的重量。
1.3 题解
现在，我们来具体阐述这道题的解题过程：
令 表示第
块砝码的重量。
- 第 1 块砝码：
显然地，为了称取重量 1g ，必须拥有一枚重量为 1g 的砝码，即：。
- 第 2 块砝码：
令第 2 块砝码重量为，此时我们有砝码
，可以称出重量
为了称取重量 2 g，显然有，即：
，目前可以称出
。
- 第 3 块砝码：
令第 3 块砝码重量为，此时我们有砝码
，可以称出重量
为了称取重量 5 g，显然有，即：
，目前可以称出
。
- 第 4 块砝码：
同理，可以得出第 4 块砝码 ，可以称出
。
此时，，总共需要 4 块砝码。
论毕。
参考资料
- 《拜托，面试别再问我三进制了！！！》 —— 沈剑 著
- 《世界上最完美的砝码组合---神秘的“3”重现江湖！》 —— 隔壁家的二傻子 著
创作不易，你的「三连」是丑丑最大的动力，我们下次见！
