最少砝码 Java解决

2744557306

问题描述】
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
  c' e5 ~/ O- K" \$ `7 S; u那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。

# K# q1 p3 T3 Z" W* X【输入格式】
$ U  h% O4 H. h6 L输入包含一个正整数 N。
/ V) B6 u, x5 D! z( K9 V* o
; H* O/ V* s2 Y; G2 I; k【输出格式】
. o+ \7 v" V" M  W. Y/ e+ r输出一个整数代表答案。
8 U& c7 H/ A# Y% v6 }
【样例输入】
- ~5 K* S/ z, q2 E, c& c7
% R8 p7 ]9 R/ ~( b
【样例输出】
3

【样例说明】
8 y& Y6 P: R$ D. S# C' q9 t3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
- k0 W- Z- t% z" w2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
- T; Q; J2 P$ E5 = 6 − 1；
8 L, T) M2 L% p' G/ F. e! _6 = 6；
6 l1 q; U: h' b2 P3 g7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   % \9 C7 \. \( M) {) j- I8 F3 J\" b
2. public class Main {  ) U2 o( A* M8 c
   
3.     public static void main(String[] args) {  - C3 |( G+ H( I% _) A- C
   
4.         int n = new Scanner(System.in).nextInt();   
   ) U) Z2 R4 f) K! o
5.         int maxWeight = 1, minCnt = 1;  2 X9 h  i# j% K) W
   
6.         while (maxWeight < n) {  , `7 ^$ J  E6 j. C
   
7.             maxWeight = maxWeight * 3 + 1;  
   + ]/ _6 O2 |& l7 m
8.             minCnt++;  6 R, \8 {1 k+ {% y
   
9.         }  ( t' ~$ ?' n! G# E8 z- X) V2 v; \
   
10.         System.out.println(minCnt);  ; d\" @\" W+ q. b# r
    
11.     }  
    4 A6 Y1 l; T' A  a# }* h7 b
12. }
    ' @0 m9 m5 u3 I% K6 q) Z1 a

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
! _" r" n, h9 L/ b此时我们想扩大区间范围就只可以增加砝码
8 V9 W8 `+ E6 ^7 F0 N假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
( ?$ d/ Q. o3 f; B7 k所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

: _+ R7 D  X3 l0 ~; c2 B让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
/ e" `: E6 P9 C# P" h2 y* b
* ^  \9 ~9 |5 }+ s另 n + 1 = k - n k = 2n + 1
* S1 D. `& K: m2 p5 l. e那么x + 1可以控制的最范围就是[1, 3n + 1]
; W% e% |# ~1 S/ z! h+ S

. U. M5 l3 K' S; ?+ K
: B0 P$ Z& a$ y2 @. o( c