最少砝码 Java解决

2744557306

问题描述】
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
) w( o: o9 U& J6 c- A注意砝码可以放在天平两边。

【输入格式】
9 G+ F5 x1 @4 V; g输入包含一个正整数 N。

# S4 a5 p( E+ D7 P【输出格式】
输出一个整数代表答案。
3 z6 x& H. U7 l+ C) m' s+ F9 m
, M, _% q( ]5 D# Z7 K4 E$ C" J+ K0 S【样例输入】
7
. S* G. d  R( Z% t
【样例输出】
4 k7 `* N( f, [/ D8 l3

【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
* L  B+ x* w3 e$ S1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
' j2 D7 r4 _' A; X7 ?+ P) ^3 = 4 − 1；
" i  t6 g0 J) b3 v8 K$ ?4 = 4；
5 = 6 − 1；
6 = 6；
7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   3 W- L2 t& u3 C
2. public class Main {  
   ; Y# V5 S& p* b
3.     public static void main(String[] args) {  
   ' d0 n7 |, }8 W- y$ I
4.         int n = new Scanner(System.in).nextInt();   
   0 j8 W; J- v( k9 U7 ~
5.         int maxWeight = 1, minCnt = 1;  6 O- x, `: a\" t/ H5 I. b  E/ X. U
   
6.         while (maxWeight < n) {  
   % ^% S; W; X\" o  w5 F
7.             maxWeight = maxWeight * 3 + 1;  9 a& H# t1 F5 J0 l
   
8.             minCnt++;  \" I+ Y/ y2 t! d8 N5 [2 v' M9 h, Y
   
9.         }  
   . r- s4 A$ ]% L+ F$ N4 o/ D% W
10.         System.out.println(minCnt);  6 H. v& y; l, n  H% I: y
    
11.     }  
    / j7 g8 G0 P, B$ G* K
12. }\" K( l2 @1 p& U( F( F/ a+ u
    

复制代码

题解
3 F# M3 o' ~1 `9 J! ^5 X  V) s! Z如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
9 Z: o( k$ `* q& _. p! q此时我们想扩大区间范围就只可以增加砝码
3 l- S8 i! [. E" F假设增加的砝码重量为 k
7 \0 d! w9 H: V" m1 ^$ _因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

0 P/ l8 U* _7 l9 C, c; b( _* y另 n + 1 = k - n k = 2n + 1
& G+ w3 I, E5 C) K0 \/ X那么x + 1可以控制的最范围就是[1, 3n + 1]

4 z2 v! r* S2 @# a+ Q/ d/ h2 d