最少砝码 Java解决

2744557306

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

4 f* m7 E- s% c0 \【输入格式】
输入包含一个正整数 N。

  [0 }" j; m; N8 ^【输出格式】
  ?+ S( G. M* J# y  N! X输出一个整数代表答案。

! w+ m& K8 {) `7 r% u【样例输入】
+ A( V6 j" g. S" t; L7
5 K- d, S3 K% x' l' H; N
- _7 }* \' h3 n2 e6 [% N  x【样例输出】
3
* u/ @9 w2 L9 N' K; ?
( u/ b) c+ o3 C7 d+ t+ b  B【样例说明】
3 I1 J; w1 x  T/ T' D0 R% u8 ]3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
) U' [3 x9 x* r& y8 t* E1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
% D4 X" _. C0 G4 = 4；
5 = 6 − 1；
* X- }) b- v+ `0 I6 = 6；
6 Z0 c, z1 X" f! [% u1 x2 L7 n7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  9 t$ J0 [' y+ {% X
   
2. public class Main {  
   0 c& R! n6 p. L+ Q7 X3 }1 ]: F\" O
3.     public static void main(String[] args) {  
   \" @2 x3 L+ p) J$ o1 A
4.         int n = new Scanner(System.in).nextInt();   
   + X; j2 i5 c$ _1 T
5.         int maxWeight = 1, minCnt = 1;  , u) c\" e# [4 ^' g% t* b3 `8 F
   
6.         while (maxWeight < n) {  
   + t. f( m9 g6 `7 U+ Y4 G' L
7.             maxWeight = maxWeight * 3 + 1;  , z- {' Q0 v8 V, u
   
8.             minCnt++;  5 {5 Y! i, k\" x! _
   
9.         }  0 E% n: l7 D; V% u
   
10.         System.out.println(minCnt);  3 Y: ^( e8 P\" v& g9 l7 G1 B. [
    
11.     }  2 U! U6 b) B0 f( ]2 h0 x# s\" E, D
    
12. }
      m  A( d) g0 U9 z

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
; }* G1 S. U% l0 Q4 R/ o- m3 P此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
" y7 V7 n: n( J7 ~3 I因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
# ?$ W9 D* [' ?$ M. E3 q# q所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
+ _- I4 B  p( A$ e
* ~4 k: |2 b/ X. ~& j; U让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

2 t2 d. @6 @* `' E; X9 ]+ e( k另 n + 1 = k - n k = 2n + 1
! \% `- z8 m; c, f那么x + 1可以控制的最范围就是[1, 3n + 1]

. p$ O! i, y, z9 Z: K