最少砝码 Java解决

2744557306

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

. s8 z2 c: c. n2 `【输入格式】
/ f9 s! K4 ]$ C; ]2 p# ^输入包含一个正整数 N。
% L. i# Z+ B; v1 D: S
, y! }8 R' H% a- O9 }# \+ b( {【输出格式】
) `9 [2 n' X" i: x4 t8 H9 V5 a输出一个整数代表答案。
. X' r+ F. X( Y/ G. g4 [* `# [4 w0 K
【样例输入】
7

【样例输出】
3

【样例说明】
/ g" [+ @9 i$ s. {' M3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
3 ^8 W  ]: o: X2 = 6 − 4 (天平一边放 6，另一边放 4)；
: l; i: `. Z8 Q. r6 [# J3 = 4 − 1；
% I+ L  X/ ?2 c% S/ h- v; B4 = 4；
5 = 6 − 1；
6 = 6；
' D: @0 H4 t! _0 A) L7 g, D: R1 M7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   8 j' I) t$ t1 R1 h' H2 T9 G
2. public class Main {  
   / ]0 s. B9 i7 z. W$ ?0 g- `
3.     public static void main(String[] args) {  
   + V0 {( u0 _; w+ |* a6 c) P, |; j3 [% h
4.         int n = new Scanner(System.in).nextInt();    & M% c4 ^% J& d- e
   
5.         int maxWeight = 1, minCnt = 1;  
   ( p4 A2 h1 `4 E
6.         while (maxWeight < n) {  9 M  r1 }& u; ?
   
7.             maxWeight = maxWeight * 3 + 1;  
   3 A\" q& T; h+ a! ]+ ^- ~
8.             minCnt++;  
   ) ]( G! v6 M- |& t1 T( z
9.         }  
   - f5 ~* g\" w: i  w5 t
10.         System.out.println(minCnt);  
    * j: Z7 S( S% F
11.     }  
    . S* u+ }8 C2 E2 Y0 @3 y' W+ ?
12. }$ \8 |- V8 [! n; I6 ]2 C: F4 z
    

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
' z5 [" I, ]$ k& j6 U) V& T0 E此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
! d& M) N" s9 ]; U因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
4 F+ _7 S2 j/ z所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
$ q2 ^: j  H& l3 J: u
让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

另 n + 1 = k - n k = 2n + 1
那么x + 1可以控制的最范围就是[1, 3n + 1]

8 b( y, I6 [3 Y4 o7 @. f# n; h5 s

% l. z" ^4 y3 m9 j