最少砝码 Java解决

2744557306

问题描述】
* C$ n; n! T# M你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
4 I  [$ V: Q& U: @那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。

2 z6 |' [  P) J  K* J, n【输入格式】
输入包含一个正整数 N。

【输出格式】
输出一个整数代表答案。
' }! X. n; A, h7 ?
4 N, i: Z# i; H) f3 @7 ~3 v【样例输入】
& t1 G& D" y* D7 u# X8 S7

# P$ g) Y8 \7 X: d% ^1 ~【样例输出】
- i6 r# O5 N/ Q+ t9 V4 ^* g3

; Z; D- }; k6 Y/ R- l【样例说明】
; k9 F/ U1 W& M( m" D) m3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
5 = 6 − 1；
6 = 6；
7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  ' ~! q* q7 K6 M7 `! f& `8 W6 R
   
2. public class Main {  
   1 z) ?( G1 W* J7 O& k/ o& _
3.     public static void main(String[] args) {    P2 |; k# E; ], {
   
4.         int n = new Scanner(System.in).nextInt();   
   5 H: {  k& \/ Z. O
5.         int maxWeight = 1, minCnt = 1;  0 v  I# t# z8 b2 M! f
   
6.         while (maxWeight < n) {  2 P: J3 Q! G2 [1 T\" v
   
7.             maxWeight = maxWeight * 3 + 1;  
   7 g8 O1 _3 P* i. p( `. O
8.             minCnt++;  
   7 [, w: r0 n# u3 V( k1 s+ W
9.         }  
   / ^5 y8 m7 W( y0 l) c# j
10.         System.out.println(minCnt);  2 S  t' r1 Z\" |8 n0 w
    
11.     }  
    9 d% J  X8 ^, g# Y5 w
12. }
    8 }9 l* Z; k7 Q, C

复制代码

题解
" i6 S. Y% B+ I" r# e如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
& P- d; s, a" M& q! L+ W4 `2 B- V此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
6 \  g0 u8 n( \% u" O5 R3 [因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
! o7 G/ \1 p" C" v所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

0 U! `. V5 i7 ^: @# x让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
8 ~) x, d: C, a
另 n + 1 = k - n k = 2n + 1
0 ^8 C: k9 @! I那么x + 1可以控制的最范围就是[1, 3n + 1]
1 C* ?" E7 [/ w7 f8 _8 ^  z
. v$ u2 Z  E. M9 Z& g8 p