最少砝码 Java解决

2744557306

问题描述】
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。
1 q5 i( l5 T+ ?4 G, T
) V' T/ {+ y, Q  z9 i' A: b4 Q【输入格式】
9 u# s9 G0 B& ~) g5 a输入包含一个正整数 N。

* `# Y$ g/ `* n2 [- {【输出格式】
  n  O- A: r) \8 d% X% q输出一个整数代表答案。

【样例输入】
! {, P9 y/ Z* a: |: Z8 r( ^7
2 A  f9 ?; F9 |% @
【样例输出】
- p- ~6 z0 s0 B3 S3

+ q  t) h1 Q+ }% p- s/ {【样例说明】
. s2 e& N7 _3 h$ h7 X3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
5 = 6 − 1；
3 W1 f0 k) {% a6 d5 Z/ r6 }! y1 I6 = 6；
+ x2 r$ @2 l4 L' d& O0 ?- B- |7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  8 Q  I7 t/ r, u% m0 f- _5 g
   
2. public class Main {  & O5 q- l- w6 m1 `& K
   
3.     public static void main(String[] args) {  ' n& D+ m6 a( ?* T% p
   
4.         int n = new Scanner(System.in).nextInt();   
   % Q' v! T# D, ~( E1 X* ?* @) Y
5.         int maxWeight = 1, minCnt = 1;  # Y# L+ S; f: q- A& h  c  T\" q6 E% j
   
6.         while (maxWeight < n) {  & x- }: g; V  f9 D- Z3 s
   
7.             maxWeight = maxWeight * 3 + 1;  ; ]5 P; l3 S- a3 ^
   
8.             minCnt++;  
     u. X* X; |9 ^, x! K6 a
9.         }  
   3 A/ [- L2 u# V. t7 e7 W# I
10.         System.out.println(minCnt);  
    , |/ F- j+ M3 v) N1 [. ~
11.     }  # \' @9 R4 Z2 q0 G: i
    
12. }( h1 Z; ~+ i5 v+ m/ z
    

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
此时我们想扩大区间范围就只可以增加砝码
6 p# t' s4 i+ @假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
+ e* `. }9 F$ j5 c7 e0 E, h所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

; N8 K) A. G% v# A5 a- M& {% f! X, E另 n + 1 = k - n k = 2n + 1
' u& p% a" F( r% B; d! E那么x + 1可以控制的最范围就是[1, 3n + 1]

4 y' d2 k) I% o9 g" c: E