最少砝码 Java解决

2744557306

问题描述】
' g. E* b7 k8 e9 O! [' G" _( \& m! `你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
+ t& c% e3 ^" Z4 L. v5 U$ H那么这套砝码最少需要包含多少个砝码？
. I* `8 Q) t' L- C注意砝码可以放在天平两边。
/ b% G1 m- Z4 r
【输入格式】
输入包含一个正整数 N。
/ E4 C- _' g; ?0 c$ ?$ i# M
8 B1 Q5 {1 L! V/ r" K【输出格式】
输出一个整数代表答案。
" j3 S" s$ A2 w( M2 f; ^( w
/ ^+ E$ o1 f+ W: ]/ e# V【样例输入】
4 e& [5 }$ M* e- }& a% C7

+ p. L6 }5 z. h7 P9 N; }- n【样例输出】
) d: {% [9 q# l* D! ]' E* g3

3 j$ C. V. w3 J. s【样例说明】
/ ]9 N$ L$ A1 T3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
4 R3 a8 `$ D4 a+ W; g7 d1 A! b1 = 1；
+ V; }8 ^4 v. k2 = 6 − 4 (天平一边放 6，另一边放 4)；
/ a+ t' k6 m  m# k" |3 = 4 − 1；
4 = 4；
5 = 6 − 1；
/ G5 g" ~$ K  Z+ y$ ?6 = 6；
  s0 q; x8 I0 }* H/ a7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  , c4 E7 r/ r' e, @  F- T+ Q/ o* I
   
2. public class Main {  
   # M7 R1 r- c; Q  J' C$ x  J9 W: [
3.     public static void main(String[] args) {  
   ; g9 S; n4 _7 {0 S9 D
4.         int n = new Scanner(System.in).nextInt();   
   2 e0 S4 b3 C$ ^) C
5.         int maxWeight = 1, minCnt = 1;  9 r& E6 K( g- Y' G: a- v$ A+ m
   
6.         while (maxWeight < n) {  
   8 h2 {\" i. f$ a( S. e, `\" r; A
7.             maxWeight = maxWeight * 3 + 1;  
   : P' Z* u# o9 k
8.             minCnt++;  9 j\" v. y& m( u4 \\" R% z* C5 B
   
9.         }  6 I+ T6 }, w! N, V! e4 \  n
   
10.         System.out.println(minCnt);  
      u/ v+ O* U! P! C, c5 p\" x) p) z
11.     }  
    4 b* G3 ]  Z' D' m2 X3 B+ G
12. }
    6 d3 G) D+ N% K

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
2 X9 ~* p0 _% a) Y' h! C% |此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

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

另 n + 1 = k - n k = 2n + 1
0 }% D3 _) T7 F9 K5 {那么x + 1可以控制的最范围就是[1, 3n + 1]



0 m: d: Z- S: r* B6 [9 y' `