当前位置：网站首页>题目 2612: 蓝桥杯2021年第十二届省赛真题-最少砝码（枚举找规律+递推）

题目 2612: 蓝桥杯2021年第十二届省赛真题-最少砝码（枚举找规律+递推）

2022-07-01 12:36:00 【51CTO】

文章目录

Question
Ideas
Code

Question

       
       题目描述
       
       你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 
       
       N 
       
       的正整数重量。那么这套砝码最少需要包含多少个砝码？
       
       注意砝码可以放在天平两边。
       
       输入
       
       输入包含一个正整数 
       
       N。
       
       输出
       
       输出一个整数代表答案。
       
       样例输入
       
       7
       
       样例输出
       
       3
       
       提示
       
       【样例说明】
       
       3 
       
       个砝码重量是 
       
       1
       
       、4、6，可以称出 
       
       1 
       
       至 
       
       7 
       
       的所有重量。
       
       1 
       
       = 
       
       1
       
       ；
       
       2 
       
       = 
       
       6 
       
       4 (
       
       天平一边放 
       
       6
       
       ，另一边放 
       
       4)
       
       ；
       
       3 
       
       = 
       
       4 
       
       1
       
       ；
       
       4 
       
       = 
       
       4
       
       ；
       
       5 
       
       = 
       
       6 
       
       1
       
       ；
       
       6 
       
       = 
       
       6
       
       ；
       
       7 
       
       = 
       
       1 
       
       + 
       
       6
       
       ；
       
       少于 
       
       3 
       
       个砝码不可能称出 
       
       1 
       
       至 
       
       7 
       
       的所有重量。
       
       【评测用例规模与约定】
       
       对于所有评测用例，1 
       
       ≤ 
       
       N 
       
       ≤ 
       
       1000000000
       
       。
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.

Ideas

一开始想的是二分
后来发现不知道如何判断是否能表达1-n的数
就开始打表找规律发现第i个砝码能表示的最大数是第i-1个砝码能表示的最大数的三倍+1 递推即可

Code

       
       def 
       
       f(
       
       n):
       
       '''
       
        n>=2 f(n)代表砝码数为n的时候最大能表示的数 f(1) = 1 # 递推
       
        称1 需要1个砝码 砝码重量1
       
        称2 需要2个砝码 砝码重量1 2
       
        称3 需要2个砝码 砝码重量1 2
       
        称4 需要2个砝码 砝码重量1 3
       
        称5 需要3个砝码 砝码重量1 2 3
       
        称6 需要3个砝码 砝码重量1 2 3
       
        称7 需要3个砝码 砝码重量1 3 6
       
        称8 需要3个砝码 砝码重量1 5 7
       
        称9 需要3个砝码 砝码重量1 3 8
       
        称10 需要3个砝码 砝码重量1 3 8
       
        称11 需要3个砝码 砝码重量1 3 8
       
        称12 需要3个砝码 砝码重量1 3 8
       
        称13 需要3个砝码 砝码重量1 3 9
       
        '''
       
       if 
       
       n 
       
       == 
       
       1:
       
       return 
       
       1
       
       return 
       
       f(
       
       n
       
       -
       
       1) 
       
       * 
       
       3 
       
       + 
       
       1
       
       while 
       
       True:
       
       try:
       
       n 
       
       = 
       
       int(
       
       input())
       
       res 
       
       = 
       
       1
       
       while 
       
       f(
       
       res) 
       
       < 
       
       n:
       
       res 
       
       += 
       
       1
       
       print(
       
       res)
       
       except:
       
       break
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.