最少砝码 Java解决

2744557306

问题描述】
4 |; |$ _* |2 r6 |你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
$ z3 r' H) b6 f0 k) K6 N那么这套砝码最少需要包含多少个砝码？
! d: W  }6 n4 _- Y+ j注意砝码可以放在天平两边。

1 G  `+ Q8 I7 z: v9 e$ z: X; J【输入格式】
输入包含一个正整数 N。

【输出格式】
- X8 N$ s+ Y, ?$ o9 n) h; W输出一个整数代表答案。

【样例输入】
7
/ x  M& M/ c. o: u) O" Z# r- b
5 {* U% t7 y1 i$ A【样例输出】
6 k) [) z3 |6 r: F# a3

' x) {% m( h  l+ @, |【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
: Y( s: m6 W# g1 = 1；
. T! e, `- d7 Y6 H) z3 r2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
5 = 6 − 1；
6 = 6；
7 = 1 + 6；
+ f2 n  \/ P! ~: ]. i少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  + t( ]( Z& @3 W. S) [. X! s& w1 ~3 D
   
2. public class Main {  
   . @; B! R- s3 u& X
3.     public static void main(String[] args) {  % a- G; A, Q) f/ `1 _
   
4.         int n = new Scanner(System.in).nextInt();   
     W; X+ J& D$ `  a/ [
5.         int maxWeight = 1, minCnt = 1;  , j, a8 C* Z( E5 N) F. E, A
   
6.         while (maxWeight < n) {  
   ! h% j, X* F0 J6 y
7.             maxWeight = maxWeight * 3 + 1;  
   9 B: T- g) {! W6 o9 d
8.             minCnt++;    A5 {2 S- e  l% t) n
   
9.         }  ) z* I5 e2 T. R: y# b
   
10.         System.out.println(minCnt);  
    ) W/ w% _) [7 N( O: i\" A1 Q
11.     }  
    ' ^9 g; T) [: X% f* i) T
12. }
    2 l; |/ @* P% x8 e# h% B

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
7 N- z, l2 u" g8 q因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
+ t# v4 b/ P" s: G9 A0 \/ c  s: H所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
* N% S. m" Y. p0 f$ W3 G
' N% l+ {* M. }; d+ ]! I% D: _- e让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

& |& G1 z- j) k1 o- j; `8 a$ B: @: [另 n + 1 = k - n k = 2n + 1
' \. R9 ~4 V. f4 E) x6 F3 g9 P那么x + 1可以控制的最范围就是[1, 3n + 1]


% E! o. N" i8 \( l1 f
. j( V! ]7 X; d, @6 R& e1 s6 ?