C++ 中的自数

什么是自数？

自数在数学中是一种特殊的数字。它不能通过将一个数字与其数字之和相加来生成。换句话说，当您应用一个称为“生成器函数”的特定函数时，没有其他数字会产生它。

什么是生成器函数？

生成器 函数 的工作方式如下：

1. 取一个数字 n。
2. 将 n 加到其数字之和。

例如

• 对于 n=21，数字之和为 2+1=3。
• 生成器函数将返回 21+3=24。

因此，24 不是自数，因为 21 生成了它。

识别自数

如果不存在数字 n 使得生成器函数等于该数字，则该数字是自数。

例如

• 1, 3, 5, 7, 9 等是自数，因为没有其他数字可以通过生成器函数生成它们。

方法 1：简单方法

示例

输出

Self Numbers from 1 to 100 are:
1 3 5 7 9 20 31 42 53 64 75 86 97    

说明

步骤 1：理解目的

代码的目的是在 1 到 100 的范围内查找自数。自数是不能通过将另一个数字与其数字之和相加而创建的数字。例如，21 不是自数，因为它可以由 15 生成（15 + 1 + 5 = 21）。另一方面，1、3 和 5 是自数，因为没有其他数字可以生成它们。

步骤 2：生成器函数

生成器函数是一个简单的数学函数。它接受一个数字 n，将 n 加到其数字之和，并返回结果。

例如

• 如果 n=15，则数字为 1 和 5。相加得到 1+5=6。再加上 15 得到 15+6=21。因此，15 的生成器是 21。

此生成器函数有助于我们确定哪些数字不是自数，因为通过生成器函数创建的任何数字都不能是自数。

步骤 3：标记非自数

要查找自数，代码

• 最初假设所有数字都是自数。
• 在计算每个数字的生成器函数时，它会将结果数字标记为非自数。

这是使用一个称为 isSelfNumber 的数组（或列表）完成的。此数组跟踪一个数字是否为自数。

• 如果 isSelfNumber[x] 为 true，则表示 x 是自数。
• 如果 isSelfNumber[x] 为 false，则表示 x 不是自数，因为它是由某个其他数字生成的。

步骤 4：循环遍历数字

程序从 1 循环到 100。对于每个数字

• 它计算生成器结果。
• 如果结果在范围内（1 到 100），它会将 isSelfNumber 数组中的该数字标记为 false。

此标记可确保所有可以生成的数字都被识别为非自数。

步骤 5：查找自数

在标记完所有非自数之后，程序再次遍历 isSelfNumber 数组。任何仍标记为 true 的数字都将作为自数打印出来，因为没有其他数字生成它们。

示例演练

让我们通过一个例子来看看逻辑是如何工作的

1. 从数字 1 开始
   • 生成器函数：1+1=2。
   • 将 2 标记为非自数。
2. 移至数字 2
   • 生成器函数：2+2=4。
   • 将 4 标记为非自数。
3. 继续处理数字 3
   • 生成器函数：3+3=6。
   • 将 6 标记为非自数。
4. 处理完所有数字后
   • 像 1、3、5、7、9 等数字仍未被标记，因为没有其他数字生成它们。这些是自数。

步骤 6：输出结果

最后，程序打印 isSelfNumber 数组中所有仍标记为 true 的数字。这些数字是范围内的自数。

时间复杂度

外循环

• 遍历 1 到 n 的所有数字。这需要 O(n) 时间。

生成器函数

• 对于每个数字，都会计算其数字之和。
• 数字 i 大约有 O(log10(i)) 位数字，因此生成器函数需要 O(log(i)) 时间。

总时间复杂度

• 对于所有 n 个数字，总复杂度为：O(n⋅log(n))

空间复杂度

用于跟踪的数组

• 使用一个大小为 n+1 的布尔数组来跟踪自数。
• 这需要 O(n) 空间。

其他变量

• 一些临时 变量 用于计算，这需要 O(1) 空间。

总空间复杂度

• 由数组主导，因此是 O(n)。

方法 2：使用数学排除法

与其显式计算每个数字的生成器函数，不如通过迭代范围并标记生成的数字来直接识别非自数。这避免了对布尔数组的需求，并减少了冗余计算。

程序

输出

Self Numbers from 1 to 100 are:
1 3 5 7 9 20 31 42 53 64 75 86 97    

说明

步骤 1：代码目的

代码用于在范围内（在此情况下为 1 到 100）识别自数。自数是任何数字都无法通过其本身与其数字之和相加而生成的数字。例如

• 21 不是自数，因为它可以通过 15 生成（15 + 1 + 5 = 21）。
• 1、3、5 等是自数，因为没有其他数字可以生成它们。

步骤 2：生成器函数

生成器函数计算一个数字的“生成器”值。

对于给定的数字 n，它将 n 加到其数字之和。

例如

• 对于 n=15，数字为 1 和 5。相加得到 1+5=6，而 15+6=21。
• 因此，15 的生成器是 21。

此函数帮助我们识别哪些数字被生成，哪些没有。

步骤 3：存储生成的数字

代码使用集合（unordered_set）来代替使用大型数组来跟踪生成的数字。

• 使用集合是因为它只存储唯一值，因此没有重复。
• 在程序计算生成器时，它会将每个生成的数字添加到集合中。

例如

• 如果 n=15，则生成器为 21，因此 21 会被添加到集合中。
• 如果 n=20，则生成器为 22，因此 22 会被添加到集合中。

步骤 4：识别自数

将所有生成的数字存储在集合中后

程序遍历范围内的所有数字（1 到 100）。

对于每个数字

• 它会检查该数字是否不在集合中。
• 如果它不在集合中，则它是一个自数，并将被打印出来。

例如

• 像 1、3、5 等数字不在集合中，因为没有数字可以生成它们。
• 像 21、22 等数字在集合中，因此它们不是自数。

步骤 5：输出

程序打印范围中所有不在集合中的数字。这些是自数。

对于 1 到 100 的范围，输出为

• 1 3 5 7 9 20 31 42 53 64 75 86 97

此方法的优点

高效的内存使用

• 仅将生成的数字存储在集合中，因此与存储所有数字相比，内存使用量减少了。

更快的查找

• 检查数字是否存在于集合中非常快速且高效。

清晰的逻辑

• 使用集合通过直接关注生成的数字来简化过程，避免了不必要的数组操作。

复杂度分析

时间复杂度

生成器函数

• 计算数字的生成器需要 O(log(n)) 时间，因为它对数字求和。
• 这是针对从 1 到 LIMIT 的所有数字进行的，因此总时间为 O(LIMIT⋅log(LIMIT))。

检查自数

• 每个数字在集合中进行检查，每个数字需要 O(1) 时间。
• 对于 LIMIT 个数字，这会增加 O(LIMIT) 时间。

总时间复杂度： O(LIMIT⋅log(LIMIT))

空间复杂度

生成的数字存储

• unordered_set 最多存储 LIMIT 个数字，需要 O(LIMIT) 空间。

临时变量

• 用于循环和生成器变量，需要 O(1) 空间。

总空间复杂度： O(LIMIT)

方法 3：使用反向映射

此方法通过直接反转生成数字的过程来工作。与其计算哪些数字被生成，不如尝试“反转”范围内每个数字的生成器函数。它消除了使用集合或 数组 来跟踪生成的数字的需要，从而提高了内存效率。

程序

输出

Self Numbers from 1 to 100 are:
1 3 5 7 9 20 31 42 53 64 75 86 97    

说明

步骤 1：代码目的

目标是识别自数，即不能通过将一个数字与其数字之和相加而生成的数字。例如

• 21 不是自数，因为它可以通过 15 生成（15 + 1 + 5 = 21）。
• 1、3、5 等是自数，因为没有数字可以生成它们。

步骤 2：数字之和函数

代码的第一部分是一个辅助函数，用于计算数字的数字之和。例如

• 对于 n=15，数字为 1 和 5，因此它们的和为 1+5=6。
• 此函数用于帮助计算数字 x 是否可以生成另一个数字 n。

步骤 3：检查一个数字是否为自数

为了确定数字 n 是否为自数

• 程序会循环遍历所有小于 n 的数字 x。
• 对于每个 x，它计算 x + x 的数字之和。
• 如果此值等于 n，则表示 n 可以由 x 生成，因此 n 不是自数。
• 如果不存在这样的 x，则 n 是自数。

例如

对于 n=21

• x=15：15+(1+5)=21。因此，21 不是自数。

对于 n=3

• 不存在 x<3 生成 3。因此，3 是自数。

步骤 4：循环遍历范围

程序会遍历指定范围内的所有数字（在此情况下为 1 到 100）。

• 它使用上面解释的自数逻辑检查每个数字。
• 如果数字是自数，则打印它。

例如

• 像 1、3、5、7 这样的数字是自数，因为没有比它们小的数字生成它们。
• 像 21 和 42 这样的数字不是自数，因为它们是由其他数字生成的。

步骤 5：输出

• 输出是范围内所有自数的列表。对于 1 到 100 的范围，自数是
• 1 3 5 7 9 20 31 42 53 64 75 86 97

优点

C++ 中的自数具有以下几个优点

无额外内存

• 代码不使用数组或集合，因此节省了空间。

直接的逻辑

• 它通过反转生成过程直接遵循自数的定义。

易于理解

• 该方法清晰，并且对于 1 到 100 这样的小范围效果很好。

复杂度分析

时间复杂度

• 对于每个数字 n，它会检查所有小于 n 的数字 x，看 x 是否生成 n。
• 数字求和计算增加了少量开销。
• 总时间复杂度：O(LIMIT^2 ⋅log(LIMIT))。

空间复杂度

• 没有使用额外的 数据结构，只使用了一些变量。
• 总空间复杂度：O(1)。

性质

C++ 中的自数具有以下几个特性

唯一性

• 每个自数都是唯一的，因为没有比它小的数字可以生成它。
• 例如，3 是唯一的，因为不存在 x 使得 x+sumDigits(x)=3。

范围独立性

• 自数出现在所有数字范围内。
• 在任何有限范围内，总会有一些数字是自数。

自数的增长

• 随着数字的增加，连续自数之间的差距也在增大。
• 较大的数字更有可能被生成，因为它们的 x+sumDigits(x) 值更高。因此，自数变得不那么频繁。

无限计数

• 自数集是无限的。并非所有数字都可以表示为 x+sumDigits(x)，这意味着任何范围内总是存在自数。