最少砝码 Java解决

2744557306

问题描述】
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
  P" l; E: _; J) ]那么这套砝码最少需要包含多少个砝码？
  A# h/ X, i2 r3 C注意砝码可以放在天平两边。

【输入格式】
输入包含一个正整数 N。

【输出格式】
输出一个整数代表答案。
. w- R2 R3 ]9 s6 k- G8 D+ Y1 X
4 e7 ]' Y' H$ S  _) h. ~【样例输入】
7

/ @9 S2 i  H5 C【样例输出】
+ `! X( u) _9 A8 V5 O3
* {. ?8 P" T1 i/ `0 |9 t
. w5 @/ S  ^+ p$ r3 m- i" K【样例说明】
% I. V7 v0 M' F+ U7 o* Y3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
5 ^+ H- r7 I) T# V: Y( L! j' H# F4 = 4；
% |( G# t# h1 C& K/ n2 s: K5 = 6 − 1；
6 = 6；
' T+ h0 a2 y3 w8 s3 m7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  9 M+ T3 \- ~% v& W! |, L8 x& I
   
2. public class Main {  
   $ r) p8 L4 J! [$ N4 Z( O9 s
3.     public static void main(String[] args) {  
   6 o! ]3 q; z1 F9 d- z8 R
4.         int n = new Scanner(System.in).nextInt();   
   3 f& u' o- q, O9 E% ^) ~
5.         int maxWeight = 1, minCnt = 1;  
   ' h6 W\" G; M$ J! ^
6.         while (maxWeight < n) {  , s$ }+ S, X9 l2 r2 w( x* k
   
7.             maxWeight = maxWeight * 3 + 1;  * _6 _+ `- P/ |5 a6 T8 z- ]& |
   
8.             minCnt++;  
   - K5 T1 Z+ w. P9 O; k; T( m
9.         }  
   # _, o/ ]5 u# Y, X
10.         System.out.println(minCnt);  
    . t% x/ V. I+ w& m
11.     }  
    , w% `8 N' j3 h; s: j
12. }) Z# O* c5 o$ v0 i
    

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
- G1 O3 u- e+ a0 h: H此时我们想扩大区间范围就只可以增加砝码
- d0 C, v$ \: Z2 o' W# Y假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
- H% E$ e  ~, Q% ?所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
1 |8 F$ r0 H" K/ j
另 n + 1 = k - n k = 2n + 1
* @& d: ~2 I5 T那么x + 1可以控制的最范围就是[1, 3n + 1]

/ S6 P5 k! e0 _