最少砝码 Java解决

2744557306

问题描述】
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
9 _1 i, w3 @7 Y/ M' d- c那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。
: G& a2 v% l5 W  e
/ T" W1 O0 T8 Z3 p1 j【输入格式】
( {/ \0 U# _9 r8 B" `输入包含一个正整数 N。
; V% W6 O- B4 O) E, }# m5 H
【输出格式】
& @- K5 R9 p1 L3 o0 Z& y输出一个整数代表答案。

【样例输入】
) b5 J. v: |( m* y6 A7
; p5 e$ i; y* g+ {6 D
  l% m# @- P0 M/ T+ }【样例输出】
3
9 X( _+ A8 B% k- c& ]5 C
【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
+ f1 L5 Y/ Y- e2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
5 = 6 − 1；
+ l. R$ }# A+ a. M/ K  Y. m6 = 6；
7 = 1 + 6；
2 }: x( R5 |* `1 T- D少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   , g) ]$ h( d0 f2 e
2. public class Main {  , v6 P# G4 E\" L+ i# }' Z+ l
   
3.     public static void main(String[] args) {  $ ^; s9 W: `( q5 X  V, b6 X- q
   
4.         int n = new Scanner(System.in).nextInt();    9 H7 l- ]* T2 v% ^  w* I) T  ^6 ?
   
5.         int maxWeight = 1, minCnt = 1;  ! w* E% w# r# F7 L. r
   
6.         while (maxWeight < n) {  6 x) L% a\" C$ |. [7 s8 m( ?
   
7.             maxWeight = maxWeight * 3 + 1;  
   0 R* Q4 u. Y: A& p
8.             minCnt++;  
   3 t$ A5 U6 @( b
9.         }  * Q8 R% W\" F* }& f0 u3 j3 t
   
10.         System.out.println(minCnt);  & L# X* N8 f2 U4 u8 X$ h& |
    
11.     }  
    : Y& d  b5 E: v
12. }$ B9 s\" q- \% U\" P6 ^\" j  ~
    

复制代码

题解
  O; k' `& Y, @: Y: ^4 t如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
+ ~8 q. G/ F* m, @, l4 L0 q因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
9 S) Y/ r$ B8 r8 Q  J+ k0 F# V  k所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
* c- r/ P/ K3 g& X8 j
" E3 |- g: q! G9 F/ v* o另 n + 1 = k - n k = 2n + 1
) J4 _% q7 ]6 O# G那么x + 1可以控制的最范围就是[1, 3n + 1]

: b$ p% {5 [; N& U

. X3 i9 c* W- m. S$ m6 H