数学建模社区-数学中国

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

---

作者: 2744557306    时间: 2024-3-29 16:40
标题: 最少砝码 Java解决
问题描述】
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
$ s/ V7 ?7 N) k% ]6 l. X" P注意砝码可以放在天平两边。
3 f0 n( @  j1 v! P/ P; Q# x
* ?0 N1 w& F0 A! i【输入格式】
+ i6 ]9 ]2 p, i6 W; ^3 I' ~输入包含一个正整数 N。
) v. V* O3 D: A. j# B$ T8 v
【输出格式】
! ~* U, O4 S5 Y9 U5 t7 y  X输出一个整数代表答案。
- F% S! Y( b. s+ i3 H7 c
【样例输入】
; x2 I7 W% `, R% k: i! U! o7
* [# [6 n# X/ d
【样例输出】
% v/ \6 t% j3 R2 G3
4 T% r4 r2 ~9 ]% C2 t
5 u" o. Z; W' \【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
0 I7 n0 W; y% L$ E, J3 w' s4 = 4；
5 = 6 − 1；
6 = 6；
7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   ! N6 b4 t$ Z. I/ F
2. public class Main {  
   
3.     public static void main(String[] args) {  
   + K8 w. M5 z; ~
4.         int n = new Scanner(System.in).nextInt();   
   - K% q( f4 T* Q" H
5.         int maxWeight = 1, minCnt = 1;  
   
6.         while (maxWeight < n) {  
   
7.             maxWeight = maxWeight * 3 + 1;  
   
8.             minCnt++;  
   " v: v$ U8 W. A2 `2 E" y
9.         }  
   5 @6 G; f1 L* V) o
10.         System.out.println(minCnt);  
    + ?( H. u, ^) @& P" n' B9 U0 z
11.     }  
    - z  v2 t8 ~) q9 m* {. n0 v
12. }
    

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
8 C+ _' \- o4 y: K& k此时我们想扩大区间范围就只可以增加砝码
7 c; N$ g& V5 ^6 w# q) f假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
9 ]6 V, }4 O, P2 c: z. O1 \1 }
让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
8 x( _. f. s! h) K: K
另 n + 1 = k - n k = 2n + 1
那么x + 1可以控制的最范围就是[1, 3n + 1]

8 c% N: r2 ^0 G4 a( g% e8 n' \

: D! W4 @, l5 K! ?

---

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

Powered by Discuz! X2.5