QQ登录

只需要一步,快速开始

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

最少砝码 Java解决

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

1189

主题

4

听众

2934

积分

该用户从未签到

跳转到指定楼层
1#
发表于 2024-3-29 16:40 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
问题描述】
) p: n# B, G! V$ @: ~- {& V' e你有一架天平。现在你要设计一套砝码,使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
$ r' v2 h( E1 n那么这套砝码最少需要包含多少个砝码?
+ _- ?6 J, `# X* K注意砝码可以放在天平两边。; M5 n8 Y2 y( G7 I
4 d1 P& F* y7 \" H- T
【输入格式】& D4 L  F8 |" z$ P+ J! S
输入包含一个正整数 N。
/ i7 e7 u! {( e& J1 h! z$ [& w
7 i) B3 y! s3 a【输出格式】& a% b7 v& S. N5 c
输出一个整数代表答案。9 Q0 G4 \* i: i6 }/ q, h

% z" x8 Q' l/ g: y2 Q& B【样例输入】
2 y3 j+ v3 k% f/ f7
+ P  R0 F* e* J/ I3 Z  R" V* D) D
【样例输出】
" d2 R2 L6 O$ Z1 S6 {( d$ a& {2 i3% h8 C+ f' f: O$ |6 f& z

) O9 u. e; z# l【样例说明】# y0 w( J' _% n' I7 ]" y
3 个砝码重量是 1、4、6,可以称出 1 至 7 的所有重量。
- @6 t* R- M6 d: J, ?# Q4 b! N0 F1 = 1;
5 r2 [6 U1 z2 C4 d2 = 6 − 4 (天平一边放 6,另一边放 4);
. ]8 o+ p% Z  L1 Z3 = 4 − 1;
$ b' l. o2 f9 U5 e) e6 H* i( W  `4 = 4;. u2 i% y. @8 |# {
5 = 6 − 1;
/ g9 @( r9 |' T; l' x6 = 6;( c# m# Q$ x( x6 |& l
7 = 1 + 6;
; i  B0 @8 V: }/ ~' ~1 w少于 3 个砝码不可能称出 1 至 7 的所有重量。
  1. import java.util.Scanner;  4 g  O4 X\" F4 J# d0 K2 e& D0 g
  2. public class Main {  
    0 z1 S4 F% c7 W4 F
  3.     public static void main(String[] args) {  
    3 `- [. h$ W& R7 L\" y' _. h
  4.         int n = new Scanner(System.in).nextInt();   
    * P. M2 E; `. v8 J
  5.         int maxWeight = 1, minCnt = 1;  
    . X: h! }% }+ H* w& z
  6.         while (maxWeight < n) {  
    * e4 N) U- u  u, N
  7.             maxWeight = maxWeight * 3 + 1;  
    1 e7 ~- X9 l5 ^8 t7 g# X
  8.             minCnt++;  * f- L7 z, ^0 y/ D0 |2 M( [7 k
  9.         }  7 u, u  }& o7 P- U8 M
  10.         System.out.println(minCnt);  - Q& ~+ w8 u# h6 P6 S% J2 `  x
  11.     }  ) J+ B+ C; \4 C3 y
  12. }
    / c  s! G( C& ^( r
复制代码
题解, ^4 m/ b8 {+ @( |
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
$ D6 ]! _: o8 S/ i+ ~& {此时我们想扩大区间范围就只可以增加砝码
$ }/ b4 o0 K5 Z  h2 x假设增加的砝码重量为 k
0 X% K# E+ e1 |+ M1 R因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
: e" v' r; f! e' {, Q% d! B4 A所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
4 d( k+ D0 S+ R5 X" V& e
. J) m! C4 m7 _8 _让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围7 a0 Z+ a+ P: @1 o( A
5 W8 y' g; x, }3 ^/ r) @0 s
另 n + 1 = k - n k = 2n + 1
3 N2 u1 t9 e7 @5 [那么x + 1可以控制的最范围就是[1, 3n + 1]: r; v, J  y/ J8 k( ~
9 l" k; n! y$ u, e
. K, a2 r- O/ S

8 ]( f! M$ ?, U8 K7 e9 ?: y1 ]( ~) 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, 2026-6-15 01:57 , Processed in 0.420034 second(s), 51 queries .

回顶部