最少砝码 Java解决

2744557306

问题描述】
% M! u- k' f0 j$ R) c你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
. o* J& E" w' j& k$ Y% ]% ^1 O& i那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。

) o' ^* B$ n  V/ j/ F( u4 d: g【输入格式】
3 ^! y7 i) u. U. E. g输入包含一个正整数 N。

【输出格式】
输出一个整数代表答案。

【样例输入】
( }& ?. c) x0 h5 X7 j! N  O8 `7
( E3 ^- w, ~  }3 A6 b7 }$ l
! T0 q7 J  z$ ~# l, u【样例输出】
3

【样例说明】
- v3 @$ d9 u1 |1 h, K% Y( M3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
  P. I$ Z7 f' E  ~. v/ p5 |4 _- T/ ]1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
( F6 t$ U) P4 V& E' X3 = 4 − 1；
+ X  y. o. I4 r3 e& X' n4 = 4；
# M, b' G* H0 V/ k! e2 V" T4 c5 = 6 − 1；
0 j$ l+ Z' w( T4 T5 D: M' v2 g6 = 6；
7 = 1 + 6；
! h: t8 m7 A7 s' [少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  ; w! Z: Z2 t- u! s
   
2. public class Main {  
   + R1 |: H8 j- @$ ~
3.     public static void main(String[] args) {  
   , N: C6 K. Z6 r
4.         int n = new Scanner(System.in).nextInt();    0 N$ o4 f  [) r% }
   
5.         int maxWeight = 1, minCnt = 1;  
   ( W+ x1 Q1 i; R8 _! s$ r& H- x
6.         while (maxWeight < n) {  
     j; F$ g\" D! z! E; e# B\" U0 L
7.             maxWeight = maxWeight * 3 + 1;  3 k7 q* J7 t4 l( R2 K8 J' Y
   
8.             minCnt++;  % Z( m' d: `. S* r
   
9.         }    `' S2 R# W* Q1 J& f! z# T3 p
   
10.         System.out.println(minCnt);  - ~6 S\" W+ w, Y+ X0 T; A4 f
    
11.     }  ) r0 s6 ~/ x. Y6 {! T) i
    
12. }9 I% N0 X/ o: e* k' |1 M
    

复制代码

题解
5 }: U8 j5 a& ^0 G如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
此时我们想扩大区间范围就只可以增加砝码
3 W% O. J/ H9 s" @( R  W; T4 j% l0 a1 w假设增加的砝码重量为 k
% a6 F4 @" e% d  z/ z) Y5 E: e因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
5 F4 d4 w8 j) p# Q/ A2 |所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
2 D' Y; w5 R/ A9 `6 S2 U# s5 a
让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

另 n + 1 = k - n k = 2n + 1
7 ^9 D& [0 u: p' i# |那么x + 1可以控制的最范围就是[1, 3n + 1]
6 i* F0 {, x. w3 A
1 }0 s6 [6 p7 f5 e" S

1 Q, B& \* L* Z( R9 F