QQ登录

只需要一步,快速开始

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

最少砝码 Java解决

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

1175

主题

4

听众

2833

积分

该用户从未签到

跳转到指定楼层
1#
发表于 2024-3-29 16:40 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
问题描述】3 s5 A' Z+ a/ Y% Y1 i. V
你有一架天平。现在你要设计一套砝码,使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
' y" A. Z" s# a' {9 E( }5 o那么这套砝码最少需要包含多少个砝码?
1 D. _8 c" z' |3 G& _注意砝码可以放在天平两边。5 e9 `/ {, K$ v1 A! U3 N; S1 M
( Z4 k/ N  p+ }% k4 {: {, d; N0 m
【输入格式】
6 ]! s0 i" ^& R; [% C* Y; f输入包含一个正整数 N。
* V* r# d! ]3 Y( M; v4 i0 {6 |8 w0 J" c& o! u+ p0 [1 S4 M% _
【输出格式】
' `/ N) A  w. u- e6 E输出一个整数代表答案。, n/ r+ R! @, j* d; j7 N

) j! e/ b' I: _7 Z6 o【样例输入】
( C6 h6 e, {$ M7$ j0 A3 z1 w: c7 `: O" m

. z  v2 h# ]) N【样例输出】
) ^) }: J* A6 g3  [: i, N6 |$ v5 Q. |, ?$ `
8 y8 ?1 ]% A! W+ m  _+ s
【样例说明】, S, |' d: R: i# b8 G7 P
3 个砝码重量是 1、4、6,可以称出 1 至 7 的所有重量。
$ f) M% ]. [7 Q' ]# u1 = 1;
1 f3 n- T/ K" x& e2 = 6 − 4 (天平一边放 6,另一边放 4);( o. i: R( [- x4 ?6 h
3 = 4 − 1;4 ]8 k' p- S# k5 n
4 = 4;
2 e2 n/ u1 ?+ S- p' @; t) O2 r, J4 e5 = 6 − 1;
! `' x7 e  t0 o6 = 6;
. a+ ?" L0 u- d1 f+ t# t7 = 1 + 6;+ y$ B5 q# N  i* _5 y
少于 3 个砝码不可能称出 1 至 7 的所有重量。
  1. import java.util.Scanner;  
      f  ?, k5 `, u+ o\" L. q7 D
  2. public class Main {  % G9 m, N1 Z# Y. q\" o7 j& b
  3.     public static void main(String[] args) {  
    & J* [$ L! @6 C0 L; Y' U
  4.         int n = new Scanner(System.in).nextInt();    ) J$ y! e# E  n8 w; B- \+ O# D, A) v
  5.         int maxWeight = 1, minCnt = 1;  
    ; b7 v8 t/ I/ J  ]4 u7 f
  6.         while (maxWeight < n) {  + n) R: U% C6 l, l  V6 y! ^
  7.             maxWeight = maxWeight * 3 + 1;  ) b% y/ Q  W9 h6 A
  8.             minCnt++;  
    * v1 E( n- O: i0 I9 G! F
  9.         }  \" D  j* v8 m+ [% s6 m+ J/ O
  10.         System.out.println(minCnt);  + G0 Z) Y2 ~& l/ `
  11.     }  
    * a. \3 o! [# R- d9 H
  12. }
    6 K( L2 o- K  P1 q
复制代码
题解8 w1 T+ Y+ o9 d+ j7 U; i, R
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
. m* W6 ^0 x2 E" V0 u此时我们想扩大区间范围就只可以增加砝码3 S. w; y& D; [
假设增加的砝码重量为 k( A( [+ y7 `5 Z
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作: o3 J) I/ H& m  K) w  w
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了0 Q0 _  L) i6 O" Y& s4 p: ]* i

! k& y& m  g5 x8 @& b让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围& e% c3 |3 H# k4 ]$ v1 X, {
$ O) m& ~/ V; @. p+ a# W
另 n + 1 = k - n k = 2n + 1
3 M( ^& m. q8 c9 L/ }3 }8 P那么x + 1可以控制的最范围就是[1, 3n + 1]
  _9 b! Z! e% r3 O/ k" [$ l
3 D8 w6 W8 u- b& t+ N
) w& D4 q$ b7 t8 y
* H+ N3 M( B: T: c
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-24 22:01 , Processed in 0.826346 second(s), 50 queries .

回顶部