最少砝码 Java解决

2744557306

问题描述】
% `% `8 G, |4 i你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
3 H' A/ z% w7 Z& C9 Z注意砝码可以放在天平两边。
  T9 _$ ?, q+ ]* U# h6 \0 h* @, F
1 Y7 h" k( Y  m6 R0 k【输入格式】
" ]( [' R  F) n+ T" v7 l输入包含一个正整数 N。
. I1 O7 L" D& g* J
【输出格式】
: ^& |1 _: k; `. g, Y输出一个整数代表答案。
. |' g! V8 ]9 Q; j2 W5 E3 H* E
. g! z% \) s# \2 }+ t9 ?( f) g【样例输入】
7
& U+ Y" N- [% o" q( z! u0 M
2 i4 k' r2 }3 W: l" [! a; j, Z6 Y【样例输出】
3

% d1 j* E3 l# `3 B  ^( ^  J2 l6 k【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
9 o% I2 B+ W5 w: |8 y4 R$ Z1 = 1；
- W- v0 ^: W- r. M$ c9 F' V7 O2 = 6 − 4 (天平一边放 6，另一边放 4)；
, V+ s3 n' f8 `: H' P2 ?1 b3 = 4 − 1；
4 = 4；
5 = 6 − 1；
$ w: g- R8 s! V  U: S1 h6 = 6；
' d  P8 K+ V& Q- u, J7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   - _- O& d* b7 N
2. public class Main {  
   7 E5 q. m, T. \9 X
3.     public static void main(String[] args) {  . ]& Q5 i% l. K
   
4.         int n = new Scanner(System.in).nextInt();    8 r8 S/ @( ]$ Z9 N$ V4 a& |
   
5.         int maxWeight = 1, minCnt = 1;  
   , Z: G( _% V% ]& ?
6.         while (maxWeight < n) {  : F; R4 m& n8 m6 ?- a! Q& ^
   
7.             maxWeight = maxWeight * 3 + 1;  
   \" s& a9 ^3 O0 f$ U- P; ]' [
8.             minCnt++;  ' K- A3 n8 a; U- w
   
9.         }  
   ( m, t1 Q; E8 }/ y0 q- l7 F
10.         System.out.println(minCnt);  
    * O* \5 k- L0 |# h* {. ^
11.     }  
    5 }\" ^' L7 _; I( n\" ~\" A
12. }\" M# V8 [- g# S! m
    

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
+ v2 g# T  [4 \" G因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

另 n + 1 = k - n k = 2n + 1
) }' B' E; d  D  L% V那么x + 1可以控制的最范围就是[1, 3n + 1]
7 I7 L! `) P& e( k3 Y
3 k6 B4 k: E2 U6 v% a. ]( }4 g
" b( q& p7 s+ G/ v
* ]5 g/ l7 [; Q8 {% U