最少砝码 Java解决

2744557306

问题描述】
! v+ Y2 a) L4 t: q你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
- Z2 t- a9 L+ O1 q6 S- Q2 r那么这套砝码最少需要包含多少个砝码？
0 R) f1 ]9 Y4 F. }+ D3 X注意砝码可以放在天平两边。
- l3 G) D% S9 o/ L0 \9 J4 s) O
【输入格式】
2 A1 `6 _: j# m7 P输入包含一个正整数 N。

9 V  w8 S: e# b9 [/ k$ T; a【输出格式】
+ |  Z, i2 I( c2 p$ k. U, v输出一个整数代表答案。
$ E4 S, a; W+ K) n/ ?
8 z! A6 l( u" e  z* P【样例输入】
, d* f6 x9 N% r6 z" j7 B+ q, b7

2 F- E" k% M- f" Z3 z" B【样例输出】
. |3 V: V+ ~6 B1 K% S, O/ h5 u$ S& S! C3

【样例说明】
4 x& w9 z4 N, U0 g7 k# ?) c. Y% s3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
+ d. s/ r; y4 {' K6 p( R* a0 q7 j3 = 4 − 1；
8 ?: b, G6 M3 e- S% {4 = 4；
5 = 6 − 1；
6 = 6；
2 L, b( P5 g: p6 d4 ?9 r2 G1 h7 = 1 + 6；
4 k6 y8 f3 D# j3 B" ~' T) k少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  ' h+ `( R) _# G/ R1 Q
   
2. public class Main {  
   3 f' d, l3 \- X4 k
3.     public static void main(String[] args) {  3 e' u) ^- O( R
   
4.         int n = new Scanner(System.in).nextInt();   
   4 y! ]0 N/ q! c6 ?* G' F  r
5.         int maxWeight = 1, minCnt = 1;  ' ^, L0 K8 [! K0 E2 h
   
6.         while (maxWeight < n) {  3 G: k& w3 s- [  R( `
   
7.             maxWeight = maxWeight * 3 + 1;  
   7 w' V5 B( ?1 t* g& y8 p
8.             minCnt++;  
   5 z/ ?5 H  T5 e8 e% R: h8 B
9.         }  ( F7 T- J1 V$ R& S' }8 V9 J
   
10.         System.out.println(minCnt);  
    7 K5 D- @  P) r6 m! b
11.     }  % v4 ?5 y1 T7 E/ t' @0 @
    
12. }
    * Y0 w  f2 f0 L: B4 U, P\" i

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
* A, f1 l* h! ^- b2 T* O) O8 s7 A: ?因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
7 L  N' V2 I* _& T: A, N, g6 z/ @
1 A8 p& V& q2 \! b: X) d% Y% G, P. c让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
; Z8 v5 K. G$ p5 d2 ?. G0 b
另 n + 1 = k - n k = 2n + 1
; h' k. D( `$ ^: \0 \. N; z那么x + 1可以控制的最范围就是[1, 3n + 1]


/ R! g9 X& J, T; h, b; Z