最少砝码 Java解决

2744557306

问题描述】
- A7 d& x* T1 {你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
" N% |  d, S( N' K/ n1 B注意砝码可以放在天平两边。
. B0 S: Q! M: X3 |* i; e" u
4 K* A+ @2 [  L: G; k1 j【输入格式】
输入包含一个正整数 N。
+ v* }+ ^$ |3 M% V6 }
$ F) F3 K# i) ^【输出格式】
输出一个整数代表答案。

【样例输入】
# l5 }9 B( y5 z3 C$ k" q, K7

【样例输出】
+ |" m0 E1 i- [/ x, t3
" Z7 O) u2 ~  s( Q: q- t4 G
. H: E9 M5 D7 }, b" [【样例说明】
7 _1 Y: V' u, z7 D3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
! t0 u' u. G# J8 T: y1 \5 = 6 − 1；
. Z+ F' @* p6 Z. N7 Y1 f! C/ m6 = 6；
7 = 1 + 6；
% U( W, D1 R2 u少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  0 c9 d( y2 G: ?; v0 K! r; q\" t  B
   
2. public class Main {  7 [2 S$ {' x3 i
   
3.     public static void main(String[] args) {  
   : n8 C' S; t. Z9 ]7 }4 I  o
4.         int n = new Scanner(System.in).nextInt();   
   # [9 R1 O\" G8 T% r) T  b
5.         int maxWeight = 1, minCnt = 1;  + C$ A  u! e0 K* a. `
   
6.         while (maxWeight < n) {  
   9 q( i, ]: R! Y$ _- u% Z
7.             maxWeight = maxWeight * 3 + 1;  / T4 V4 K8 ^4 v! w\" A8 D! Q
   
8.             minCnt++;  1 _$ L& }, h! e8 v) k! B
   
9.         }  
   - s: t4 D& f$ V( W1 K- O& @
10.         System.out.println(minCnt);  
    + v5 o7 n0 _0 m6 R9 f
11.     }  
    * T% g6 L4 u\" T0 [* j8 G7 F, ~1 M
12. }
    2 B* w$ f  d6 E/ p1 W. S: S

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
8 b! m7 V& n  A8 c9 r$ a: ~9 J此时我们想扩大区间范围就只可以增加砝码
( V0 x* [- S7 ?2 i假设增加的砝码重量为 k
" X6 U; C- t: j* E% W4 ~& v5 _" K0 U, M( u因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
% E0 B5 J* l( W9 {: d
0 B; }1 N4 \- N9 `1 D让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
4 q. f1 n" Q$ J# ~+ m; V
另 n + 1 = k - n k = 2n + 1
那么x + 1可以控制的最范围就是[1, 3n + 1]

/ |. _' n4 L1 b( Z
7 x, r7 }. [: Z3 ~4 c* l& i5 K