最少砝码 Java解决

2744557306

问题描述】
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
; X5 s2 q9 m# q那么这套砝码最少需要包含多少个砝码？
7 G: k' H' I4 N. n, Y注意砝码可以放在天平两边。

【输入格式】
输入包含一个正整数 N。
6 Y- @  G( h# P
8 |4 k. M+ }- d9 s【输出格式】
输出一个整数代表答案。

  o# ^! c' n6 {【样例输入】
. P, l! m& O! I( n7
$ q$ \) `& e; i3 J, V$ J3 m4 ^
【样例输出】
! u+ ?1 A) ~: Q7 e+ I# i6 r3

【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
$ p+ h* ?- e0 U8 f  n: f8 j2 = 6 − 4 (天平一边放 6，另一边放 4)；
7 v" [' j) \1 \- |) J6 L3 = 4 − 1；
* K9 g  |$ _% X& P4 = 4；
6 m  @! {8 N- C% @5 = 6 − 1；
+ q' z1 A# ?1 J* J0 K% V) b& d6 = 6；
7 = 1 + 6；
9 ~, q# y( W4 W# P& o+ n少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  ; ?; r. ^( _/ Y- I/ k2 S7 o( S& b
   
2. public class Main {  : v: p5 M& [$ I# ?  H! v
   
3.     public static void main(String[] args) {  \" }5 B9 P9 |/ o8 G\" z1 O8 @/ h$ m
   
4.         int n = new Scanner(System.in).nextInt();    ( U; t  `, J9 n$ B& ?8 ~8 O
   
5.         int maxWeight = 1, minCnt = 1;  
   / M4 V% n1 e. _2 D7 ?5 f2 W
6.         while (maxWeight < n) {  
   % m/ N3 |/ R6 H2 v7 c
7.             maxWeight = maxWeight * 3 + 1;  
   7 g# y& R$ F# u2 O
8.             minCnt++;  2 a5 ^* R% M\" i: A2 A
   
9.         }  
   * c6 m  C: U0 e0 g, k: R% X
10.         System.out.println(minCnt);  ; v# [; w$ \/ R- v; A
    
11.     }  6 h' `5 V- x7 @9 C8 }
    
12. }- Q5 k! }* X; P6 J9 v2 s
    

复制代码

题解
# Q/ r  c( c9 h  }4 e3 q' q! y如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
( V% B* z; H( I此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
: V: \/ S- k3 G所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
5 v) Z. x  f0 |( q) l5 u" i
让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
7 [  J3 j1 h6 t3 l$ C. S
! [  v% O$ s0 U/ b2 o6 `另 n + 1 = k - n k = 2n + 1
/ G% ~8 o. `/ @; e/ E# \$ l那么x + 1可以控制的最范围就是[1, 3n + 1]
/ ~2 C. O/ x+ t- R

. ?4 f( d( f; G. Z  ~5 u0 P