最少砝码 Java解决

2744557306

问题描述】
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。

【输入格式】
! z/ w$ ~# N+ {$ x- V输入包含一个正整数 N。
- B0 }2 U$ |% V1 Z
【输出格式】
5 e! T! C! ]' E6 I9 O4 l" f输出一个整数代表答案。
' b4 m4 u: j! Q* o4 N$ b
【样例输入】
- h) l' z; k! u, @7
  Y( L7 c8 t* M$ w$ {# M- s
【样例输出】
3

5 @% J4 T! M. d( g$ r5 E【样例说明】
4 l* C4 G5 l1 j1 W3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
- \7 u+ e; S/ r2 A6 r' j3 = 4 − 1；
4 = 4；
! O. f4 T3 U; Y) C/ A; H  }. G5 = 6 − 1；
0 g2 ]/ i5 Q5 t4 U6 = 6；
: |0 b2 d8 i: l& f( R7 = 1 + 6；
$ j' ?3 n- c6 f* }$ y. a/ K少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   $ ?\" c2 l! e' K\" m3 r
2. public class Main {  
   ( m& g- d$ w# N  m- |! ]3 S
3.     public static void main(String[] args) {  
   , v! ?- I  o( H1 Z. A% v( G9 Z. O
4.         int n = new Scanner(System.in).nextInt();    5 q/ i  n/ }2 \$ L2 u  F3 j
   
5.         int maxWeight = 1, minCnt = 1;  
   5 @! P\" p4 h4 ~/ H) M$ w
6.         while (maxWeight < n) {  
   3 B6 v7 A3 M  C' b
7.             maxWeight = maxWeight * 3 + 1;  
   , J! f$ V2 V6 @6 j, M$ b
8.             minCnt++;  
   & Z' C( x6 N$ Q9 Y' O- N. X( C
9.         }  
   5 C/ B5 n4 d4 ~) O\" D
10.         System.out.println(minCnt);  # [; Y! D1 {5 Q5 R4 `- h
    
11.     }  
    8 r2 j4 d1 K6 n/ ~% K: c- B
12. }, g+ U: @+ q3 {5 j
    

复制代码

题解
. H. {) F& ^# N* R0 F; F$ y6 F如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
: \8 [6 s- @: [此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
  d) @3 F: r: d- @0 ^* U因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

* e5 X2 M% W  ?" G# Q% |另 n + 1 = k - n k = 2n + 1
' o+ |- L3 j0 ~, b那么x + 1可以控制的最范围就是[1, 3n + 1]

. x% K8 p5 l6 G- y

4 v" H! z# L& k: \5 z