QQ登录

只需要一步,快速开始

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

最少砝码 Java解决

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

1189

主题

4

听众

2934

积分

该用户从未签到

跳转到指定楼层
1#
发表于 2024-3-29 16:40 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
问题描述】: ]5 n! D! S/ X- b
你有一架天平。现在你要设计一套砝码,使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
  P" l; E: _; J) ]那么这套砝码最少需要包含多少个砝码?
  A# h/ X, i2 r3 C注意砝码可以放在天平两边。+ }; A9 Z( l) [& T$ M6 q
4 c4 ]0 G$ R6 Y( \% ^6 G
【输入格式】" @7 u) W8 A- X( g0 ]4 ~
输入包含一个正整数 N。* P: X- y. c1 X3 o, p$ r$ I) s( M
7 e' Z4 _0 W/ \# M: }; M9 A
【输出格式】( ~  k. B+ [' `
输出一个整数代表答案。
. w- R2 R3 ]9 s6 k- G8 D+ Y1 X
4 e7 ]' Y' H$ S  _) h. ~【样例输入】3 Z* W& F) ~* R: x: f
7+ T# p1 i1 Y* v/ I( l

/ @9 S2 i  H5 C【样例输出】
+ `! X( u) _9 A8 V5 O3
* {. ?8 P" T1 i/ `0 |9 t
. w5 @/ S  ^+ p$ r3 m- i" K【样例说明】
% I. V7 v0 M' F+ U7 o* Y3 个砝码重量是 1、4、6,可以称出 1 至 7 的所有重量。% y$ v+ C9 z6 \" f
1 = 1;7 {. U9 O5 @( Y7 s6 d; B8 T2 z
2 = 6 − 4 (天平一边放 6,另一边放 4);5 d0 [  @3 m9 G4 F
3 = 4 − 1;
5 ^+ H- r7 I) T# V: Y( L! j' H# F4 = 4;
% |( G# t# h1 C& K/ n2 s: K5 = 6 − 1;+ ?: t# g$ e& z5 S; f
6 = 6;
' T+ h0 a2 y3 w8 s3 m7 = 1 + 6;' r  R: {) N1 |, h& j. L
少于 3 个砝码不可能称出 1 至 7 的所有重量。
  1. import java.util.Scanner;  9 M+ T3 \- ~% v& W! |, L8 x& I
  2. public class Main {  
    $ r) p8 L4 J! [$ N4 Z( O9 s
  3.     public static void main(String[] args) {  
    6 o! ]3 q; z1 F9 d- z8 R
  4.         int n = new Scanner(System.in).nextInt();   
    3 f& u' o- q, O9 E% ^) ~
  5.         int maxWeight = 1, minCnt = 1;  
    ' h6 W\" G; M$ J! ^
  6.         while (maxWeight < n) {  , s$ }+ S, X9 l2 r2 w( x* k
  7.             maxWeight = maxWeight * 3 + 1;  * _6 _+ `- P/ |5 a6 T8 z- ]& |
  8.             minCnt++;  
    - K5 T1 Z+ w. P9 O; k; T( m
  9.         }  
    # _, o/ ]5 u# Y, X
  10.         System.out.println(minCnt);  
    . t% x/ V. I+ w& m
  11.     }  
    , w% `8 N' j3 h; s: j
  12. }) Z# O* c5 o$ v0 i
复制代码
题解; r7 T) B7 |0 L0 |
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
- G1 O3 u- e+ a0 h: H此时我们想扩大区间范围就只可以增加砝码
- d0 C, v$ \: Z2 o' W# Y假设增加的砝码重量为 k8 D9 f5 ^) t8 P  `$ x8 D0 ^
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
- H% E$ e  ~, Q% ?所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了/ i! _/ f" ?; E
5 M4 b3 \+ h4 s" i4 w# u3 c
让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
1 |8 F$ r0 H" K/ j  Y# v) R" z8 H7 Z0 x6 C/ P# P
另 n + 1 = k - n k = 2n + 1
* @& d: ~2 I5 T那么x + 1可以控制的最范围就是[1, 3n + 1]; L* K, ?6 k) P  M9 x  m2 U0 w

/ S6 P5 k! e0 _4 F% `" M% e  ]5 J! m& W  X
" s( U2 w; q9 {/ K, E
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-8-5 15:22 , Processed in 0.423386 second(s), 51 queries .

回顶部