数学建模社区-数学中国

标题: 最少砝码 Java解决 [打印本页]
作者: 2744557306    时间: 2024-3-29 16:40
标题: 最少砝码 Java解决
问题描述】6 P1 d% g- S+ X" p! S0 E
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。, t* ?0 i2 h# J. E2 {
那么这套砝码最少需要包含多少个砝码？1 ]2 ~3 @2 y# U
注意砝码可以放在天平两边。+ v$ ^# _3 f) h) F* D( X6 O; f0 C

4 L- X% F; n7 K" n9 `0 t【输入格式】
+ T( N( O, ?# k8 z/ m) ]. B) `输入包含一个正整数 N。
. V- n8 _7 c6 W" t
" W: A, G. K4 [% O- D9 y. Q【输出格式】
& C+ m9 \9 [* {: K输出一个整数代表答案。; z1 G; ?- B4 i- E1 H7 ~

$ T. k2 D* N. Q/ h$ N【样例输入】$ K; ]& ]' E+ K  R
7
7 X# u' y+ o/ }6 ^0 B4 T$ i5 \' ]" e" S2 t9 q, i
【样例输出】+ L( \$ {2 s+ t- w  T
35 D! H  p; _$ \6 H; i  _5 w. S: m. h
" |: D: T- [3 B6 j, X8 U8 d# `2 z
【样例说明】
' e1 s8 Q! K) F( [$ A# i0 B3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。$ o3 z$ L  y# A
1 = 1；
" W! ~0 F$ M" c6 f/ m# J2 = 6 − 4 (天平一边放 6，另一边放 4)；3 f. I' |- O( t- r% _$ Q
3 = 4 − 1；
6 ?! p4 D! h/ _* L2 q9 E( C% \4 = 4；
& t$ E2 r% k: ]; |; @: o5 = 6 − 1；
9 W& o' ?+ k! g9 M6 = 6；: j" {% n) j/ S4 C  F) d
7 = 1 + 6；
6 x5 T* E; @6 a$ u4 \# N0 M少于 3 个砝码不可能称出 1 至 7 的所有重量。
  1. import java.util.Scanner;  0 g4 U& \( C# e0 b) c
  2. public class Main {  
    , \' L! J* j( h7 l7 T& F! H, v
  3.     public static void main(String[] args) {  ( K& U+ ~9 l. O
  4.         int n = new Scanner(System.in).nextInt();   
    # v. g% }; o. [
  5.         int maxWeight = 1, minCnt = 1;  " a" x& V) l& h. ]3 S0 M$ n
  6.         while (maxWeight < n) {  9 a& K" c. Q, ?) P
  7.             maxWeight = maxWeight * 3 + 1;  
    % L; Q3 Z& l, m2 \2 A' R
  8.             minCnt++;  1 N1 h7 `' r3 R& {
  9.         }  
    & J$ R" ^+ J3 G
  10.         System.out.println(minCnt);  . }& U# \, G: z8 N9 m5 y! w9 m
  11.     }  
    ( u4 G6 y- T6 j- I% L. F
  12. }
    , J& f5 |  ]# O& b6 r
复制代码
题解
* L% v% I- y* s9 j8 Y如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
/ Z* K- s0 d4 X% J8 v% r此时我们想扩大区间范围就只可以增加砝码
/ V; ]% V! k! y假设增加的砝码重量为 k
, n3 H4 W  [6 ^1 ]- U. b4 y因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
, j) N, Y+ H6 a" ^) `! b3 x所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了# W- R+ H( h' e

4 z) i3 H$ L: X* w: J让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围. A! F, [1 T# r# l
, g. w0 q: W) L7 x
另 n + 1 = k - n k = 2n + 1( f+ }6 F1 G$ F8 ^- z
那么x + 1可以控制的最范围就是[1, 3n + 1]" V; V; X4 m) \  q, ], u" K8 H0 o- n& b

. `$ @, |6 [1 Q# ?% t) e! n+ y
9 i# z6 m! q/ r) x1 d( P7 y: H* U, ~' k3 K1 O6 E: F! k( X




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5