最少砝码 Java解决

2744557306

问题描述】
' r' ^# `' n8 T3 z* Z你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
* @( j8 K' W, N, f9 w3 {1 S注意砝码可以放在天平两边。
" p7 k$ W8 \! q" l
【输入格式】
+ ]4 Q4 T* \$ v输入包含一个正整数 N。

【输出格式】
: Z1 a% E5 {3 D( f& e1 z输出一个整数代表答案。

2 _9 Z9 ^( M( A【样例输入】
' L6 [" p! `3 ?2 g7 Q& D  E, j7
  ^; J' `: w2 C$ I7 l: \5 X. e
【样例输出】
* s+ M2 g# l8 ~9 {: D# q; d3

【样例说明】
3 A( w  J. f+ ~" R- ?/ o2 e3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
; }5 B8 {$ c* G6 ?& ?: @1 ?1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
; a+ P/ b! [! f8 D: A5 g! z+ i3 = 4 − 1；
4 = 4；
+ h# C2 i0 z' D+ g5 = 6 − 1；
6 = 6；
7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  & y6 c* {, y2 m1 j7 N  p
   
2. public class Main {  * z$ `' ~* Y; A, d) R
   
3.     public static void main(String[] args) {  
   / Y9 [* s  z3 B8 w! O
4.         int n = new Scanner(System.in).nextInt();   
   \" ]% o) K: g3 C/ }& j
5.         int maxWeight = 1, minCnt = 1;  ' S' G8 @) k7 W
   
6.         while (maxWeight < n) {  2 G- Z% F  C4 {
   
7.             maxWeight = maxWeight * 3 + 1;  
   , K+ F) r1 U! X2 d' U1 x
8.             minCnt++;  
   - n8 V$ z% p- z  S
9.         }  * W) D' K( B\" ~5 S
   
10.         System.out.println(minCnt);  * l+ r2 r; Q1 A% {, D- x
    
11.     }  , C: h5 ~& V3 \; r4 S! d
    
12. }4 A3 o* i# G! a# m* c# B
    

复制代码

题解
3 l$ z8 L5 i* r. k' I如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
* S5 E( `: v) d9 s& |& P此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
# s$ W  T% b8 w; C6 [: ^+ U因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
- C! ]) u1 g; @0 Y6 A6 K所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
9 r, L- |5 ^* S
4 Y4 \: f2 N0 L3 n3 S' N& q让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
3 Y" ^4 ^6 V# ?7 [7 U: Y3 J1 ?
5 m6 Y- ^( a3 N: i7 x, J# m# Z另 n + 1 = k - n k = 2n + 1
& S# p7 W( I$ `, q' Y; {那么x + 1可以控制的最范围就是[1, 3n + 1]
, E# I0 A, a4 U5 G5 E" o/ `

5 x! x& {. e) w/ _* f. B% A8 i