问题描述
随着2024年的钟声回荡,传说中的时空之门再次敞开。这扇门是一条神秘的通道,它连接着二进制和四进制两个不同的数码领域,等待着勇者们的探索。
在二进制的领域里,勇者的力量被转换成了力量数值的二进制表示中各数位之和。
在四进制的领域里,力量的转换规则相似,变成了力量数值的四进制表示中各数位之和。
穿越这扇时空之门的条件是严苛的:当且仅当勇者在二进制领域的力量等同于四进制领域的力量时,他才能够成功地穿越。
国王选定了小蓝作为领路人,带领着力量值从1到2024的勇者们踏上了这段探索未知的旅程。作为小蓝的助手,你的任务是帮助小蓝计算出,在这2024位勇者中,有多少人符合穿越时空之门的条件。
答案提交
这是一道结果填空题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
分析这道题,只需要找到1-2024中2进制各位和同时等于4进制各位和的数字就可以
计算10进制数字的2进制步骤为:
-
除以2并记录余数:将十进制数除以2,记录余数。
-
更新被除数:将商作为新的被除数,重复步骤1,直到商为0。
-
读取余数:从最后一个余数开始,依次读取所有余数,这些余数将构成四进制数。
用python实现它:
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进制步骤为:
-
除以4并记录余数:将十进制数除以4,记录余数。
-
更新被除数:将商作为新的被除数,重复步骤1,直到商为0。
-
读取余数:从最后一个余数开始,依次读取所有余数,这些余数将构成四进制数。
python:
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进制各位数相等的数字,对此我整出了5种解决办法😎
1.直接转换:
-
将每个数字分别转换为二进制和四进制表示。
-
比较这两个表示是否相同(忽略前导零)。
-
统计满足条件的数字个数。
这种方法直观但效率较低,因为它需要对每个数字进行两次转换和一次比较。
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(logn)O(logn),因为将数字转换为二进制字符串需要处理其位数。 -
count('1')
的复杂度是 O(k)O(k),其中 kk 是二进制字符串的长度。对于一个数字 nn,其二进制表示的长度约为 O(logn)O(logn)。 -
因此,整体时间复杂度为 O(logn)O(logn)。
-
-
空间复杂度:
-
bin(n)
返回一个字符串,空间复杂度是 O(logn)O(logn)。 -
整体空间复杂度为 O(logn)O(logn)。
-
digit_sum_quaternary(n)
函数
-
时间复杂度:
-
在将数字转换为四进制时,循环每次除以4,直到 nn 变为0,因此循环的次数为 O(log4n)O(log4n),即 O(logn)O(logn)。
-
构建四进制字符串的时间是 O(logn)O(logn)(因为字符串拼接的时间)。
-
sum(int(digit) for digit in quaternary)
的时间复杂度是 O(k)O(k),其中 kk 是四进制字符串的长度,大约也是 O(logn)O(logn)。 -
因此,整体时间复杂度为 O(logn)O(logn)。
-
-
空间复杂度:
-
使用字符串
quaternary
存储四进制表示,空间复杂度是 O(logn)O(logn)。 -
整体空间复杂度为 O(logn)O(logn)。
-
主循环
-
时间复杂度:
-
循环从1到2024,循环次数是常数 O(1)O(1)。
-
在每次循环中,调用
digit_sum_binary(i)
和digit_sum_quaternary(i)
,它们的时间复杂度都是 O(logn)O(logn),因此每次循环的复杂度是 O(logn)O(logn)。 -
整体循环的时间复杂度为 O(2024⋅logn)O(2024⋅logn),即 O(logn)O(logn)(常数项可以忽略)。
-
2.基于规则筛选法(如前面详细解释的方法):
-
利用二进制和四进制之间的转换规则。
-
检查二进制表示是否只包含
00
、01
和10
的组合,并且长度为偶数。 -
直接根据这些条件筛选数字,无需显式转换。
这种方法效率相比上一个更高,因为它避免了不必要的转换操作。
# 使用规则筛选法改进查找从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(logn)O(logn),因为二进制表示的位数与数字的对数成正比。
-
-
digit_sum_quaternary(n)
函数:-
在四进制表示中,每次循环中都将
n
除以 4,时间复杂度同样为 O(logn)O(logn)。
-
-
find_matching_numbers(limit)
函数:-
循环遍历从
1
到limit
的每个数字,外层循环运行 O(n)O(n),内层的两个数位和计算都是 O(logn)O(logn)。因此,整体时间复杂度为 O(nlogn)O(nlogn)。
-
空间复杂度
-
代码中的空间使用主要是局部变量(如
digit_sum
和循环变量i
),没有使用额外的数据结构,因此空间复杂度为 O(1)O(1)。
3.编程优化法(很多写法不做示例):
-
使用编程语言中的内置函数或库来简化转换和比较操作。
-
利用编程语言的特性(如字符串处理、循环控制等)来优化算法。
这种方法依赖于编程技能和语言特性,但通常能够提供更高效、更灵活的解决方案。
4.使用并行计算🤓👆:
-
使用并行计算法来解决这个问题,可以利用多核处理器的能力来同时处理多个任务,从而加速计算过程。在Python中,
concurrent.futures
模块提供了一个高级接口来异步执行调用,使用线程池或进程池。由于Python的全局解释器锁(GIL)在多线程中的限制,对于CPU密集型任务(如这里的位操作和条件检查),使用进程池通常比使用线程池更有效。 -
由于数据量相对较小(1到2024),并行计算可能不是必要的,但在处理更大规模的数据时可能会很有用。将任务分割成多个子任务,在多个处理器或线程上并行执行,使用
concurrent.futures.ProcessPoolExecutor
来并行计算1到2024之间满足条件的数字数量:
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()
性能分析
时间复杂度
binary_sum
函数:
-
该函数将整数
n
转换为二进制字符串,然后计算所有位的和。 -
时间复杂度为 O(log2n),因为需要遍历
n
的每一位二进制表示。
quaternary_sum
函数:
- 该函数通过循环将整数
n
不断除以 4 并累加余数来计算四进制表示中各位的和。 -
时间复杂度为 O(log4n),因为需要遍历
n
的每一位四进制表示。由于 log4n 是 log2n 的一半(以 2 为底的对数),可以简化为 O(log2n)。
check_range
函数:
-
该函数遍历从
start
到end
的每个整数,对每个整数调用binary_sum
和quaternary_sum
函数。 -
时间复杂度为 O((end−start+1)⋅log2n),其中 n 是
end
范围内的最大值。
并行计算:
-
使用了
ThreadPoolExecutor
来并行执行check_range
函数,但并行化不会改变时间复杂度的本质。 -
假设将任务均匀分成
num_cores
份,每份的时间复杂度仍然与单线程相同,但总时间可以缩短到 O(numcores(end−start+1)⋅log2n)(忽略线程调度和同步的开销)。
空间复杂度
binary_sum
和 quaternary_sum
函数:
-
这两个函数的空间复杂度都是 O(1),因为它们只使用了有限的额外空间(用于存储局部变量和返回结果)。
check_range
函数:
-
该函数的空间复杂度也是 O(1),因为它只使用了有限的额外空间来存储计数器
count
。
并行计算:
-
使用了
ThreadPoolExecutor
来管理线程,每个线程会调用check_range
函数。 -
由于每个线程都独立运行
check_range
,所以总的空间复杂度是 O(numcores),用于存储线程栈和相关的数据结构。但在实际应用中,这个开销通常可以忽略不计,因为num_cores
是一个相对较小的常数。
5.暴力搜索法(虽然不推荐,但也是也行):
-
简单地遍历所有可能的数字,对每个数字进行转换和比较。
-
虽然这种方法在大多数情况下效率很低,但在某些特殊情况下(如数据量非常小或没有其他更好的解法时)可能是可行的。
## 5.暴力搜索法(虽然不推荐,但也是也行): - 简单地遍历所有可能的数字,对每个数字进行转换和比较。 - 虽然这种方法在大多数情况下效率很低,但在某些特殊情况下(如数据量非常小或没有其他更好的解法时)可能是可行的。 ```python 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)。
性能分析
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)。
-