最少砝码 Java解决

2744557306

问题描述】
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
! K3 Y) \4 G6 A+ o+ \$ s那么这套砝码最少需要包含多少个砝码？
; E: ?+ ~& y0 {- g" Q注意砝码可以放在天平两边。

! @) S* Y7 E3 a# j. P' a【输入格式】
输入包含一个正整数 N。

) M2 ~5 |* T* @" ~4 M& X  [【输出格式】
输出一个整数代表答案。
1 N- C& j4 i7 G# s8 I. T: E, o9 V! U
6 n6 J+ N' r+ o【样例输入】
7

【样例输出】
3
6 E* U; m& Q* K2 _, g+ \
【样例说明】
1 x- k2 }* E+ k( V3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
) A+ {5 @4 i1 ?0 Y, ~1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
$ B6 `, W, L! l3 = 4 − 1；
4 = 4；
5 = 6 − 1；
6 = 6；
2 u7 i; s! A, N7 = 1 + 6；
3 E# S! r; m- P( Y# G8 \) v少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   9 p; B8 {4 _$ S7 ]+ W0 a
2. public class Main {  ) i( s% g: t# Y0 \9 Q$ R
   
3.     public static void main(String[] args) {  ( U9 R2 C( W/ A; \, a
   
4.         int n = new Scanner(System.in).nextInt();   
   * X- Y/ F/ x# n. Q6 e+ A5 \7 m3 v) K
5.         int maxWeight = 1, minCnt = 1;  & K: ^# B  I\" S# P$ r  {4 v5 T& W
   
6.         while (maxWeight < n) {  
   5 q\" V0 S0 X, v( z3 f8 K) \) g
7.             maxWeight = maxWeight * 3 + 1;  # i% m* L! q7 d4 ~% @% m' I
   
8.             minCnt++;  , F  m7 {6 V& l& R# r' _8 q
   
9.         }    A! f\" y5 x$ C
   
10.         System.out.println(minCnt);  
    % {# o' K( {/ p% z( x8 P5 s; M* ^
11.     }    }! c% F+ R: _9 a  }5 ^3 H\" h
    
12. }
    / h% f/ p5 N% M& e1 e& S4 A) A# l

复制代码

题解
% k8 E) \+ [! j6 f如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
此时我们想扩大区间范围就只可以增加砝码
6 {- x2 J7 D* T$ H9 d假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
& M# P* K5 o% r" P9 K所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
& f3 ^3 \% g$ f* s! o! T
让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

- x( V* J+ R/ n2 i4 g/ d另 n + 1 = k - n k = 2n + 1
那么x + 1可以控制的最范围就是[1, 3n + 1]

: g, U9 E  b$ Z! P