最少砝码 Java解决

2744557306

问题描述】
& N$ @/ p& \8 X; }你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
: S# o+ U" }0 A& S' t注意砝码可以放在天平两边。

【输入格式】
输入包含一个正整数 N。
9 U  Q/ T/ ]  Z  O4 q' G
【输出格式】
输出一个整数代表答案。

【样例输入】
# x  }- G" G. H# H8 P7
+ ]% q6 \7 h/ L. K4 J
【样例输出】
3

【样例说明】
: n1 x" \: s" b3 u6 J3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
$ J5 P4 g( g) W1 W2 n0 Q- \2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
3 B" ~1 u) v% y  C5 V. V4 = 4；
; p# |, H, T+ i6 W; P. s  L5 = 6 − 1；
6 = 6；
2 T& c. X% I9 F( n1 u% Q7 = 1 + 6；
  P1 X4 @- K& Q少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  2 @7 N8 w* U# M6 Q4 n( L; Q3 g/ J
   
2. public class Main {  
   $ }0 E' X2 E) w. B
3.     public static void main(String[] args) {  
   9 {* t% Q: v& F( o1 q9 B
4.         int n = new Scanner(System.in).nextInt();   
   0 l3 Y2 ]2 i) m- M\" J. G
5.         int maxWeight = 1, minCnt = 1;  8 w  I5 l, }# W
   
6.         while (maxWeight < n) {  
   ; c( x2 d) U8 `: Q\" _4 ~5 M3 x\" ~) C5 r
7.             maxWeight = maxWeight * 3 + 1;  1 z; P  l2 b. B
   
8.             minCnt++;  
   # b) ^2 r5 p7 s/ t\" T
9.         }  3 Z- ]; @$ Z2 ]7 |/ E. I
   
10.         System.out.println(minCnt);  \" J% k0 G  Q2 C* g9 W3 v
    
11.     }  
    % n6 a5 d) [% F, E$ U
12. }
    + R% y4 h& O2 @# t

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
2 v. \0 f* t( h5 `此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
2 \+ o7 Q' M: b: G7 I所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

8 V4 s' J: w7 I让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
( {' z( e: _9 i; G2 J
另 n + 1 = k - n k = 2n + 1
7 \- S6 z/ k! v  s; v8 v那么x + 1可以控制的最范围就是[1, 3n + 1]
6 w; {& e# w4 ?8 C0 W# u. V+ Q4 ?6 W
7 r: X2 A% K# {+ Y0 `( u& g
, b# v. a: a( x- m$ m& T5 E3 m