最少砝码 Java解决

2744557306

问题描述】
5 g( @6 U3 x8 _* N# m/ n" X你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
& J& n, X% }2 Z# t" O那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。

( @# M# I) E& i! I3 q【输入格式】
输入包含一个正整数 N。

【输出格式】
% [& x9 D3 ]' t输出一个整数代表答案。
  R- O! u1 @  m9 O6 s" Z- h
; T: Q* \' o6 \. T) i5 ?0 p【样例输入】
7
! L% D- ?3 h/ s8 ~& n/ E" J6 f4 b
【样例输出】
! h: j) [) D; S5 I3

3 }) y; F% z; H$ C7 ~【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
  ^4 f. p6 d5 t7 ]* v4 g1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
5 = 6 − 1；
; y4 I+ T1 j( R7 p- j. Q4 g6 = 6；
7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   4 w6 k& h9 k: t, c' d
2. public class Main {  
   ) E$ o) A# [/ ^) {$ M& Y
3.     public static void main(String[] args) {  7 V( h8 Z7 w! ?
   
4.         int n = new Scanner(System.in).nextInt();    , f( L  p8 x\" U/ [: Y8 V  \$ M
   
5.         int maxWeight = 1, minCnt = 1;  - S8 u! t. N\" R7 m0 \
   
6.         while (maxWeight < n) {    x* Y3 v% l  A+ y3 P( @8 \
   
7.             maxWeight = maxWeight * 3 + 1;  # B- g+ J+ L+ _7 U+ U- p1 P6 C
   
8.             minCnt++;  ; f& N) N3 Y# ]' ?2 `
   
9.         }  
   # E' O9 G! T. F- ^) A
10.         System.out.println(minCnt);  
    5 @; p6 n2 L) L0 j* j# x\" q
11.     }  
    3 h+ r7 X% v* `/ G, r+ v( |& x
12. }
    # _3 a, Z' R) u\" X

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
+ X6 ~3 a% Q; t0 t% j) L7 r9 x此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

- O/ X/ {* y) J( `- V2 I  z+ A让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

# v2 W8 N) W' C/ d9 m: i另 n + 1 = k - n k = 2n + 1
3 c& d, I! U% J) i& ~  l) L( l那么x + 1可以控制的最范围就是[1, 3n + 1]
$ _1 B5 C& _5 B' F; U


9 ^, e0 q. k6 f0 ?  ?  [