最少砝码 Java解决

2744557306

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

【输入格式】
' m8 w+ r% F4 D: n输入包含一个正整数 N。
$ ]0 l& X0 e8 K3 V6 D
( g- p1 W' H# E: B7 }【输出格式】
输出一个整数代表答案。

4 n) V5 t$ \: ]' Y# t【样例输入】
0 @* Y& A+ M. L2 u, z7

! D, g' x! V7 j+ F% Z# @) F【样例输出】
% H& e3 M5 l6 y4 r0 \' U- b& l3

【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
  v$ `% a& ~0 \- Y9 g1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
2 G$ i3 y' b: s% E. U3 K4 F3 = 4 − 1；
# u  I* q; {3 e6 ]4 = 4；
9 o0 S9 a( }9 Z5 = 6 − 1；
6 = 6；
* y( U1 ?$ i- h7 = 1 + 6；
& m( a2 N; `# M! t- I! P4 \0 Z1 ]少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  3 y8 M/ \! f; T$ G
   
2. public class Main {  5 Y/ j\" w+ S, s8 N6 l
   
3.     public static void main(String[] args) {  
   & J9 o. c8 g/ K/ r7 q4 I
4.         int n = new Scanner(System.in).nextInt();   
   2 F\" C; M2 W  b
5.         int maxWeight = 1, minCnt = 1;  
   9 q& I! a$ V' C' k; v
6.         while (maxWeight < n) {  
   * G! r& T: T: B; i$ s) y. E
7.             maxWeight = maxWeight * 3 + 1;  / J5 l: i2 j$ K& B
   
8.             minCnt++;  
   9 F  y# |& h, |) W  v8 l% u! v) C- R
9.         }  
   \" B) Y9 j7 _2 q6 i2 I1 p
10.         System.out.println(minCnt);  ' }& D$ a0 b/ g) b$ ?; ]
    
11.     }  - X1 k9 S9 ]5 O, T
    
12. }
    # Q2 Q6 L' k: h2 M/ ]% U1 H

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
$ ~) {2 Y6 G; R( L# p此时我们想扩大区间范围就只可以增加砝码
3 f; G$ g$ P4 Y* [假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
0 J6 b& w  j+ G+ r5 g
" s0 X( Y; K2 R- s! k另 n + 1 = k - n k = 2n + 1
那么x + 1可以控制的最范围就是[1, 3n + 1]
$ [3 D2 p( i2 U9 }3 Z; H
* O/ K' b8 Y3 r

/ m( g6 q7 J8 c2 F1 s# _