最少砝码 Java解决

2744557306

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

【输入格式】
输入包含一个正整数 N。
4 T6 _, b0 \# \6 N
, `% R4 y. f) ~% s: w" X/ o) D4 N( I【输出格式】
- ^, D' E- U) d) F9 Z输出一个整数代表答案。

【样例输入】
, i5 H. O9 x5 B9 a$ S9 u7
; I6 T- Y4 {& p
【样例输出】
3

2 R& I  S  b; M: r9 P4 \【样例说明】
7 \' _5 u- N! @; x3 J3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
7 J; C8 c2 Q* {# R; i( J) ^2 F( H1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
0 o3 I) d) i, R" `) \3 = 4 − 1；
4 = 4；
0 ^" K+ K. M* _# z* z5 = 6 − 1；
6 = 6；
0 I  |, h- b( Q+ Y3 Q5 L7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  2 {  Q\" V8 }1 u  w( O; k. X' o
   
2. public class Main {  4 L! F# r0 S5 O& l
   
3.     public static void main(String[] args) {  9 N7 \) R/ B; C& ~
   
4.         int n = new Scanner(System.in).nextInt();    / L0 K4 p4 L( u$ p! ~5 M, [2 d
   
5.         int maxWeight = 1, minCnt = 1;  
   ) \9 A* P\" m\" l
6.         while (maxWeight < n) {  7 D  }& Q: W0 s& x, S' ]9 g
   
7.             maxWeight = maxWeight * 3 + 1;  
   $ N( D* k# j* F$ W7 N. C* Q
8.             minCnt++;  0 m: K' _. P/ K( d
   
9.         }  
   5 ?! o$ E7 B1 Y$ }/ l
10.         System.out.println(minCnt);  ( g6 C: ^! N0 V2 W1 V  v
    
11.     }  
    0 T6 J- P' w/ n0 \9 d
12. }# E7 Y, {9 L$ N
    

复制代码

题解
& T' j& T' _9 h6 u% k- u如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
0 m$ A% {% S7 w: w) P0 o  n' e此时我们想扩大区间范围就只可以增加砝码
# R) p0 r+ g- I7 l: U8 c/ @假设增加的砝码重量为 k
( E# j: p* V2 H7 J  K因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
  d% R0 F& W3 S; A  S& A+ v0 d所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
0 r6 o. W. ^0 _: u* Y( s
另 n + 1 = k - n k = 2n + 1
" G9 L/ p$ @) P- B9 X那么x + 1可以控制的最范围就是[1, 3n + 1]
- W0 B: b" L- s% r$ D: J% H
7 i. I' t) l: j& M% Z* a

( `  m$ t4 c: S$ v; l" X3 @