最少砝码 Java解决

2744557306

问题描述】
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
. _* i# l& [9 ~6 z! o那么这套砝码最少需要包含多少个砝码？
! k- e3 d8 K; q注意砝码可以放在天平两边。

; m, d1 V# G( ^6 \( s【输入格式】
! \! J) {3 T% E* }2 d输入包含一个正整数 N。

* k1 c) v) ~3 j9 S3 o: n【输出格式】
1 D8 o, |) K$ W' J* G1 ^. ?输出一个整数代表答案。
7 j, a$ S" r; k4 m; E
8 o; e+ {7 j5 x  x【样例输入】
7
4 }2 ^5 Z- h# z- c
【样例输出】
3

【样例说明】
/ z3 t6 j  y4 }. G( L/ z& e3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
$ ~! I7 j, t) C( c% i1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
& j# d) N0 f1 R' u' O) t4 = 4；
. A7 v/ `4 F0 K9 p5 = 6 − 1；
8 y' R6 T; D9 W6 m6 = 6；
7 = 1 + 6；
* |4 ?  q/ t2 i: X' m6 P2 L少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   ' Z  Q$ k0 o$ D3 C1 F) H- b# R
2. public class Main {  8 b0 Y2 ~/ V\" L; f6 w4 E
   
3.     public static void main(String[] args) {  
   ( l( u2 }+ v6 k
4.         int n = new Scanner(System.in).nextInt();    ( O$ Q0 X5 `$ B. |
   
5.         int maxWeight = 1, minCnt = 1;  
   ; o: g& D0 h. |( [8 p8 c
6.         while (maxWeight < n) {  ! J/ t. P) f' Z) B) E
   
7.             maxWeight = maxWeight * 3 + 1;  
   5 F4 J7 s8 w2 H3 F7 k
8.             minCnt++;  0 s+ G& v+ w0 \$ }; w) Y& i# s: H
   
9.         }  
   2 U5 j& r5 k9 m. `8 s
10.         System.out.println(minCnt);  
    ' f) {$ c: u& ~. a6 a
11.     }  
    / b9 ~* W: n& `4 Z) A2 ?# G
12. }
    3 q4 r- E\" d: j' y  \3 n

复制代码

题解
* _- p. {5 ^9 K- V2 S" g, o如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
0 d5 [, {5 g' w9 g8 p  z3 l此时我们想扩大区间范围就只可以增加砝码
7 i( e2 U; J/ m6 v假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
! I0 G9 v0 E9 [& V' C- G% `所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

6 E: ?  ]" F9 M, R: W让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

另 n + 1 = k - n k = 2n + 1
; O. {' d& z7 e. _1 ^) z那么x + 1可以控制的最范围就是[1, 3n + 1]


9 k  ]! ]- W- a( t9 }) K( f