最少砝码 Java解决

2744557306

问题描述】
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
9 V& I7 n; @8 ~$ t: w+ Z注意砝码可以放在天平两边。

; Z6 h4 Z! F( y# h! m( L【输入格式】
输入包含一个正整数 N。

【输出格式】
. l9 K. \! h1 ~( s* U- H9 p输出一个整数代表答案。
  g; ?; ~. s! U6 A  n' l+ D
: d  N9 Q" Y7 C【样例输入】
1 q! N4 M- x+ S7 X2 N7
/ V1 f4 n( L0 }0 B1 n2 w; g+ K% U* L
. Y  u+ c. ~9 D$ r! R# k, Z【样例输出】
& `! G- ?" \: Y) ~* d" u/ ^6 h3
8 p; H2 \+ ]8 O" e7 N9 Y) R! X
【样例说明】
( [2 {4 x# p4 \$ I- j/ P3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
4 z6 H# h" F1 i' ]- P7 k1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
5 = 6 − 1；
6 = 6；
7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   $ q2 Q. V' _5 T
2. public class Main {  
   # ?5 E4 w' g# }) s\" ^; q, ^5 g+ b  m
3.     public static void main(String[] args) {  
   . J0 u8 x% L( q/ Y) u. P+ Q# k
4.         int n = new Scanner(System.in).nextInt();   
   ( M) R6 ~; X; ^/ ]
5.         int maxWeight = 1, minCnt = 1;    e7 y, x  b  Q+ N2 n
   
6.         while (maxWeight < n) {  3 K8 _  V$ V) y) F+ U
   
7.             maxWeight = maxWeight * 3 + 1;  
   1 J5 _. p; u) Y
8.             minCnt++;  
   3 b/ G\" O( O8 |# [
9.         }  # g* F! n- E- |5 ~3 B* H; B
   
10.         System.out.println(minCnt);  ( J8 z1 J4 S\" W: O0 B8 p
    
11.     }  
    1 W  {5 U/ X- ~8 v0 a
12. }
    3 u3 [' C/ ?; [/ \& D! w

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
: P  V! z/ h/ s* |: }3 k此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

  c. {$ S1 }& Q, k" _1 j让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
& X( K( i% z6 H4 S4 [
% E0 v+ H: F) J8 h' M2 s  \另 n + 1 = k - n k = 2n + 1
& n3 W) |3 p( U5 R0 F那么x + 1可以控制的最范围就是[1, 3n + 1]
, Q1 z6 t) T+ h. o3 f
: d: j4 U, a3 o7 p+ D9 P. I5 j& D
+ {  e6 A: M, x9 l2 Y