最少砝码 Java解决

2744557306

问题描述】
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
! r' o9 w3 p. R2 ?  C注意砝码可以放在天平两边。
. u3 W* j! B; v' B' i, Z
【输入格式】
输入包含一个正整数 N。

【输出格式】
5 t* c0 r# v5 Q, V% w输出一个整数代表答案。
( Y4 n# s6 A9 t8 B8 j  p+ j, v
【样例输入】
7
* h3 v7 B, A; a% I
【样例输出】
3

8 g4 _! X% ^; O, w. o' D3 \【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
  Z; u( [) C+ ^. D' R' {* z2 = 6 − 4 (天平一边放 6，另一边放 4)；
+ X' _) H# P& T% E) P1 w$ {3 = 4 − 1；
4 = 4；
5 = 6 − 1；
+ [2 s' J) w& D; X, d6 = 6；
. X- F- d7 y+ D  v* f' y: b7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   % @9 j. L6 W! j. m; u/ `8 a9 L
2. public class Main {  - {3 V* R- A( d* e; }  _
   
3.     public static void main(String[] args) {  : G! M0 H- ~& {  k1 G- P) L
   
4.         int n = new Scanner(System.in).nextInt();   
   ; P& ?$ y* ]7 o* ?9 }
5.         int maxWeight = 1, minCnt = 1;  
   * h+ }9 z! P6 h6 q. d/ R
6.         while (maxWeight < n) {  
   2 A' `( P6 R( K; ]- L5 M
7.             maxWeight = maxWeight * 3 + 1;  7 ~% N7 z; H\" x0 E
   
8.             minCnt++;  ' P( N; `( I% S6 M9 i+ @- t! a' |
   
9.         }  
   2 n' p9 T% c\" @/ B
10.         System.out.println(minCnt);  . \2 m9 Y# ?6 h. i
    
11.     }  
    1 L7 t% L+ e& A7 i0 a4 P- k
12. }# B, E: z  d$ E$ a  ^6 z* G
    

复制代码

题解
' y5 N" Z1 C. Z  l" y  a# G如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
( i" {9 S" c7 X& C
让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
5 _4 x- C; p  V
4 K9 v- N: V+ B, x  j( a另 n + 1 = k - n k = 2n + 1
那么x + 1可以控制的最范围就是[1, 3n + 1]
, @4 a9 A/ z; V0 d" Q  ]4 K  o
, g. y3 h# g9 I3 ^