网站建设中公司_营销网站制作平台有哪些_电商运营推广是做什么的_常州seo招聘

一、问题描述

这是一道有趣的算法题，来源于计算机内存存储限制的灵感。题目描述如下：

在某一天，Hexadecimal的内存发生了严重问题，导致她只能读取二进制数字，也就是只能由数字 0 和 1 组成的数字。
如果一个数字在其十进制表示中包含其他字符（如 2-9），则这个数字无法被加载到内存中。

举个例子：

对于 n = 10，从 1 到 10 中，只有 1 和 10 是合法的二进制数字。
对于 n = 20，从 1 到 20 中，合法的数字为 1、10 和 11，一共 3 个。

Hexadecimal 的任务是：给定一个整数 n，从 1 到 n 的数字中，统计有多少个数字可以成功加载到内存中。

二、输入输出格式

输入格式：

一个正整数 n，满足条件：
1 ≤ n ≤ 10^9

输出格式：

输出一个整数，表示从 1 到 n 中可以被加载到内存的数字个数。

三、示例

输入：

输出：

解释： 从 1 到 10 中：

1 和 10 是有效的二进制数字。
其他数字如 2、3、4 等因为包含非二进制字符而被排除。

四、解题思路详解

要解决这个问题，我们需要理解几个关键点：

二进制数字的定义：
题目中提到的“二进制数字”并不是指数字在二进制系统中的表示，而是数字在十进制表示中只能包含字符 0 和 1。
例如：
- 10 是合法的，因为它只包含 0 和 1。
- 2 是非法的，因为它包含 2。
暴力法的不可行性：
对于 n 的最大值为 10^9，我们不可能直接从 1 遍历到 n 并逐一判断是否满足条件，这样会导致程序运行时间过长。
更高效的解决方案：
- 遍历数字的所有可能的组合，而不是依次检查所有数字。
- 可以通过递归构造所有符合条件的“二进制数字”，避免生成不合法的数字。

五、Python代码实现

下面是基于递归的高效解决方案。

1. 主代码实现

def count_binary_numbers(n):"""统计从 1 到 n 中的合法二进制数字个数"""def generate_binary_numbers(current):"""递归生成合法的二进制数字"""nonlocal count# 如果当前数字超出范围，停止递归if current > n:return# 如果当前数字合法且大于 0，计入统计if current != 0:count += 1# 递归生成下一位的二进制数字generate_binary_numbers(current * 10 + 0)  # 添加数字 0generate_binary_numbers(current * 10 + 1)  # 添加数字 1# 初始化计数变量count = 0# 从数字 0 开始递归生成generate_binary_numbers(0)return countif __name__ == "__main__":# 输入范围n = int(input("请输入数字 n："))# 调用函数并输出结果result = count_binary_numbers(n)print("合法的二进制数字个数为：", result)

2. 核心算法分析

递归函数 generate_binary_numbers：

递归终止条件：
- 如果当前数字 current > n，停止递归，返回上一级。
计数条件：
- 如果当前数字合法（current != 0），将其计入结果。
递归逻辑：
- 每次递归调用时，在当前数字的末尾分别添加 0 和 1，生成新的合法二进制数字。

六、代码运行详解

以 n = 10 为例：

初始调用：
- 从数字 0 开始，分别递归生成：
  - 0 * 10 + 0 = 0
  - 0 * 10 + 1 = 1
第二层递归：
- 对于数字 1，递归生成：
  - 1 * 10 + 0 = 10
  - 1 * 10 + 1 = 11
终止条件：
- 当递归生成的数字超过 10（即 current > n）时，停止递归。

最终生成的合法数字为：1 和 10，因此输出结果为 2。

七、优化思路

1. 使用 BFS（广度优先搜索）

递归是基于 DFS（深度优先搜索）实现的，但也可以使用 BFS 来构造合法的二进制数字队列，从而避免递归深度过深的问题。

from collections import dequedef count_binary_numbers_bfs(n):"""使用 BFS 统计合法二进制数字的个数"""queue = deque([1])  # 初始队列，包含数字 1count = 0while queue:current = queue.popleft()if current > n:continuecount += 1# 将当前数字的下一位加入队列queue.append(current * 10 + 0)queue.append(current * 10 + 1)return countif __name__ == "__main__":n = int(input("请输入数字 n："))result = count_binary_numbers_bfs(n)print("合法的二进制数字个数为：", result)

2. 复杂度分析

时间复杂度：
由于二进制树的高度与数字范围相关，递归或 BFS 的时间复杂度约为 O(log(n))，远低于暴力枚举的 O(n)。
空间复杂度：
递归深度和队列存储的最大节点数均为 O(log(n))。

八、完整测试与结果分析

测试用例

输入 `n`	输出合法数量
10	2
20	3
100	6
1000	10
1000000	20

测试结果分析

测试通过，结果正确。
当输入范围较大时（如 n = 10^9），算法仍能快速得出结果。

九、总结

通过递归或 BFS，我们可以高效地解决这道题目：

充分利用了二进制数字的特性，避免了暴力枚举的低效方法。
在 Python 中，使用递归或队列结构均可快速生成符合条件的数字。
该方法适用于输入范围较大的问题，如 1 ≤ n ≤ 10^9。

本题的核心思想在于避免冗余计算，并通过二进制树的结构构造合法数字。希望本文对你解决类似问题有所帮助！