最少砝码 Java解决

2744557306

问题描述】
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
! W/ R/ y; g4 s& S注意砝码可以放在天平两边。
8 \1 v. B! S8 u, l+ n5 k
【输入格式】
输入包含一个正整数 N。
: U4 t& o- M+ u3 E
$ ~, R- f! J5 N1 F3 m) }3 t. U【输出格式】
输出一个整数代表答案。

: K9 D# r1 I6 ?4 ?' G# Y【样例输入】
7
0 J6 u+ y$ A" U4 T& ^) ?7 O. X
# a: I2 ^9 I6 F* X6 l& j( V【样例输出】
3

【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
5 l9 R/ P; z% d/ X. O1 = 1；
1 I) Z7 z: J! j, H# K0 T2 = 6 − 4 (天平一边放 6，另一边放 4)；
8 a$ E, y* N& O4 Z& U" [! a3 = 4 − 1；
4 = 4；
5 = 6 − 1；
* }, i8 ^2 A' ~* W. e, S6 = 6；
. X. r, N( \, ~/ y7 = 1 + 6；
2 g( O4 _9 `, \4 _+ h( d" Q* [少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;    U$ [* [  I7 ?, l0 p4 n+ _
   
2. public class Main {  ) O3 W/ u  U. H8 A. J8 J: v8 `
   
3.     public static void main(String[] args) {  
   9 z3 C1 e$ }* F: d% M0 |: x
4.         int n = new Scanner(System.in).nextInt();   
   - ~4 D1 O/ T% O; [- m) c
5.         int maxWeight = 1, minCnt = 1;  7 y7 I+ l4 ~* h3 Y! g
   
6.         while (maxWeight < n) {  / O) y) p: j1 ~  y3 G% u1 S
   
7.             maxWeight = maxWeight * 3 + 1;  
   - f, [% h& T! v6 x5 v
8.             minCnt++;  + e% C9 C/ z4 J' u: T
   
9.         }  
   % S8 L6 }9 l3 s, M$ }
10.         System.out.println(minCnt);  / B/ n* v\" d, z( c: {. b* w7 {
    
11.     }  
    1 O6 V; r9 U\" n# C1 |
12. }0 J, l& O: m0 k$ u+ ]7 u( c
    

复制代码

题解
7 B4 I( ^3 s; r( v9 Y& _/ f# `$ M如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
此时我们想扩大区间范围就只可以增加砝码
' E$ \3 w0 ~0 [7 J0 f9 _1 I. E# j3 O假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
4 m9 Z0 B$ n2 p! o
让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

另 n + 1 = k - n k = 2n + 1
# l$ d( v3 N% J8 d0 i那么x + 1可以控制的最范围就是[1, 3n + 1]



1 `2 ?3 F( x0 _+ C6 I' i. l' G