最少砝码 Java解决

2744557306

问题描述】
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
# y1 ~# a# Y; B那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。

0 ?+ |/ `% l  K【输入格式】
输入包含一个正整数 N。
2 ]4 U! f/ ]( Z% b" [
9 y& [3 M- f) f! T. ~【输出格式】
输出一个整数代表答案。
  Z9 F$ [0 h7 y9 ?9 W
+ d( }& \$ a- E$ `【样例输入】
" V* W3 c- H7 ?- _7

( ~* R) g" `- ~9 i7 _. [7 {【样例输出】
3
5 j. ^6 v/ P) V; n- ]$ M5 t7 E
/ Z) F9 f7 b# l8 a* ?【样例说明】
7 W: }6 l. a- s& Y3 k3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
5 b2 h  R6 K1 M/ h) T9 ~9 y3 E3 = 4 − 1；
4 = 4；
5 = 6 − 1；
/ h! p( }) [' c6 A$ L/ N6 = 6；
1 M9 {4 ^; b" J( S/ b7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  ! Y1 c- d4 h( z$ A* M1 N9 c
   
2. public class Main {  
   1 O) Q' t/ j6 V6 E
3.     public static void main(String[] args) {  ' d* _( f/ \$ S' @4 i+ ?
   
4.         int n = new Scanner(System.in).nextInt();   
   \" v\" n6 l# N8 I+ Y) {
5.         int maxWeight = 1, minCnt = 1;  
   7 r2 h/ k8 b6 v
6.         while (maxWeight < n) {  
   - p0 j6 m+ V6 d% d9 K
7.             maxWeight = maxWeight * 3 + 1;  
   4 V: q6 Y, t) F\" q6 _4 D3 @
8.             minCnt++;  0 k/ s6 {* `8 e+ w
   
9.         }  1 V' D3 @* q, e, }
   
10.         System.out.println(minCnt);  
    % a9 i/ k! S& v# T8 k7 K  e6 Q5 a
11.     }  + a1 G. [0 v\" M8 G/ B' }
    
12. }, H% R& ~( Y' n5 [/ b
    

复制代码

题解
. q6 r) q* x! P3 c如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
# m2 h  r+ S. L此时我们想扩大区间范围就只可以增加砝码
7 N+ Q, F( o3 h" q) A假设增加的砝码重量为 k
  R& N$ G6 L* M; G7 j+ d" V5 K因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
$ g0 J8 g2 B# N1 p0 K所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
. f; U& |( a8 f) I# p0 }; n1 s$ O
3 h  j( d6 ~: V4 l$ f; s+ G另 n + 1 = k - n k = 2n + 1
; o: `* q! b9 t) z6 a: _那么x + 1可以控制的最范围就是[1, 3n + 1]


2 g( o  p  i& R) a- E0 h$ ^" |! `