最少砝码 Java解决

2744557306

问题描述】
! D9 o- P$ P  ]* _3 t9 S. H7 N! T你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
. P+ n7 n+ ~4 |% B那么这套砝码最少需要包含多少个砝码？
# T$ V. S6 j6 l4 C, W注意砝码可以放在天平两边。
1 `9 h7 A( z2 T
- e: Q( |" m; |: k( t【输入格式】
" o4 v" r! \$ g0 Y4 m$ B3 L输入包含一个正整数 N。
% |! E: B* X; B( T2 d
【输出格式】
输出一个整数代表答案。

【样例输入】
7

【样例输出】
3
4 l, C5 ^; B1 o: K4 b
! l9 R, p% I3 q8 u- i2 A" z. i4 U【样例说明】
) _- K/ v. Q1 }! b( W3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
# m+ y% p$ D$ v. c& _1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
6 z- m) b. ?8 V- ^9 i3 = 4 − 1；
4 = 4；
5 = 6 − 1；
( w- S1 C% Q7 l6 = 6；
; x$ r6 i) \/ x$ l: X9 L6 C7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  4 V* d. Z8 f: i8 E; O
   
2. public class Main {  
   * ?* _, [  a0 P6 R\" v1 G; x
3.     public static void main(String[] args) {  * ~! B5 _\" F: @6 B
   
4.         int n = new Scanner(System.in).nextInt();   
   7 L: R; y1 T. T' u% }
5.         int maxWeight = 1, minCnt = 1;  ; Q. Z+ a5 O0 E  d\" t
   
6.         while (maxWeight < n) {  
   2 `9 f: ^& Q2 s+ b' m' j! L
7.             maxWeight = maxWeight * 3 + 1;  9 N  m6 r) J/ p7 V4 E
   
8.             minCnt++;  ' |+ H: `- m3 Y0 m. b5 V\" r
   
9.         }  % D2 v\" j4 h+ y. v6 A1 V6 c2 {4 S
   
10.         System.out.println(minCnt);  
    / {2 ]* W- x- G: v0 ]\" G
11.     }  
    ! S# ], ^; N  }! y, \3 N
12. }0 r* F7 ?\" y8 B3 x
    

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
( d; h9 c2 o# Y) V( r# |* W5 o此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
& P& R5 r" ^4 a; i7 c因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
! d8 \; \8 b5 k2 p, b9 j0 C所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

! V+ C0 g' s0 G2 ^6 w+ V% q让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

另 n + 1 = k - n k = 2n + 1
, |+ z" v3 a, E$ B1 [& \* \那么x + 1可以控制的最范围就是[1, 3n + 1]
7 @+ f3 E3 V% A& `9 V% A

( `8 F8 v, s+ z
4 g0 S( p+ N& V# V- F* V' }