数学建模社区-数学中国

标题: 最少砝码 Java解决 [打印本页]
作者: 2744557306    时间: 2024-3-29 16:40
标题: 最少砝码 Java解决
问题描述】
. E% i- {; [: m  x/ m你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
: h' ^8 B. u" M2 ~$ z+ V那么这套砝码最少需要包含多少个砝码？. l4 {6 c% ^8 `! |5 m) R3 ?
注意砝码可以放在天平两边。& D* M, Y( [3 T! g( t3 n) o
7 i! P8 v" x  b; C
【输入格式】; Q: F4 h# p3 ]9 H' R% J/ \
输入包含一个正整数 N。
( [7 A% h4 E9 y/ N* G/ Y! p" v4 ?1 |4 S; r$ G5 J, [: P6 j
【输出格式】6 o' t* V0 R. p2 G2 A* ]- _. c
输出一个整数代表答案。1 G# a, r- V1 }  O3 m8 f. b# Q

: g/ k' i$ @) b* Z( O【样例输入】' m) R" Q/ c1 w0 m) z0 p, @+ k
78 T/ q9 L; L+ S: k
/ M# S$ d1 v& k
【样例输出】9 n7 R9 O/ z% Z9 L( A
34 h. `4 W0 V/ R1 k3 Q& O' o; A- h2 o0 I! t

8 \, h. s! a, j( G【样例说明】5 w9 u# m" @* K( M% D
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。1 ^8 [6 Q4 Y/ M3 ?6 e, g
1 = 1；
) N. X9 g$ s6 q! q9 i+ G. T/ Z2 = 6 − 4 (天平一边放 6，另一边放 4)；5 g, Q) _5 z& `
3 = 4 − 1；+ @& ~6 T6 m/ M# D% J
4 = 4；
" q" Z7 B8 ~2 X0 j. T5 = 6 − 1；
1 V# l. j% ~2 u6 = 6；$ X2 Q, [8 p- P* }2 f
7 = 1 + 6；
* }* J- B5 Q/ F# F* D4 |. U1 |) C1 d少于 3 个砝码不可能称出 1 至 7 的所有重量。
  1. import java.util.Scanner;  % X  b1 I! j2 s3 r5 r5 X5 k, j
  2. public class Main {  0 q3 E5 K4 T& c3 `6 p
  3.     public static void main(String[] args) {  
    . Z8 p: g- c' a* \; N) _
  4.         int n = new Scanner(System.in).nextInt();   
      Y* K& h  l' Q) Y4 q. o
  5.         int maxWeight = 1, minCnt = 1;  
    7 M$ r7 p" e7 t: i" n9 G0 f2 d6 X
  6.         while (maxWeight < n) {  . C, F5 x& H/ k' ]
  7.             maxWeight = maxWeight * 3 + 1;  5 R% w- w$ `% j+ \1 I
  8.             minCnt++;  
    $ f9 J- u8 M3 S. d1 p# W
  9.         }  
    ' g3 T; Q0 b/ J. K/ H  w% R' d3 ^# f) }
  10.         System.out.println(minCnt);  7 E7 m4 D/ F/ T) Q
  11.     }  
    # z5 S. o" l: u3 z3 \/ X: _
  12. }
    8 P" N0 R3 X( q8 s, q* ?
复制代码
题解
9 N% o4 g; I1 G6 t0 a7 J0 y4 m如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
3 I4 B$ ^8 t# D( A5 ]: z( M此时我们想扩大区间范围就只可以增加砝码
6 |# b- j. L+ |8 J假设增加的砝码重量为 k: ?; u' ?2 }1 \' Q( {6 z- R& Q
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
0 R, I! Y) \' P+ ^0 H  ?4 s1 h所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了* C" l$ d1 u( L% N+ d

" k' e4 y$ _8 Y5 U让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围1 \1 W! }( e# P: i6 M3 c5 n

  |* V9 @5 `3 R& I6 d" p另 n + 1 = k - n k = 2n + 1+ i2 }, W6 a: C
那么x + 1可以控制的最范围就是[1, 3n + 1]
+ d5 d) t$ G- m5 u/ C/ j+ J
, f, ~. k& {9 l3 |: N* E' V
6 f2 {" l$ h& S+ }  v$ z1 ~& `* \/ d- {




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5