彭丑丑

V1

2022/09/01阅读:16主题:山吹

至少要几个砝码,可以称出 1g ~ 40g 重量

请点赞关注,你的支持对我意义重大。

🔥 Hi,我是小彭。本文已收录到 GitHub · AndroidFamily 中。这里有 Android 进阶成长知识体系,有志同道合的朋友,关注公众号 [彭旭锐] 带你建立核心竞争力。

前言

大家好,我是小彭。

在计算机面试中,逻辑类题目是规模以上互联网公司的必考题。由于题目花样百出,准备难度较大,题海战术可能不是推荐的做法。在这个系列里,我将精选十道非常经典的逻辑题,希望能帮助你找到解题思路 / 技巧。如果能帮上忙,请务必点赞加关注,这真的对我非常重要。


系列文章:


1. 问题描述

给定一台天平,至少要几个砝码,可以称出 1g ~ 40g 这 40 个重量?

这个问题等同于 “德·梅齐利亚克砝码”问题:一位商人有一个 40 磅的砝码,由于跌落在地而碎成4 块。后来,称得每块碎片的重量都是整磅数,而且可以用这 4 块来称从 1 ~ 40 磅之间的任意整数磅的重物。(引用自法国数学家 G.B.德·梅齐里亚克)问这 4 块砝码碎片各重多少?


2.解题关键

砝码的和与差: 假设有 m 和 n 两个砝码(m > n),除了可以称出 m + n 的重量外,还可以称出 m - n 的重量。


3. 题解

令  表示第 块砝码的重量。

  • 第 1 块砝码 :为了称取重量 1g ,必须拥有一枚重量为 1g 的砝码,即 = 1。目前可以称 {1, 2, 3}。
  • 第 2 块砝码 :砝码组 ,可以称出 。为了称取重量 2g,显然有 - 1 = 2,即 = 3。目前可以称 {1, 2, 3, 4}。
  • 第 3 块砝码 :砝码组 ,可以称出 。为了称取重量 5g,显然有 - 4 = 5,即 = 9。目前可以称 {1, 2, 3, 4, ..., 13}。
  • 第 4 块砝码:同理,第 4 块砝码 = 27,可以称出 。总共需要 4 个砝码。

参考资料

我是小彭,带你构建 Android 知识体系。技术和职场问题,请关注公众号 [彭旭锐] 私信我提问。

分类:

移动端开发

标签:

Android

作者介绍

彭丑丑
V1