最少砝码 Java解决

2744557306

问题描述】
- g6 {: n. \: Q! U3 a& d你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
* G: I6 Y; l% P- y那么这套砝码最少需要包含多少个砝码？
3 P% E3 f" b6 Q" Z$ E5 @4 O! I注意砝码可以放在天平两边。
" I0 }  C4 _# Z$ t4 k" c
0 F: n$ K6 i+ k" E! \2 |/ p4 |; g【输入格式】
输入包含一个正整数 N。

【输出格式】
输出一个整数代表答案。
! e4 `( c. {' N3 L! ~$ ]! ^, g) e& I
【样例输入】
7

【样例输出】
$ p& l5 m2 _7 G- N. g, A3

3 l. m. p7 d" b( E【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
9 \6 F. X" e7 l( K5 V1 = 1；
" ^0 V' [2 u. \  [" v/ [( ?5 l2 = 6 − 4 (天平一边放 6，另一边放 4)；
& ^6 \4 k% N- l! p6 Y2 {3 = 4 − 1；
# A6 u% c5 e: @4 s4 = 4；
5 = 6 − 1；
+ i3 g( Z/ c* h" w6 = 6；
* Q, ?! J! ^0 ~7 x# y8 Q; h7 = 1 + 6；
8 \3 s& ?$ m5 n0 F$ Z少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  * f6 a- T\" L: T' X& Y6 b
   
2. public class Main {  
     P, M3 j/ c- M- m
3.     public static void main(String[] args) {  
   5 D  x/ t( w% c3 C, @+ U( I  L
4.         int n = new Scanner(System.in).nextInt();    / j9 B( L5 M' C  T; T2 L5 H2 u
   
5.         int maxWeight = 1, minCnt = 1;  * A3 r; t! W% ?% p1 n8 c
   
6.         while (maxWeight < n) {  & f5 P2 q7 u* ?7 n. H
   
7.             maxWeight = maxWeight * 3 + 1;  4 W4 l' G. ^0 ]\" [9 q
   
8.             minCnt++;  / H* T3 A  G, W9 O0 e/ E
   
9.         }  , z! c/ u7 {/ {4 O2 }
   
10.         System.out.println(minCnt);  
    $ Q1 o7 v6 d% K/ [) g
11.     }  
    ! i# ^. `6 y1 O2 B6 b
12. }
      x4 |. T  R' m9 q9 Y& E4 z

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
$ {' K# Y, J7 N) |0 U4 E, \- y; y% H因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
9 X8 p- j# A" p# @& s' S" Q所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
  q+ y( E& j& C% t+ y5 K, d% y' ]" O- C
# h0 F& ?, u; `! U. z让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
- `- a! d7 X: m3 _# B3 Q
) E% t( e; D1 {另 n + 1 = k - n k = 2n + 1
那么x + 1可以控制的最范围就是[1, 3n + 1]
. g1 |+ `4 n# {
) N' e$ }5 p6 Z3 a( a# _

; @5 D$ e1 I' ~: c6 r