最少砝码 Java解决

2744557306

问题描述】
. }6 c9 B& y2 `你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
  |. _" D8 s. r6 w那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。

【输入格式】
+ Z4 d+ p! ]8 H. {输入包含一个正整数 N。
4 X$ }' |4 H0 _, }5 J! m
9 k$ C# L5 F% f6 J0 [# O【输出格式】
. p  s; I9 f5 |) v  h5 C9 W输出一个整数代表答案。
% `0 L+ v$ s/ W8 A" I* b* [
: i" V  f# Z3 c: }  ?9 c【样例输入】
, k- o' U6 j6 E9 s7

【样例输出】
8 F; s7 Q) |( n% _. g" j! m" E" ]9 u3

3 ?9 r7 o- x" d8 I9 N: ?$ S8 E【样例说明】
- ~& l2 e  a) y0 n1 e8 s7 w3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
. u' r6 [! o" j% K7 M3 z3 [5 M( d3 = 4 − 1；
, k' t! j- J) w. r/ ~( ?- T4 = 4；
5 = 6 − 1；
4 x0 u3 h0 U% ~1 H$ O# F# @6 = 6；
6 K" w# }+ K' O+ ]1 Z& ^! g7 = 1 + 6；
. [3 q6 r; z% X1 _+ r少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   ! T4 A, s8 t/ Q0 R- ]
2. public class Main {    N! \' O- Q! f+ t+ }
   
3.     public static void main(String[] args) {  
   - M+ t+ F0 @' X\" b- ]
4.         int n = new Scanner(System.in).nextInt();   
   + y0 y/ t) y# V& m+ K: X
5.         int maxWeight = 1, minCnt = 1;  ) w2 C9 y! g3 n( s0 A0 q9 u' k& c
   
6.         while (maxWeight < n) {  0 n: c: v: h\" t* V1 Y
   
7.             maxWeight = maxWeight * 3 + 1;  
   ' G  p, |1 V& i+ B6 l3 d
8.             minCnt++;  
   . a\" Q0 _3 l# G2 @- P% ]
9.         }  ( _+ O4 V6 b) v2 r/ D; I! }, `
   
10.         System.out.println(minCnt);  : z2 _! q1 T; l\" F; g! L5 ?+ p& A
    
11.     }  8 |' x$ O) B, b
    
12. }3 ?+ P5 f5 t- A
    

复制代码

题解
3 _8 Z( G. Z6 Y2 x8 b8 e* i+ P如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
* x1 K- T( x% Y$ D. d所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
7 J2 K% P8 v6 j, p# ~2 a( N2 \
让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

另 n + 1 = k - n k = 2n + 1
3 r0 K- H" [/ w% ^3 ?' h# d那么x + 1可以控制的最范围就是[1, 3n + 1]
/ y3 R6 ~) N5 C( `; A. k) a3 U


/ y1 E2 F$ {9 ?' g# J1 d! N: l, h% f8 ^