最少砝码 Java解决

2744557306

问题描述】
1 E+ f' @1 N) ?5 E你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。
: O' @( n. g8 O* G2 E2 L: O* ]
【输入格式】
输入包含一个正整数 N。

0 |. M" W  w0 |  k, W【输出格式】
2 s5 r) g7 B  C# w' \! g输出一个整数代表答案。
8 K1 I0 x4 L  T0 G  |; x
【样例输入】
7
% P7 ^# _6 O. W+ ~
【样例输出】
3

& @8 Y- O2 `0 w/ D: e【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
$ R7 a) \; F# l* Q0 s4 \) A2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
; j- N7 N2 n* J) r, N# G4 = 4；
5 = 6 − 1；
6 = 6；
7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   6 s6 ~% {4 M. I/ ]8 ^+ d+ e
2. public class Main {  5 C' O/ q, y) R, ^
   
3.     public static void main(String[] args) {  
   ! e9 C/ }% n! ~6 Q# r
4.         int n = new Scanner(System.in).nextInt();   
   # H\" A, ?. b( x1 _; M+ |
5.         int maxWeight = 1, minCnt = 1;  - [\" v% s1 }7 T  ?; ?1 _. ^6 }
   
6.         while (maxWeight < n) {  - G5 k. u% R- x: p: Y, f7 O
   
7.             maxWeight = maxWeight * 3 + 1;  . ~% S1 ~0 Y* h. K/ p+ u. J. T
   
8.             minCnt++;  
   ( @4 j8 O, g# Z, u8 v5 i5 Y
9.         }  0 k# k  v7 m; o9 Y, Q4 H
   
10.         System.out.println(minCnt);  
    1 D\" H9 @5 b' o: A; C1 {  n
11.     }  ! M# |6 w- u1 G! R& Q1 Z# I
    
12. }
    ' c4 r' d) A9 p; ]9 `

复制代码

题解
6 h0 `- `8 y5 O, ~" e' \如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
# K. E) M" ^/ {8 A! `此时我们想扩大区间范围就只可以增加砝码
8 n. g( S& [# E/ K, O9 t4 g' m& k/ g假设增加的砝码重量为 k
) }- L# R8 y9 F6 r3 D因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
& v" N. e1 B! c- w8 h
让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

另 n + 1 = k - n k = 2n + 1
那么x + 1可以控制的最范围就是[1, 3n + 1]

) W( h* X* _1 ]* C( |9 ^( W9 b% m