经典的数学问题，“天平称重问题”——java代码实现，原理及解析

经典的数学问题，“天平称重问题”——java代码实现，原理及解析

天平称重原理

首先，我们知道，一个数 N 的二进制表示中最高位的位数加一，就是 N 在二进制下的位数（也就是最高位是第几位）。例如，如果 N=10，那么 N 的二进制表示是 1010，其中最高位是第四位，所以 N 在二进制下的位数为 4。

接下来，我们考虑如何用一个公式来计算 N 在二进制下的位数。我们知道，如果将一个数 N 进行对数运算，对数的底数可以是任意正数。因此，我们可以使用以 2 为底数的对数，即 log2(N)，来计算 N 在二进制下的位数。

然而，在 Java 中，Math 类中没有提供以 2 为底数的对数函数。但是，我们可以使用换底公式，将以任意底数 a 的对数转换为以另一个底数 b 的对数。具体地，对于任意正数 N，有以下公式成立：

logb(N) = loga(N) / loga(b) 

其中，loga(N) 表示以底数 a 的对数，loga(b) 表示以底数 a 的 b 的对数。

因此，我们可以将以 2 为底数的对数转换为以自然数 e 为底数的对数，即：

log2(N) = loge(N) / loge(2)

然后，我们可以使用 Java 的 Math 类中的 log 方法，来计算自然数 e 为底数的对数。具体地，(Math.log(N) / Math.log(2)) 表示以 2 为底数的对数，再加上 1，就是 N 在二进制下的位数，即最高位的位数加一。

因此，我们使用 (Math.log(N) / Math.log(2)) + 1 这个公式，来计算 N 在二进制下的位数，也就是最高位的位数加一。

----------------------------------------------------------------------------------------------------------------------------------------

问题描述

        你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意 小于等于 N 的正整数重量。

        那么这套砝码最少需要包含多少个砝码？

        注意砝码可以放在天平两边。
输入格式

        输入包含一个正整数 N。
输出格式

        输出一个整数代表答案。
样例输入

7

样例输出

3

样例说明

33 个砝码重量是 1、4、61、4、6，可以称出 11 至 77的所有重量。

1 = 1；1=1；

2 = 6 − 42=6−4(天平一边放 66，另一边放 44)；

3 = 4 − 1；3=4−1；

4 = 4；4=4；

5 = 6 − 1；5=6−1；

6 = 6；6=6；

7 = 1 + 6；7=1+6；

少于 33 个砝码不可能称出 11 至 77​ 的所有重量。
评测用例规模与约定

对于所有评测用例，1 ≤ N ≤ 10000000001≤N≤1000000000。
运行限制

    最大运行时间：1s
    最大运行内存: 512M
核心代码：

public static int minimumWeights(int N) {int k = (int) (Math.log(N) / Math.log(2)) + 1;return k;
}

完整代码：

import java.util.Scanner;public class fama {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);System.out.print("请输入一个正整数：");try {long N = Long();int k = (int) (Math.log(N) / Math.log(2)) + 1;System.out.println("需要的砝码数量为：" + k);} catch (Exception e) {System.out.println("输入的不是正整数！");}}
}