最少砝码 Java解决

2744557306

问题描述】
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
' y" A. Z" s# a' {9 E( }5 o那么这套砝码最少需要包含多少个砝码？
1 D. _8 c" z' |3 G& _注意砝码可以放在天平两边。

【输入格式】
6 ]! s0 i" ^& R; [% C* Y; f输入包含一个正整数 N。
* V* r# d! ]3 Y( M; v4 i0 {6 |
【输出格式】
' `/ N) A  w. u- e6 E输出一个整数代表答案。

) j! e/ b' I: _7 Z6 o【样例输入】
( C6 h6 e, {$ M7

. z  v2 h# ]) N【样例输出】
) ^) }: J* A6 g3

【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
$ f) M% ]. [7 Q' ]# u1 = 1；
1 f3 n- T/ K" x& e2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
2 e2 n/ u1 ?+ S- p' @; t) O2 r, J4 e5 = 6 − 1；
! `' x7 e  t0 o6 = 6；
. a+ ?" L0 u- d1 f+ t# t7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
     f  ?, k5 `, u+ o\" L. q7 D
2. public class Main {  % G9 m, N1 Z# Y. q\" o7 j& b
   
3.     public static void main(String[] args) {  
   & J* [$ L! @6 C0 L; Y' U
4.         int n = new Scanner(System.in).nextInt();    ) J$ y! e# E  n8 w; B- \+ O# D, A) v
   
5.         int maxWeight = 1, minCnt = 1;  
   ; b7 v8 t/ I/ J  ]4 u7 f
6.         while (maxWeight < n) {  + n) R: U% C6 l, l  V6 y! ^
   
7.             maxWeight = maxWeight * 3 + 1;  ) b% y/ Q  W9 h6 A
   
8.             minCnt++;  
   * v1 E( n- O: i0 I9 G! F
9.         }  \" D  j* v8 m+ [% s6 m+ J/ O
   
10.         System.out.println(minCnt);  + G0 Z) Y2 ~& l/ `
    
11.     }  
    * a. \3 o! [# R- d9 H
12. }
    6 K( L2 o- K  P1 q

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
. m* W6 ^0 x2 E" V0 u此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

! k& y& m  g5 x8 @& b让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

另 n + 1 = k - n k = 2n + 1
3 M( ^& m. q8 c9 L/ }3 }8 P那么x + 1可以控制的最范围就是[1, 3n + 1]
  _9 b! Z! e% r3 O/ k" [$ l
3 D8 w6 W8 u- b& t+ N
) w& D4 q$ b7 t8 y
* H+ N3 M( B: T: c