最少砝码 Java解决

2744557306

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

【输入格式】
6 B9 z4 J* R# o5 J2 t. D+ l输入包含一个正整数 N。

【输出格式】
输出一个整数代表答案。

【样例输入】
8 |# l: C4 M" w7
: Z6 a3 K. b0 D
【样例输出】
  A9 M. g* |, [# W; T3

【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
$ m. m# x- C- S& c) \1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
( T; w, Q# s- y5 N. `  W. @$ R: \3 = 4 − 1；
: U6 ]1 |, x& Q, ?/ z( g4 = 4；
8 n6 J  ~$ _/ o6 o) k) ?$ t5 = 6 − 1；
6 = 6；
7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   , i' w4 N/ {- s$ L6 P
2. public class Main {  * p$ l\" \. Q% F) c
   
3.     public static void main(String[] args) {  \" r% W6 v  B/ v+ j
   
4.         int n = new Scanner(System.in).nextInt();    9 z: d7 T# T& r
   
5.         int maxWeight = 1, minCnt = 1;  
   1 o5 [# Z7 ^0 O
6.         while (maxWeight < n) {  ) h* g- }/ G: @: h1 m
   
7.             maxWeight = maxWeight * 3 + 1;  
   ; U8 T0 p2 {; U* o
8.             minCnt++;  
   + {+ z2 J* M1 j% y' F7 C
9.         }  
   3 E) v& C\" K' S' ?0 i  u- ?
10.         System.out.println(minCnt);  * p  N- l7 ~9 U  U\" M, ^# T- }* ^) _
    
11.     }  % |2 w5 G) f0 z  i% J4 ]7 _! e
    
12. }5 |( `2 F' i! s) i3 Q
    

复制代码

题解
  N$ W$ x/ p9 x$ u! q如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
- y, U- L7 i9 r此时我们想扩大区间范围就只可以增加砝码
. P  s% [+ Z: `( g; ^- e$ w假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
) o$ N9 Z0 m+ w0 B
: {; T* {' s6 s8 g, \9 p让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

0 Z0 y( |, ~. P% Z9 d# d另 n + 1 = k - n k = 2n + 1
9 |- D" o) E! s  d% E; t, S那么x + 1可以控制的最范围就是[1, 3n + 1]
' m% W  M, C* K4 {% f5 e) M* q, d/ P; N

! S' q# e" o( |# y. _# j: s