当前位置：网站首页>Topic 2612: the real topic of the 12th provincial competition of the Blue Bridge Cup in 2021 - the least weight (enumerating and finding rules + recursion)

Topic 2612: the real topic of the 12th provincial competition of the Blue Bridge Cup in 2021 - the least weight (enumerating and finding rules + recursion)

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

Question

       
        Title Description 
       
        You have a balance . Now you have to design a set of weights , So that any weight less than or equal to... Can be weighed by using these weights  
       
       N 
       
        Positive integer weight of . How many weights should this set of weights contain at least ？
       
        Note that the weight can be placed on both sides of the balance .
       
        Input 
       
        The input contains a positive integer  
       
       N.
       
        Output 
       
        Output an integer to represent the answer .
       
        The sample input 
       
       7
       
        Sample output 
       
       3
       
        Tips 
       
       【 Sample explanation 】
       
       3 
       
        The weight of a weight is  
       
       1
       
       、4、6, It can be said that  
       
       1 
       
        to  
       
       7 
       
        All the weight of .
       
       1 
       
       = 
       
       1
       
       ;
       
       2 
       
       = 
       
       6 
       
       4 (
       
        Put the balance aside  
       
       6
       
       , On the other side  
       
       4)
       
       ;
       
       3 
       
       = 
       
       4 
       
       1
       
       ;
       
       4 
       
       = 
       
       4
       
       ;
       
       5 
       
       = 
       
       6 
       
       1
       
       ;
       
       6 
       
       = 
       
       6
       
       ;
       
       7 
       
       = 
       
       1 
       
       + 
       
       6
       
       ;
       
        Less than  
       
       3 
       
        A weight cannot weigh  
       
       1 
       
        to  
       
       7 
       
        All the weight of .
       
       【 Evaluate use case size and conventions 】
       
        For all profiling use cases ,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

At first, I thought of two points
Later, I found that I didn't know how to judge whether I could express 1-n Number of numbers
Start typing your watch to find the rules Find the first i The maximum number that can be represented by a weight is i-1 Three times the maximum number that a weight can represent +1 Recursion

Code

       
       def 
       
       f(
       
       n):
       
       '''
       
        n>=2 f(n) The number of representative weights is n The maximum number that can be represented when  f(1) = 1 #  Recurrence 
       
         call 1  need 1 A weight   Weight of weight 1
       
         call 2  need 2 A weight   Weight of weight 1 2
       
         call 3  need 2 A weight   Weight of weight 1 2
       
         call 4  need 2 A weight   Weight of weight 1 3
       
         call 5  need 3 A weight   Weight of weight 1 2 3
       
         call 6  need 3 A weight   Weight of weight 1 2 3
       
         call 7  need 3 A weight   Weight of weight 1 3 6
       
         call 8  need 3 A weight   Weight of weight 1 5 7
       
         call 9  need 3 A weight   Weight of weight 1 3 8
       
         call 10  need 3 A weight   Weight of weight 1 3 8
       
         call 11  need 3 A weight   Weight of weight 1 3 8
       
         call 12  need 3 A weight   Weight of weight 1 3 8
       
         call 13  need 3 A weight   Weight of weight 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.