最少砝码—省赛java

十二届蓝桥杯省赛真题G题—砝码称重

【问题描述】

你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。

【输入格式】

输入包含一个正整数 N。

【输出格式】

输出一个整数代表答案。

【样例输入】

7

【样例输出】

3

【样例说明】

3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
5 = 6 − 1；
6 = 6；
7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

学好数学，少走弯路（等比数列）

硬找规律真不好找，但是思考助力前行

方法：

前提是所选的砝码的重量都是要小于n的

• 如果n = 1；必须选1
• 比1重的，也必须都要有1作为起始
• 选1.2砝码可以满足1 = 1，2 = 2， 3 = 1+2止步于此
• 选1.3砝码可以满足1 = 1，2 = 3-1，3 = 3，4 = 1+3止步于此（最大重量为4）
• 选1.4砝码可以满足1 = 1，2 = 未知（不合适）

到此规律浮现：砝码1，3，9，27…这样选可以选得最少的砝码

也就是公比为3的选

规律：

import java.util.Scanner;public class G_砝码称重 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int weight = 1;//对应砝码序列的重量int count = 1;//砝码个数int total = 0;//总重量while (total < n) {count++;weight *= 3;total += weight;}System.out.println(count);}}

参考链接：看的小小风0的博客