最少砝码 Java解决

2744557306

问题描述】
* n; Y' r9 ~! s, W! k你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
. c2 t1 @  I& Y那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。
' y) N& s4 o4 W0 H; L4 Q
% ?  P, S* y" i7 X( n【输入格式】
输入包含一个正整数 N。
3 b- k. t8 G: R6 L6 w6 J
【输出格式】
输出一个整数代表答案。

. R0 A  V# b7 X4 ^9 H【样例输入】
0 O$ g0 ~6 x# V8 z" r' F" u+ D7

0 [8 u3 Q  {- ?* [( D【样例输出】
3

【样例说明】
; Z" s; ^5 q( n3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
5 = 6 − 1；
6 = 6；
, s0 }" P' e  V' a1 P7 U' i! C7 = 1 + 6；
2 S- g, k3 `' X: L; e1 s* l  A少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  6 P+ c- j& a3 n
   
2. public class Main {  
   . u4 y$ {* i8 G
3.     public static void main(String[] args) {  
   \" f+ h5 @: p$ M) |
4.         int n = new Scanner(System.in).nextInt();   
   . @$ Y- ], Y: D4 T
5.         int maxWeight = 1, minCnt = 1;  ( a& `( F$ T$ E5 @9 T4 U
   
6.         while (maxWeight < n) {  , I, q: I# J7 n+ m2 Z
   
7.             maxWeight = maxWeight * 3 + 1;  
   5 ]: o6 s) j) B. q5 R* p# F
8.             minCnt++;  : S, ]1 k. S+ G
   
9.         }  8 X8 Q& l7 G; q- Y3 J4 D! N( W
   
10.         System.out.println(minCnt);  2 z& L! Q- G; l% ~5 P# C) E; `5 ?% m
    
11.     }  ( v6 `0 C6 }' S9 \+ x
    
12. }
      ^7 S# r2 G% ^$ L

复制代码

题解
5 V0 N7 L( X& n: x! W% t如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
( M% P/ ~& H$ C此时我们想扩大区间范围就只可以增加砝码
+ z' c7 N- P5 k# C  J" a3 T8 o( y* X# @假设增加的砝码重量为 k
3 U: P- s, {# ~+ f4 a3 d因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
3 }. Q* s9 i0 }
, \. U8 p- n# C让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
0 P( o$ F3 v& o# [3 h" S( F
另 n + 1 = k - n k = 2n + 1
那么x + 1可以控制的最范围就是[1, 3n + 1]


/ w4 G. w- \! ]8 C$ U2 k/ W$ d
2 ^8 X' y* _' D! |