QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1291|回复: 0
打印 上一主题 下一主题

最少砝码 Java解决

[复制链接]
字体大小: 正常 放大

1175

主题

4

听众

2828

积分

该用户从未签到

跳转到指定楼层
1#
发表于 2024-3-29 16:40 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
问题描述】
) |8 i: S, d/ o! ?你有一架天平。现在你要设计一套砝码,使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
& M6 t9 c4 s% z" ^) _/ s6 r+ @那么这套砝码最少需要包含多少个砝码?
0 I! b( M* {5 e6 F  O% R: q注意砝码可以放在天平两边。* F, t, X5 ^0 r( A9 y
# P; i4 u6 Z# ?' L2 g5 H4 H
【输入格式】. x5 H5 f* i7 k/ Z0 W8 V% K. K
输入包含一个正整数 N。
. q6 O; i, h  \, ^/ l
1 `* @+ H7 Q- \" {  N# s【输出格式】
  @6 X6 l& ?, p输出一个整数代表答案。1 L4 k# c# ~  [% |3 x8 \
3 S+ M) B% i$ A( `
【样例输入】
$ d  X% |4 X! z; G) K6 s- P7
! R$ C$ \: p* Y" C% r4 K; p% ?4 {7 p/ o: L2 h' D
【样例输出】
6 {8 b( ~7 X3 b( A0 A1 M' \3
6 [4 Z& g; P& h1 k) _4 C) [2 j; D" f
【样例说明】
, ~& ]! P/ c$ T* U3 O% ~, b3 个砝码重量是 1、4、6,可以称出 1 至 7 的所有重量。
& Q# D, \4 u  m  @$ n$ ?( O1 = 1;
( L4 a* q/ E7 h2 = 6 − 4 (天平一边放 6,另一边放 4);3 t( S. E7 S7 j% q$ x5 S/ b/ h
3 = 4 − 1;
+ l1 z. P! d$ n7 @2 |: l3 u4 = 4;
9 h; w/ U/ T$ }5 = 6 − 1;' J+ S2 h0 H8 P# {6 w  @3 G- a
6 = 6;
8 O% A! X* Q3 n! ]8 V7 = 1 + 6;
# g9 ~5 k2 {$ Y6 L. L2 n! }7 ^少于 3 个砝码不可能称出 1 至 7 的所有重量。
  1. import java.util.Scanner;  % P* [/ t4 @! f% u
  2. public class Main {  0 c9 T\" x5 ~% R( F* B5 M' g
  3.     public static void main(String[] args) {  $ {7 U/ u( f# }3 G, V, ]4 t
  4.         int n = new Scanner(System.in).nextInt();   
    7 y* [# ^/ Z% A
  5.         int maxWeight = 1, minCnt = 1;  
    9 m! y! J; ]* Y\" O; @3 u& r
  6.         while (maxWeight < n) {  
    . q% E2 I3 B: B3 I- h
  7.             maxWeight = maxWeight * 3 + 1;  + m9 m\" n: d4 N6 g3 D$ x, ^7 D
  8.             minCnt++;  ; `7 H) ?/ G- K4 N& U8 o1 x
  9.         }  
    + I8 R  m; w+ @! e! s9 w2 `/ y+ ^
  10.         System.out.println(minCnt);  
    # G+ d1 y  H) d& M; S0 i
  11.     }  * }; k% _7 b0 {: r- S7 w
  12. }
    ; ?& q0 r* V: ?8 \  c
复制代码
题解" E* V4 o) z% }' ~; P* ^/ c
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
8 _; a3 n+ T; G. @0 n此时我们想扩大区间范围就只可以增加砝码
& u& ?! L/ S. l, A5 d7 v/ p  T假设增加的砝码重量为 k7 `- t; F: S8 n: x8 h: {
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
8 r1 E6 l" s7 J5 S6 m  E9 @+ m9 X  M所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了' x& X% {" W: ^6 ]! u

$ x  ]7 I3 }8 {- ]让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
& ]- Y8 i" c3 y; Q, L% E
' h* w* z) m0 _1 x另 n + 1 = k - n k = 2n + 1+ }2 Q: F8 Y- H$ ^
那么x + 1可以控制的最范围就是[1, 3n + 1]
9 X% A2 Z1 q: G" E
# Q4 ]/ w# x$ `) P+ ]% t4 E8 a) w7 [+ {5 I
* y8 Z- C. I. B' J/ K6 b0 h
zan
转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
您需要登录后才可以回帖 登录 | 注册地址

qq
收缩
  • 电话咨询

  • 04714969085
fastpost

关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

手机版|Archiver| |繁體中文 手机客户端  

蒙公网安备 15010502000194号

Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

GMT+8, 2025-7-24 03:09 , Processed in 0.411384 second(s), 50 queries .

回顶部