蓝桥杯真题解析(穿越时空之门)

第一题

问题描述

随着2024年的钟声回荡，传说中的时空之门再次敞开。这扇门是一条神秘的通道，它连接着二进制和四进制两个不同的数码领域，等待着勇者们的探索。

在二进制的领域里，勇者的力量被转换成了力量数值的二进制表示中各数位之和。

在四进制的领域里，力量的转换规则相似，变成了力量数值的四进制表示中各数位之和。

穿越这扇时空之门的条件是严苛的：当且仅当勇者在二进制领域的力量等同于四进制领域的力量时，他才能够成功地穿越。

国王选定了小蓝作为领路人，带领着力量值从1到2024的勇者们踏上了这段探索未知的旅程。作为小蓝的助手，你的任务是帮助小蓝计算出，在这2024位勇者中，有多少人符合穿越时空之门的条件。

答案提交

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

分析这道题，只需要找到1-2024中2进制各位和同时等于4进制各位和的数字就可以

计算10进制数字的2进制步骤为：

  1. 除以2并记录余数：将十进制数除以2，记录余数。
  2. 更新被除数：将商作为新的被除数，重复步骤1，直到商为0。
  3. 读取余数：从最后一个余数开始，依次读取所有余数，这些余数将构成四进制数。

用python实现它:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def to_base2(n):  # n为输入的10进制数  
    if n == 0:  
        return "0"  
      
    fn = []  # 用于存储四进制数的各位数字（字符形式）  
  
    while n > 0:  # 当n大于0时，继续执行循环  
        remainder = n % 2  # 计算n除以2的余数  
        fn.append(str(remainder))  # 将余数转换为字符串并添加到列表中  
        n = n // 2  # 更新n为n整除2的商，用于下一次循环  
      
    fn.reverse()  # 反转列表，因为是从低位到高位添加的  
  
    ffn = ''.join(fn)  # 将列表中的字符串元素连接成一个完整的四进制数字符串  
    return ffn  
  
# 获取用户输入的十进制数，并转换为整数  
n = int(input('输入10进制数: '))  
# 调用函数进行转换，并打印结果  
jg = to_base2(n)  
print(f"转换2进制结果为{jg}")

计算10进制数字的4进制步骤为：

  1. 除以4并记录余数：将十进制数除以4，记录余数。
  2. 更新被除数：将商作为新的被除数，重复步骤1，直到商为0。
  3. 读取余数：从最后一个余数开始，依次读取所有余数，这些余数将构成四进制数。

python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def to_base4(n):  # n为输入的10进制数  
    if n == 0:  
        return "0"  
      
    fn = []  # 用于存储四进制数的各位数字（字符形式）  
  
    while n > 0:  # 当n大于0时，继续执行循环  
        remainder = n % 4  # 计算n除以4的余数  
        fn.append(str(remainder))  # 将余数转换为字符串并添加到列表中  
        n = n // 4  # 更新n为n整除4的商，用于下一次循环  
      
    fn.reverse()  # 反转列表，因为是从低位到高位添加的  
  
    ffn = ''.join(fn)  # 将列表中的字符串元素连接成一个完整的四进制数字符串  
    return ffn  
  
# 获取用户输入的十进制数，并转换为整数  
n = int(input('输入10进制数: '))  
# 调用函数进行转换，并打印结果  
jg = to_base4(n)  
print(f"转换4进制结果为{jg}")

到这里你发现没有，略微改动一下程序，我们就可以将10进制数字转换为任意进制

做这个题目需要知道1-2024中2进制和4进制各位数相等的数字，对此我整出了6总解决办法😎

1.直接转换：

  • 将每个数字分别转换为二进制和四进制表示。
  • 比较这两个表示是否相同（忽略前导零）。
  • 统计满足条件的数字个数。

这种方法直观但效率较低，因为它需要对每个数字进行两次转换和一次比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def digit_sum_binary(n):
    # 将数字转换为二进制字符串，并计算1的个数
    return bin(n).count('1')

def digit_sum_quaternary(n):
    # 将数字转换为四进制字符串，并计算各位数字的和
    quaternary = ""
    while n > 0:
        quaternary = str(n % 4) + quaternary
        n //= 4
    return sum(int(digit) for digit in quaternary)

count = 0
for i in range(1, 2025):
    if digit_sum_binary(i) == digit_sum_quaternary(i):
        count += 1

print(count)

性能分析

digit_sum_binary(n) 函数

  • 时间复杂度：
    • bin(n) 的时间复杂度是 O(log⁡n)O(logn)，因为将数字转换为二进制字符串需要处理其位数。
    • count('1') 的复杂度是 O(k)O(k)，其中 kk 是二进制字符串的长度。对于一个数字 nn，其二进制表示的长度约为 O(log⁡n)O(logn)。
    • 因此，整体时间复杂度为 O(log⁡n)O(logn)。
  • 空间复杂度：
    • bin(n) 返回一个字符串，空间复杂度是 O(log⁡n)O(logn)。
    • 整体空间复杂度为 O(log⁡n)O(logn)。

digit_sum_quaternary(n) 函数

  • 时间复杂度：
    • 在将数字转换为四进制时，循环每次除以4，直到 nn 变为0，因此循环的次数为 O(log⁡4n)O(log4n)，即 O(log⁡n)O(logn)。
    • 构建四进制字符串的时间是 O(log⁡n)O(logn)（因为字符串拼接的时间）。
    • sum(int(digit) for digit in quaternary) 的时间复杂度是 O(k)O(k)，其中 kk 是四进制字符串的长度，大约也是 O(log⁡n)O(logn)。
    • 因此，整体时间复杂度为 O(log⁡n)O(logn)。
  • 空间复杂度：
    • 使用字符串 quaternary 存储四进制表示，空间复杂度是 O(log⁡n)O(logn)。
    • 整体空间复杂度为 O(log⁡n)O(logn)。

主循环

  • 时间复杂度：
    • 循环从1到2024，循环次数是常数 O(1)O(1)。
    • 在每次循环中，调用 digit_sum_binary(i) 和 digit_sum_quaternary(i)，它们的时间复杂度都是 O(log⁡n)O(logn)，因此每次循环的复杂度是 O(log⁡n)O(logn)。
    • 整体循环的时间复杂度为 O(2024⋅log⁡n)O(2024⋅logn)，即 O(log⁡n)O(logn)（常数项可以忽略）。

2.基于规则筛选法(如前面详细解释的方法)：

  • 利用二进制和四进制之间的转换规则。
  • 检查二进制表示是否只包含00、01和10的组合，并且长度为偶数。
  • 直接根据这些条件筛选数字，无需显式转换。

这种方法效率相比上一个更高，因为它避免了不必要的转换操作。

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
# 使用规则筛选法改进查找从1到2024中二进制和四进制数位和相等的数字

def digit_sum_binary(n):
    # 计算二进制数位和
    return bin(n).count('1')

def digit_sum_quaternary(n):
    # 计算四进制数位和
    digit_sum = 0
    while n > 0:
        digit_sum += n % 4
        n //= 4
    return digit_sum

def find_matching_numbers(limit):
    # 利用规则筛选法减少不必要的计算
    count = 0
    for i in range(1, limit + 1):
        # 规则1：数位和不大于其数位数的最大可能和
        if digit_sum_binary(i) <= digit_sum_quaternary(i) * 2:
            if digit_sum_binary(i) == digit_sum_quaternary(i):
                count += 1
    return count

# 调用筛选算法计算结果
result = find_matching_numbers(2024)
print(result)

性能分析

时间复杂度

  • digit_sum_binary(n) 函数：
    • 使用 bin(n).count('1') 计算二进制数位和的时间复杂度为 O(log⁡n)O(logn)，因为二进制表示的位数与数字的对数成正比。
  • digit_sum_quaternary(n) 函数：
    • 在四进制表示中，每次循环中都将 n 除以 4，时间复杂度同样为 O(log⁡n)O(logn)。
  • find_matching_numbers(limit) 函数：
    • 循环遍历从 1 到 limit 的每个数字，外层循环运行 O(n)O(n)，内层的两个数位和计算都是 O(log⁡n)O(logn)。因此，整体时间复杂度为 O(nlog⁡n)O(nlogn)。

空间复杂度

  • 代码中的空间使用主要是局部变量（如 digit_sum 和循环变量 i），没有使用额外的数据结构，因此空间复杂度为 O(1)O(1)。

3.编程优化法(很多写法不做示例)：

  • 使用编程语言中的内置函数或库来简化转换和比较操作。
  • 利用编程语言的特性（如字符串处理、循环控制等）来优化算法。

这种方法依赖于编程技能和语言特性，但通常能够提供更高效、更灵活的解决方案。

4.使用并行计算🤓👆：

  • 使用并行计算法来解决这个问题，可以利用多核处理器的能力来同时处理多个任务，从而加速计算过程。在Python中，concurrent.futures模块提供了一个高级接口来异步执行调用，使用线程池或进程池。由于Python的全局解释器锁（GIL）在多线程中的限制，对于CPU密集型任务（如这里的位操作和条件检查），使用进程池通常比使用线程池更有效。
  • 由于数据量相对较小（1到2024），并行计算可能不是必要的，但在处理更大规模的数据时可能会很有用。将任务分割成多个子任务，在多个处理器或线程上并行执行，使用concurrent.futures.ProcessPoolExecutor来并行计算1到2024之间满足条件的数字数量：
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import concurrent.futures  
  
def binary_sum(n):  
    """计算一个数的二进制表示中各位之和"""  
    return sum(int(digit) for digit in bin(n)[2:])  
  
def quaternary_sum(n):  
    """计算一个数的四进制表示中各位之和"""  
    quaternary_sum = 0  
    while n > 0:  
        quaternary_sum += n % 4  
        n //= 4  
    return quaternary_sum  
  
def check_range(start, end):  
    """检查给定范围内的数是否满足二进制和四进制各位之和相等的条件"""  
    count = 0  
    for n in range(start, end + 1):  
        if binary_sum(n) == quaternary_sum(n):  
            count += 1  
    return count  
  
def main():  
    # 定义要检查的范围  
    start = 1  
    end = 2024  
      
    # 根据CPU核心数确定任务粒度  
    # 这里我们简单地使用4个核心作为示例，但实际应用中应该根据可用核心数动态调整  
    num_cores = 4  
    chunk_size = (end - start) // num_cores + 1  
      
    # 初始化计数器  
    total_count = 0  
      
    # 使用ThreadPoolExecutor进行并行计算  
    with concurrent.futures.ThreadPoolExecutor() as executor:  
        # 提交任务  
        futures = [executor.submit(check_range, start + i * chunk_size, start + (i + 1) * chunk_size - 1) for i in range(num_cores)]  
          
        # 等待任务完成并汇总结果  
        for future in concurrent.futures.as_completed(futures):  
            total_count += future.result()  
      
    # 输出结果  
    print(total_count)  
  
if __name__ == "__main__":  
    main()

性能分析

时间复杂度

  1. binary_sum 函数：
  • 该函数将整数 n 转换为二进制字符串，然后计算所有位的和。
    • 时间复杂度为 O(log2n)，因为需要遍历 n 的每一位二进制表示。
  1. quaternary_sum 函数：
  • 该函数通过循环将整数 n 不断除以 4 并累加余数来计算四进制表示中各位的和。
    • 时间复杂度为 O(log4n)，因为需要遍历 n 的每一位四进制表示。由于 log4n 是 log2n 的一半（以 2 为底的对数），可以简化为 O(log2n)。
  1. check_range 函数：
  • 该函数遍历从 start 到 end 的每个整数，对每个整数调用 binary_sum 和 quaternary_sum 函数。
    • 时间复杂度为 O((end−start+1)⋅log2n)，其中 n 是 end 范围内的最大值。

  1. 并行计算：

    • 使用了 ThreadPoolExecutor 来并行执行 check_range 函数，但并行化不会改变时间复杂度的本质。
  • 假设将任务均匀分成 num_cores 份，每份的时间复杂度仍然与单线程相同，但总时间可以缩短到 O(numcores(end−start+1)⋅log2n)（忽略线程调度和同步的开销）。

空间复杂度

  1. binary_sum 和 quaternary_sum 函数：

    • 这两个函数的空间复杂度都是 O(1)，因为它们只使用了有限的额外空间（用于存储局部变量和返回结果）。

  2. check_range 函数：

    • 该函数的空间复杂度也是 O(1)，因为它只使用了有限的额外空间来存储计数器 count。

  3. 并行计算：

    • 使用了 ThreadPoolExecutor 来管理线程，每个线程会调用 check_range 函数。
  • 由于每个线程都独立运行 check_range，所以总的空间复杂度是 O(numcores)，用于存储线程栈和相关的数据结构。但在实际应用中，这个开销通常可以忽略不计，因为 num_cores 是一个相对较小的常数。

5.暴力搜索法(虽然不推荐，但也是也行)：

  • 简单地遍历所有可能的数字，对每个数字进行转换和比较。

  • 虽然这种方法在大多数情况下效率很低，但在某些特殊情况下（如数据量非常小或没有其他更好的解法时）可能是可行的。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    def binary_sum(n):  
        """计算整数n的二进制表示中各位数之和"""  
        return sum(int(digit) for digit in bin(n)[2:])  
      
    def quaternary_sum(n):  
        """计算整数n的四进制表示中各位数之和"""  
        return sum(int(digit) for digit in oct(n)[2:].replace('6', '1').replace('7', '2'))
    def quaternary_sum_simple(n):  
        quaternary = ""  
        while n > 0:  
            quaternary = str(n % 4) + quaternary  
            n //= 4  
        return sum(int(digit) for digit in quaternary)  
      
    def count_valid_powers(max_value):  
        count = 0  
        for i in range(1, max_value + 1):  
            if binary_sum(i) == quaternary_sum_simple(i):  
                count += 1  
        return count  
      
    # 计算并输出结果  
    result = count_valid_powers(2024)  
    print(result)  # 输出结果应为63

    性能分析

    binary_sum 函数性能：

    • 这个函数将整数转换为二进制字符串，然后遍历字符串中的每个字符（实际上是’0’和’1’），将它们转换为整数并求和。
    • 转换整数为二进制字符串的时间复杂度是 O(log₂n)，因为二进制表示的长度与整数的位数成正比。
    • 遍历字符串并求和的时间复杂度是 O(k)，其中 k 是二进制表示的长度，也是 O(log₂n)。
    • 因此，binary_sum 函数的整体时间复杂度是 O(log₂n)。

    quaternary_sum_simple 函数性能：

    • 这个函数通过不断取模和整除操作来构建整数的四进制表示，并同时计算各位数之和。
    • 取模和整除操作的时间复杂度都是 O(1)。
    • 由于需要执行这些操作直到整数变为0，因此总的操作次数与四进制表示的长度成正比，即 O(log₄n)。
    • 但由于对数底数的变化不会显著影响渐近时间复杂度（在整数范围内，所有对数函数都是彼此多项式相关的），我们可以认为这也是 O(log n) 的复杂度，尽管这里的 n 是以4为底的对数。
    • 因此，quaternary_sum_simple 函数的整体时间复杂度也是 O(log n)（这里的 n 仍然是指的输入整数的值）。

    主函数 count_valid_powers 性能：

    • 这个函数遍历从1到 max_value（在本例中为2024）的每个整数，并对每个整数调用 binary_sum 和 quaternary_sum_simple 函数。
    • 因此，主循环的时间复杂度是 O(max_value)。
    • 对于每个整数，调用 binary_sum 和 quaternary_sum_simple 的时间复杂度分别是 O(log n) 和 O(log n)（这里的 n 是循环中的当前整数）。
    • 由于 log n 在 n 的整个范围内都是相对较小的（特别是对于 n ≤ 2024），因此可以认为这部分的时间复杂度在整体上是次要的。
    • 因此，主函数 count_valid_powers 的整体时间复杂度是 O(max_value * log max_value)，但由于 log max_value 是一个相对较小的常数（对于 max_value = 2024），所以我们可以近似地认为它是 O(max_value)。