数学建模社区-数学中国

标题: 最少砝码 Java解决 [打印本页]

---

作者: 2744557306    时间: 2024-3-29 16:40
标题: 最少砝码 Java解决
问题描述】
! F* m4 s! X& O4 B& Z1 \1 C! p你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
& x( O! e  h3 `$ }# W0 s+ q那么这套砝码最少需要包含多少个砝码？
' ~) s) c, q2 U' j, z1 d% B注意砝码可以放在天平两边。

【输入格式】
输入包含一个正整数 N。
0 m6 P( N, j/ g& u" u! E+ z
) R; O4 X: {: L6 i0 [【输出格式】
输出一个整数代表答案。
  \' l/ k- U2 ^* L7 \" w
9 j# f3 V' U. G( C' p【样例输入】
; i1 z: `0 m  `; Q" m5 \) g( j' J7

2 O* o$ a2 y- e- D% A【样例输出】
3
. j1 \! G/ z6 M0 H
【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
9 g) t, H8 v# w1 R  ?# Z. f+ e1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
5 = 6 − 1；
6 = 6；
7 t/ y. c! _! q2 j  K2 |7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   # r* f" I2 E) U+ E$ V% \4 W/ K
2. public class Main {  
   9 k/ b: R, x) l6 d: N/ }4 [0 T' w
3.     public static void main(String[] args) {  
   
4.         int n = new Scanner(System.in).nextInt();   
   / b3 D! @* T; L" @
5.         int maxWeight = 1, minCnt = 1;  
   
6.         while (maxWeight < n) {  
   / I0 E5 ^( |' X
7.             maxWeight = maxWeight * 3 + 1;  
   ( S5 [  @8 `5 i0 G3 T
8.             minCnt++;  
     x0 u$ n5 x5 Y; x$ k3 P
9.         }  
   
10.         System.out.println(minCnt);  
    ; {" w' w/ [6 n0 }! R
11.     }  
    * N. u) ~4 N7 H0 ^2 R! b
12. }
    - {$ ~- ]3 X/ Y# D9 O1 r( j

复制代码

题解
( t% D8 z% F# a如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
6 |% z, G: ?( g/ T7 i7 B因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

) _5 R9 H* G, e让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

另 n + 1 = k - n k = 2n + 1
  K# c7 H0 L4 S( A3 P5 G+ x5 n. V那么x + 1可以控制的最范围就是[1, 3n + 1]

+ o2 j5 L- ?/ L

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5