QQ登录

只需要一步,快速开始

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

最少砝码 Java解决

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

1175

主题

4

听众

2803

积分

该用户从未签到

跳转到指定楼层
1#
发表于 2024-3-29 16:40 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
问题描述】( t0 p. a: I) u, V0 H) ^; |
你有一架天平。现在你要设计一套砝码,使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
9 _1 i, w3 @7 Y/ M' d- c那么这套砝码最少需要包含多少个砝码?% n) Y, E7 x6 h! C+ w
注意砝码可以放在天平两边。
: G& a2 v% l5 W  e
/ T" W1 O0 T8 Z3 p1 j【输入格式】
( {/ \0 U# _9 r8 B" `输入包含一个正整数 N。
; V% W6 O- B4 O) E, }# m5 H5 |, }# I. r0 g  F7 T. Q
【输出格式】
& @- K5 R9 p1 L3 o0 Z& y输出一个整数代表答案。) \8 e7 i  |0 E2 U" X/ A
" A( S$ I0 |! b3 p! j+ J# N5 E
【样例输入】
) b5 J. v: |( m* y6 A7
; p5 e$ i; y* g+ {6 D
  l% m# @- P0 M/ T+ }【样例输出】' q" R! h" O# r! Q( \% O; h9 l5 {( p5 E
3
9 X( _+ A8 B% k- c& ]5 C* |4 ~0 K, k! ~1 z# x) o) z3 s  c
【样例说明】0 o' a+ J# I" V9 Q+ V0 x0 a
3 个砝码重量是 1、4、6,可以称出 1 至 7 的所有重量。4 s( D: G8 Q) j/ j# e
1 = 1;
+ f1 L5 Y/ Y- e2 = 6 − 4 (天平一边放 6,另一边放 4);/ s0 h1 y, [8 D, W  o+ d- G; S
3 = 4 − 1;' n7 }/ A- `1 e& v, c0 v
4 = 4;  I6 Y, V' E0 Z
5 = 6 − 1;
+ l. R$ }# A+ a. M/ K  Y. m6 = 6;5 ?9 j1 G& @4 `8 O& p
7 = 1 + 6;
2 }: x( R5 |* `1 T- D少于 3 个砝码不可能称出 1 至 7 的所有重量。
  1. import java.util.Scanner;  
    , g) ]$ h( d0 f2 e
  2. public class Main {  , v6 P# G4 E\" L+ i# }' Z+ l
  3.     public static void main(String[] args) {  $ ^; s9 W: `( q5 X  V, b6 X- q
  4.         int n = new Scanner(System.in).nextInt();    9 H7 l- ]* T2 v% ^  w* I) T  ^6 ?
  5.         int maxWeight = 1, minCnt = 1;  ! w* E% w# r# F7 L. r
  6.         while (maxWeight < n) {  6 x) L% a\" C$ |. [7 s8 m( ?
  7.             maxWeight = maxWeight * 3 + 1;  
    0 R* Q4 u. Y: A& p
  8.             minCnt++;  
    3 t$ A5 U6 @( b
  9.         }  * Q8 R% W\" F* }& f0 u3 j3 t
  10.         System.out.println(minCnt);  & L# X* N8 f2 U4 u8 X$ h& |
  11.     }  
    : Y& d  b5 E: v
  12. }$ B9 s\" q- \% U\" P6 ^\" j  ~
复制代码
题解
  O; k' `& Y, @: Y: ^4 t如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个# S7 `# b( Z6 E( C3 R; J
此时我们想扩大区间范围就只可以增加砝码5 c) j2 w; ?  W# N% g
假设增加的砝码重量为 k
+ ~8 q. G/ F* m, @, l4 L0 q因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
9 S) Y/ r$ B8 r8 Q  J+ k0 F# V  k所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了2 z2 T, v$ H+ Y( D% p8 Y% H
( |' ?; a7 ]  F; q# K% a3 T8 m
让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
* c- r/ P/ K3 g& X8 j
" E3 |- g: q! G9 F/ v* o另 n + 1 = k - n k = 2n + 1
) J4 _% q7 ]6 O# G那么x + 1可以控制的最范围就是[1, 3n + 1]3 B% G7 y- \! H

: b$ p% {5 [; N& U2 S, W3 u& \& C+ S- n2 y8 n. i

. X3 i9 c* W- m. S$ m6 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-8 04:18 , Processed in 0.291688 second(s), 50 queries .

回顶部