QQ登录

只需要一步,快速开始

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

最少砝码 Java解决

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

1175

主题

4

听众

2823

积分

该用户从未签到

跳转到指定楼层
1#
发表于 2024-3-29 16:40 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
问题描述】2 `% `! n3 z0 E9 A' g3 X4 t( |
你有一架天平。现在你要设计一套砝码,使得利用这些砝码可以称出任意小于等于 N 的正整数重量。) g/ n0 `) @! Z
那么这套砝码最少需要包含多少个砝码?
6 y3 B1 R) T4 B- L, R注意砝码可以放在天平两边。
. O- Y2 b, @" {
: N# `* \. f! e. |* U" h+ `% h【输入格式】
: Z6 `5 x! ?+ h* {- S8 l输入包含一个正整数 N。) F$ Q% E/ {  y. P4 p4 @* M) ^" Y

4 M8 f7 c; \( S" v7 q【输出格式】
# g- s9 G  |# y& e) w( d输出一个整数代表答案。7 \' t9 R) q9 [' ^& U" q: c

% K; r8 S/ M* E, X: \1 g; M【样例输入】9 m" ]" T( V4 ]$ u+ a+ k
71 q7 K' L/ {! M& V& C9 @

. ^' A, `! f. C3 W) ]- T, v【样例输出】, m3 X% }1 S* }7 k
3
1 \; _+ i  P8 C2 B9 H
& N6 K& `# n! Q2 _% T, |0 k【样例说明】
6 z, j0 g/ i9 Z" m; p3 个砝码重量是 1、4、6,可以称出 1 至 7 的所有重量。
/ ]$ g% ^: w- i4 ?: t1 = 1;
! z& T( f* Y) @. a& V9 d& L' y; {& Y2 = 6 − 4 (天平一边放 6,另一边放 4);$ L+ F# W, I+ V9 S# L5 Y$ u
3 = 4 − 1;& s8 p* F# W' K- o# z/ ?1 n
4 = 4;
6 F- c. X  _8 |7 d# M! X5 = 6 − 1;
5 W1 `5 a, T6 u9 o  P6 = 6;' ^' R' t# z1 O3 A0 L
7 = 1 + 6;
4 _' Z  j2 I" O4 T7 B7 A少于 3 个砝码不可能称出 1 至 7 的所有重量。
  1. import java.util.Scanner;  
      _3 C, Y) o3 |9 w+ a6 Z, o
  2. public class Main {  
    + S! l0 {+ e* b% x! Z
  3.     public static void main(String[] args) {  
    3 j! z$ V- t2 i  _9 J/ e) I
  4.         int n = new Scanner(System.in).nextInt();    6 s) L0 e1 U) n2 b0 ], m
  5.         int maxWeight = 1, minCnt = 1;  ! f$ a( o- `  d& ^  o1 }  m
  6.         while (maxWeight < n) {  
    * y4 h' ~\" R- d9 @5 J0 t
  7.             maxWeight = maxWeight * 3 + 1;  
    5 O. Q; Q1 _$ y. c\" ?
  8.             minCnt++;  
    4 K0 r  o( M; C) P+ M
  9.         }  + n# ~9 Y3 d7 t# S
  10.         System.out.println(minCnt);  
    & X0 j( x4 Q. [1 I8 m- d
  11.     }  
    ! g  H% Y1 f\" W
  12. }
      b; [\" C  n& \+ F8 W+ e
复制代码
题解* D3 y# @( a) H. ]6 W' h# Z0 E  J
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个4 e$ B- S2 B* }; R8 _
此时我们想扩大区间范围就只可以增加砝码
, Q, e& J9 L# V: x. Z' z% w' _" t假设增加的砝码重量为 k. ]7 F/ g. @# |' Q8 c& f, ~
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
5 }( d2 k: l5 M( ~& ]所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
8 j2 w$ o+ ]4 s- Y+ _) V# ^1 E+ ^/ s& O+ \% x6 }
让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围8 R2 K- N% b9 P/ f) p

! n$ ~( @) R& Y另 n + 1 = k - n k = 2n + 1( m3 ^- l9 E; \, z9 z1 u7 {5 B: Z7 t
那么x + 1可以控制的最范围就是[1, 3n + 1]6 Y& z0 @9 @& y+ J
1 g" d( J2 K' m. i
& S3 s$ [# K# M# X: c

% [2 a( {3 y' Q
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-20 12:05 , Processed in 0.297609 second(s), 50 queries .

回顶部