最少砝码 Java解决

2744557306

问题描述】
7 c" d- a$ d) `: g你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
  E1 N/ y6 `( o7 P* R那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。
( }9 r* l: k; E+ j
【输入格式】
8 G) k& X, j4 O& v1 z$ c输入包含一个正整数 N。

【输出格式】
输出一个整数代表答案。
- ]* }" d% R* H. R
【样例输入】
9 ?$ S" k: L3 p7

+ e5 \  Z7 R( y6 ?【样例输出】
3

- E2 H0 R. u* e5 t. K$ j- ~& N; R( \' A【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
% Q* v! m$ P! f6 v; d3 g  S* }( A3 = 4 − 1；
, w3 A1 x# Z1 z) N; f' P4 = 4；
5 = 6 − 1；
: O7 Y/ J  `1 F6 = 6；
7 = 1 + 6；
" v6 ~% e/ v( v9 [( A% R! L; @7 N少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  \" O  [' A9 [7 Z8 P  ~& V# I
   
2. public class Main {  # T* Z8 w4 V4 D
   
3.     public static void main(String[] args) {  1 h9 o/ M$ y2 n/ c8 G$ j3 u
   
4.         int n = new Scanner(System.in).nextInt();   
   3 K! Z3 S  r6 V7 u3 t# B  g
5.         int maxWeight = 1, minCnt = 1;  
   3 K/ b+ i7 P; n3 y\" |
6.         while (maxWeight < n) {  
   + A4 S' R/ |+ m6 g! {\" q
7.             maxWeight = maxWeight * 3 + 1;  # b2 k8 C7 S0 c$ u3 F, N' d2 V+ I
   
8.             minCnt++;  # A7 ]* N4 C# N+ k' }: E
   
9.         }  
   2 `6 H- S# u5 G. q( B$ v
10.         System.out.println(minCnt);  
    : @3 {2 O; Y: K% @& I$ T& O  q& M
11.     }  
    / K7 m- p! q$ a( N7 u( p- q8 [
12. }
    , y. e4 i3 K\" j$ v! i; y

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
. ?7 w9 |( B( y' q# B& D: G此时我们想扩大区间范围就只可以增加砝码
& ?3 R9 L& H6 X1 y假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
7 {- t3 C! N1 b
另 n + 1 = k - n k = 2n + 1
: P' S* K3 i2 D. X8 h4 M$ r那么x + 1可以控制的最范围就是[1, 3n + 1]


' ?. p: M- G' `$ n" T6 V
: g6 z# R3 u+ h$ Z5 \" d