最少砝码 Java解决

2744557306

问题描述】
0 }: J" V* b* S' }* V+ A! v你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
3 x7 @) t7 \) W) ^5 }那么这套砝码最少需要包含多少个砝码？
' G  v8 _% B" a# {$ M' k注意砝码可以放在天平两边。
/ o! [- e+ f5 G& p9 e1 w$ N, x$ ^
# E) H+ N& _$ _8 r& J# Y【输入格式】
输入包含一个正整数 N。

  d5 @& a! p7 q) R! B/ q【输出格式】
输出一个整数代表答案。

' o, K, H& P: H6 X7 B【样例输入】
7

% a- ]# Q" B7 D0 f. {" x0 T" v* S【样例输出】
3

【样例说明】
" w; i, ]# B5 X! q/ {1 G) v3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
% ~: l, o- D4 |. a1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
+ c7 b) U- b, y* e3 = 4 − 1；
! e7 W) f* I9 z: w/ n4 = 4；
9 R* }8 y8 X0 c( ^5 = 6 − 1；
4 t7 F# W! ^% u# R  e8 R3 E2 u" c1 k- }6 = 6；
7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  - y( L) [: L. V5 j. q
   
2. public class Main {  ( \$ w8 k7 K# ?
   
3.     public static void main(String[] args) {  ; g% J8 ~+ v\" Q  S
   
4.         int n = new Scanner(System.in).nextInt();    $ z& N+ G! F. L; q$ O6 @
   
5.         int maxWeight = 1, minCnt = 1;  
   3 o6 Z% t: N0 {2 `3 S, S2 |% [0 Y
6.         while (maxWeight < n) {  + P5 r. `+ X! o( \9 }# ^
   
7.             maxWeight = maxWeight * 3 + 1;  7 U- u8 a& ]( Z6 G* \
   
8.             minCnt++;  
   2 |( c, `\" F1 r
9.         }  
   ; K  F% a' k& i. O\" w- o7 d: T
10.         System.out.println(minCnt);  
    : h; Y0 U8 z0 `- m2 f
11.     }  ; O2 l4 _! {\" O7 H* m
    
12. }
    $ P- ~( l/ a  \/ q( Z; s' g

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
: Q6 P. t9 _5 x9 _: I- b此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
9 h9 c& x. w& E* }6 B) P+ ~所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
) j* B( m- D+ n4 [3 R
+ S: \7 R6 ^4 W让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

6 q1 G) Z5 k$ ]) m) C9 v5 n8 ^另 n + 1 = k - n k = 2n + 1
5 M+ c: g- z: G! a- C4 i那么x + 1可以控制的最范围就是[1, 3n + 1]

- K; ~; A  w& s# r0 o
( |  F- Q1 q! l