最少砝码 Java解决

2744557306

问题描述】
+ g5 v6 h  Y- l- p. p# }你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
6 L% K0 I' v3 B那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。
4 Z+ {2 ^& x, l' g* ~; B0 c2 M
【输入格式】
; }$ h1 R# i; O5 [& |, Y  M输入包含一个正整数 N。
, h' h5 B' [& h4 b: B% P9 Q8 b
4 @* |4 Q- Y* u9 v( c【输出格式】
/ u4 B+ O9 [/ L) \' I9 e输出一个整数代表答案。

) E# z% e/ B: P4 X/ f; f' a【样例输入】
7
: L8 {: ~" T% L2 y: R
, R6 C$ Q5 G. I" f5 U【样例输出】
6 Y& k0 q/ _" F$ `3
8 ^! m4 ^4 f6 e& r: U# M
【样例说明】
3 u' i# A. A. v/ C! v3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
! R/ {6 D. X3 I+ t4 f: f2 = 6 − 4 (天平一边放 6，另一边放 4)；
8 T' V' F' G- V( a1 r3 = 4 − 1；
4 = 4；
5 = 6 − 1；
6 = 6；
7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   / @- k. r4 Q% H) K7 h
2. public class Main {  
   0 V' o/ s$ G3 q% U4 F8 o0 u
3.     public static void main(String[] args) {  4 @$ q9 U6 S4 X. M+ A& M' X  Z
   
4.         int n = new Scanner(System.in).nextInt();    3 t6 V7 b1 i' G  R8 X
   
5.         int maxWeight = 1, minCnt = 1;  
     Y1 S4 `5 Q; [: ]\" o, z
6.         while (maxWeight < n) {  4 }' U4 `5 o. x# I3 h( u+ I
   
7.             maxWeight = maxWeight * 3 + 1;  
     o$ s7 n& O$ Y' \
8.             minCnt++;  % _0 T5 z- q1 K# y8 ^( P
   
9.         }  2 o4 a& o# R  I: H7 I! O/ A
   
10.         System.out.println(minCnt);  
    4 e4 r7 N; j- g* [% q8 F3 F2 G\" X
11.     }  4 Q; h; B  F4 t. k! G7 E& O8 M/ p
    
12. }( D7 ^. K9 G4 z& a' b0 L
    

复制代码

题解
' w' W5 h9 ^" i! E5 i如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
" ]! Z( Q) V0 I此时我们想扩大区间范围就只可以增加砝码
. V" Q9 O8 ~  n5 Y# J假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
3 B" Z! e8 D! J' E; V% z所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
7 C) n$ n* u+ J# ]) h# u* L
让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

; Z  v3 D& y. T9 @$ O: y- r9 R另 n + 1 = k - n k = 2n + 1
2 r2 G3 [% B0 [3 i那么x + 1可以控制的最范围就是[1, 3n + 1]
) n9 Z. N, b2 m, \9 Z' C* W. E
" q+ n- h, r) {3 l3 \( i