QQ登录

只需要一步,快速开始

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

最少砝码 Java解决

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

1186

主题

4

听众

2922

积分

该用户从未签到

跳转到指定楼层
1#
发表于 2024-3-29 16:40 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
问题描述】
% `% `8 G, |4 i你有一架天平。现在你要设计一套砝码,使得利用这些砝码可以称出任意小于等于 N 的正整数重量。2 h* P$ ?- r0 k; a* p! @
那么这套砝码最少需要包含多少个砝码?
3 H' A/ z% w7 Z& C9 Z注意砝码可以放在天平两边。
  T9 _$ ?, q+ ]* U# h6 \0 h* @, F
1 Y7 h" k( Y  m6 R0 k【输入格式】
" ]( [' R  F) n+ T" v7 l输入包含一个正整数 N。
. I1 O7 L" D& g* J! I. v( }. B% s- c5 ^
【输出格式】
: ^& |1 _: k; `. g, Y输出一个整数代表答案。
. |' g! V8 ]9 Q; j2 W5 E3 H* E
. g! z% \) s# \2 }+ t9 ?( f) g【样例输入】( ]' @; Q5 U$ e) Z
7
& U+ Y" N- [% o" q( z! u0 M
2 i4 k' r2 }3 W: l" [! a; j, Z6 Y【样例输出】. ]; c: ]4 t8 e
31 n( c2 Z. s  A: t

% d1 j* E3 l# `3 B  ^( ^  J2 l6 k【样例说明】( ?$ z# a- V5 ?9 U  f$ U
3 个砝码重量是 1、4、6,可以称出 1 至 7 的所有重量。
9 o% I2 B+ W5 w: |8 y4 R$ Z1 = 1;
- W- v0 ^: W- r. M$ c9 F' V7 O2 = 6 − 4 (天平一边放 6,另一边放 4);
, V+ s3 n' f8 `: H' P2 ?1 b3 = 4 − 1;4 i4 y$ C. ^& A; w" j
4 = 4;: u+ S3 m& a" ?6 M
5 = 6 − 1;
$ w: g- R8 s! V  U: S1 h6 = 6;
' d  P8 K+ V& Q- u, J7 = 1 + 6;* f$ K+ Q( c* v6 L% Z0 [7 B7 v
少于 3 个砝码不可能称出 1 至 7 的所有重量。
  1. import java.util.Scanner;  
    - _- O& d* b7 N
  2. public class Main {  
    7 E5 q. m, T. \9 X
  3.     public static void main(String[] args) {  . ]& Q5 i% l. K
  4.         int n = new Scanner(System.in).nextInt();    8 r8 S/ @( ]$ Z9 N$ V4 a& |
  5.         int maxWeight = 1, minCnt = 1;  
    , Z: G( _% V% ]& ?
  6.         while (maxWeight < n) {  : F; R4 m& n8 m6 ?- a! Q& ^
  7.             maxWeight = maxWeight * 3 + 1;  
    \" s& a9 ^3 O0 f$ U- P; ]' [
  8.             minCnt++;  ' K- A3 n8 a; U- w
  9.         }  
    ( m, t1 Q; E8 }/ y0 q- l7 F
  10.         System.out.println(minCnt);  
    * O* \5 k- L0 |# h* {. ^
  11.     }  
    5 }\" ^' L7 _; I( n\" ~\" A
  12. }\" M# V8 [- g# S! m
复制代码
题解/ |  L3 |2 s; l7 g8 V1 w$ d2 H
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个7 c9 h4 _9 J9 U0 a
此时我们想扩大区间范围就只可以增加砝码$ t$ ]  F( K  R% B/ k' P" }. V
假设增加的砝码重量为 k
+ v2 g# T  [4 \" G因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作! E1 l8 r( R- w) g  N
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了! k7 Y9 w/ I$ I0 @( \& [
: b; V& |" m2 T
让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围; g; \9 X( v6 P* o& ^
; ]2 B, @7 q8 t5 g
另 n + 1 = k - n k = 2n + 1
) }' B' E; d  D  L% V那么x + 1可以控制的最范围就是[1, 3n + 1]
7 I7 L! `) P& e( k3 Y
3 k6 B4 k: E2 U6 v% a. ]( }4 g
" b( q& p7 s+ G/ v
* ]5 g/ l7 [; Q8 {% U
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, 2026-4-10 15:57 , Processed in 0.372686 second(s), 50 queries .

回顶部