最少砝码 Java解决

2744557306

问题描述】
) p: n# B, G! V$ @: ~- {& V' e你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
$ r' v2 h( E1 n那么这套砝码最少需要包含多少个砝码？
+ _- ?6 J, `# X* K注意砝码可以放在天平两边。

【输入格式】
输入包含一个正整数 N。
/ i7 e7 u! {( e& J1 h! z$ [& w
7 i) B3 y! s3 a【输出格式】
输出一个整数代表答案。

% z" x8 Q' l/ g: y2 Q& B【样例输入】
2 y3 j+ v3 k% f/ f7
+ P  R0 F* e* J/ I
【样例输出】
" d2 R2 L6 O$ Z1 S6 {( d$ a& {2 i3

) O9 u. e; z# l【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
- @6 t* R- M6 d: J, ?# Q4 b! N0 F1 = 1；
5 r2 [6 U1 z2 C4 d2 = 6 − 4 (天平一边放 6，另一边放 4)；
. ]8 o+ p% Z  L1 Z3 = 4 − 1；
$ b' l. o2 f9 U5 e) e6 H* i( W  `4 = 4；
5 = 6 − 1；
/ g9 @( r9 |' T; l' x6 = 6；
7 = 1 + 6；
; i  B0 @8 V: }/ ~' ~1 w少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  4 g  O4 X\" F4 J# d0 K2 e& D0 g
   
2. public class Main {  
   0 z1 S4 F% c7 W4 F
3.     public static void main(String[] args) {  
   3 `- [. h$ W& R7 L\" y' _. h
4.         int n = new Scanner(System.in).nextInt();   
   * P. M2 E; `. v8 J
5.         int maxWeight = 1, minCnt = 1;  
   . X: h! }% }+ H* w& z
6.         while (maxWeight < n) {  
   * e4 N) U- u  u, N
7.             maxWeight = maxWeight * 3 + 1;  
   1 e7 ~- X9 l5 ^8 t7 g# X
8.             minCnt++;  * f- L7 z, ^0 y/ D0 |2 M( [7 k
   
9.         }  7 u, u  }& o7 P- U8 M
   
10.         System.out.println(minCnt);  - Q& ~+ w8 u# h6 P6 S% J2 `  x
    
11.     }  ) J+ B+ C; \4 C3 y
    
12. }
    / c  s! G( C& ^( r

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
$ D6 ]! _: o8 S/ i+ ~& {此时我们想扩大区间范围就只可以增加砝码
$ }/ b4 o0 K5 Z  h2 x假设增加的砝码重量为 k
0 X% K# E+ e1 |+ M1 R因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
: e" v' r; f! e' {, Q% d! B4 A所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
4 d( k+ D0 S+ R5 X" V& e
. J) m! C4 m7 _8 _让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

另 n + 1 = k - n k = 2n + 1
3 N2 u1 t9 e7 @5 [那么x + 1可以控制的最范围就是[1, 3n + 1]



8 ]( f! M$ ?, U8 K7 e9 ?: y1 ]( ~) h