最少砝码 Java解决

2744557306

问题描述】
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
5 D+ L/ ^" i/ P% @' K6 z+ w, F! J那么这套砝码最少需要包含多少个砝码？
" P  B9 ?7 L! a4 S) Z- a" @, f' w注意砝码可以放在天平两边。

【输入格式】
  B) B7 t" A2 j( i输入包含一个正整数 N。
% ], B+ }. L( ~. |* b5 V& r- l+ o/ \
【输出格式】
% U  w* l' e7 [, |5 Y# b3 z- l输出一个整数代表答案。
2 i  K4 ]% K# I% S
【样例输入】
7
) _- \& _+ o9 \4 v' C
【样例输出】
; h- O: v3 U; Z; C: M6 t- ~, v& T3
; P! |7 _& \& o) F6 E
# k% @! C$ y0 |4 a$ `( F5 t4 r3 m【样例说明】
- M4 H6 ?, F9 O  O* @: q  C4 Y3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
8 {9 C( t7 `" [0 h1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
6 C, m8 Z! {4 Q" S. j; [9 e/ ^3 v3 = 4 − 1；
' I* ]! ^5 O* P  Z9 ~: r4 = 4；
  g$ e3 P; H0 a, w4 ~. m5 = 6 − 1；
, N) v* Y! ^7 Y/ I2 \8 {& n7 u' }6 = 6；
7 = 1 + 6；
* p* R/ H* r- Q6 P少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   9 i* W8 t- _8 l; [
2. public class Main {  2 N& v5 @1 R' H( H* Y( m0 E
   
3.     public static void main(String[] args) {  
   7 p9 @9 R7 l: `8 Q5 u+ t
4.         int n = new Scanner(System.in).nextInt();   
   8 E( W0 E1 o4 w# ?3 u/ _) F& K
5.         int maxWeight = 1, minCnt = 1;  ; F1 J' X% s7 J  J
   
6.         while (maxWeight < n) {  , l& W) ]2 G' L7 ]( k6 V4 e6 a! k
   
7.             maxWeight = maxWeight * 3 + 1;  
   % _% k' Y  m: z& Z\" z
8.             minCnt++;  6 Q2 a8 Q# M% U3 y  V3 l
   
9.         }  
   ) X& o% z5 G% n% z! C6 O
10.         System.out.println(minCnt);  
    ; z( `9 I; F\" S\" B6 ?
11.     }  
    - h* k1 ^- a3 U4 A. g$ d
12. }+ o: i8 N0 V\" d. B% Y
    

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
& H0 l, @& n1 F/ V6 W9 O所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
5 _4 E/ H' w+ J- c
另 n + 1 = k - n k = 2n + 1
那么x + 1可以控制的最范围就是[1, 3n + 1]


5 Q) p; r: W& w
# a  J( N) C1 n( J$ \