最少砝码 Java解决

2744557306

问题描述】
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。
9 n& h  O0 K/ f( C- r
【输入格式】
( g7 h8 u( C' [1 |输入包含一个正整数 N。

【输出格式】
) A" y" T% h) G% m输出一个整数代表答案。
' c5 a/ ]" `6 G1 c
  _8 V$ M0 l/ U) U7 n$ ~. q【样例输入】
9 |. y/ \+ X& |7
, k! |3 Q: r* x+ B; i; t
6 I  w, A/ k) m+ A【样例输出】
3

# t$ Q! J$ n9 j* m【样例说明】
0 P6 h& s5 P* k3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
, o+ d/ f- n% K: T  S6 B1 = 1；
1 a4 R' K( W) U/ R2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
$ x! v1 v* O- U) |3 l4 = 4；
3 z" l  B  |$ }5 = 6 − 1；
6 = 6；
9 q7 N' e  l& t+ D$ w. Z8 r7 = 1 + 6；
0 q0 @1 H* a! l, X% S6 T$ M少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;    M/ j2 j2 }  U. v1 @, t. F5 e* L
   
2. public class Main {  7 _' T& i$ w% N- N' j! s
   
3.     public static void main(String[] args) {  
   : G! f2 G0 I! n1 `/ R- x
4.         int n = new Scanner(System.in).nextInt();   
   ( @; U3 T  p) g7 s* r
5.         int maxWeight = 1, minCnt = 1;  
   6 d! R6 r6 C$ ?7 K8 x7 r
6.         while (maxWeight < n) {  
   4 j8 d; O8 H* v* R
7.             maxWeight = maxWeight * 3 + 1;  % }% r+ B, Q1 T  J% |/ I  E1 R
   
8.             minCnt++;  . V% r! }% c7 S# H8 E. O
   
9.         }  
   - Z* s' @% @4 X6 m\" g* N4 s
10.         System.out.println(minCnt);  0 S3 p' F5 j7 d9 f% U
    
11.     }  : A, t7 ]1 ~$ R8 a1 e& R
    
12. }! u: g: R. N9 l# ?9 Y( ?
    

复制代码

题解
$ `5 b- m  f% C) {, t# y* P如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
: {  g6 }6 o9 p6 t/ S( G; p$ o4 h; c, w此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
+ h1 h0 f+ [0 t因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
: Z, b- _- z# {
% s" Y" m/ f: Z$ f  k( N- |4 m让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

8 r# J; h) f! {* Q2 }1 z8 i另 n + 1 = k - n k = 2n + 1
那么x + 1可以控制的最范围就是[1, 3n + 1]