【例4.15】水仙花数

GitHub跳转原题关系图返回列表

枚举 $100 \sim 999$ 中的每一个数,判断其各位数字立方和是否等于该数本身。

OJ: roj

题目 ID: 5031

难度:入门

标签:模拟枚举

创建: 2026-10-08 19:46

更新: 2026-10-08 19:46

形式化题目

无输入。 找到所有满足 100≤X≤999100 \le X \le 999 且 X=A3+B3+C3X = A^3 + B^3 + C^3 的整数 XX,其中 A,B,CA, B, C 分别为 XX 的百位、十位和个位数字。 按照由小到大的顺序输出这些数,每行输出一个。

正解

思路

因为需要找出的数的范围很小,只在三位数 100∼999100 \sim 999 之间,所以可以直接使用穷举(枚举)的方法。 具体步骤如下:

  1. 遍历范围设定:用一个循环从 100100 递增遍历到 999999。从 100100 开始是因为这是最小的三位数,到 999999 结束是因为这是最大的三位数,既不包含两位数,也不包含 10001000 这样的四位数。由于遍历的过程本身就是从小到大递增的,所以按此顺序找到的满足条件的数天然具有「由小到大输出」的性质,不需要将它们存起来再进行额外的排序。
  2. 数字分离与判断:对于当前的数 XX,我们可以定义一个辅助函数 is_narcissistic(X) 来判断它是否是水仙花数。提取一个三位数的各个数位主要有两种方式:
    • 算术方法:百位数字 A=X/100A = X / 100,十位数字 B=(X/10) mod 10B = (X / 10) \bmod 10,个位数字 C=X mod 10C = X \bmod 10。这种方法非常契合 C++ 的整数除法和取模运算特性,执行速度极快。提取数位后计算 A3+B3+C3A^3 + B^3 + C^3,若其等于 XX 则说明符合条件。需要注意计算立方时直接使用乘法(A * A * A)不仅更符合 C++ 的编程习惯,还能避免使用 pow 等浮点数函数可能带来的精度误差。
    • 字符串转换:将数字转换成字符串,再逐个字符转回整数。例如 Python 中可以写成 sum(int(d) ** 3 for d in str(x)) == x。这种写法在 Python 等高级语言中更为精简,虽然有较小的性能开销,但在本题 900900 次常数范围的枚举中可以忽略不计。
  3. 输出细节:如果 is_narcissistic(X) 返回 true,则输出该数并换行。需确保每个数占一行,并且输出结尾不要有多余空行。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 19:44
# update_at: 2026-10-08 19:44


def is_narcissistic(x: int) -> bool:
    """判断 x 是否为水仙花数:各位数字的立方和是否等于 x 本身。"""
    return sum(int(d) ** 3 for d in str(x)) == x


def solve() -> None:
    """本题无输入,枚举 100~999 并按由小到大输出所有水仙花数。"""
    # 从小到大遍历,输出天然有序;str 拆数位比 / 和 % 更短且不易写错。
    print('\n'.join(str(x) for x in range(100, 1000) if is_narcissistic(x)))


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 19:44
 * update_at: 2026-10-08 19:44
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 判断 x 是否为水仙花数:x 的百位、十位、个位数字的立方和是否等于 x 本身。
bool is_narcissistic(ll x) {
    ll hundred = x / 100;       // 百位数字 A
    ll ten = x / 10 % 10;       // 十位数字 B
    ll unit = x % 10;           // 个位数字 C
    return hundred * hundred * hundred + ten * ten * ten + unit * unit * unit == x;
}

void solve() {
    // 本题无输入:从 100 到 999 依次枚举,由小到大输出所有水仙花数。
    // 用整数乘法而不是 pow,避免浮点误差。
    for (ll x = 100; x <= 999; x++) {
        if (is_narcissistic(x)) {
            cout << x << "\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

复杂度

  • 时间复杂度:O(1)\mathcal{O}(1)(或者表示为 O(N)\mathcal{O}(N),其中 N=900N = 900 是需要枚举的数的个数)。因为枚举范围是固定的 100∼999100 \sim 999,每次提取数位和计算立方的操作都是常数时间的,因此总的时间复杂度为一个很小的常数级别,即 O(1)\mathcal{O}(1)。
  • 空间复杂度:O(1)\mathcal{O}(1),仅需常数级的额外变量存储数位、循环控制以及判定计算即可。

总结

这是一道非常经典且基础的枚举题目,主要考察如下几点:

  1. 枚举范围的确立:由于题意限制是求“所有三位数”,那么正确的遍历范围应为 100∼999100 \sim 999,排除了 100100 之下和 999999 之上的情况。
  2. 有序性天然达成:因为是从 100100 到 999999 按顺序遍历的,所以在寻找到答案后直接打印就是符合“由小到大输出”的要求,无需任何存储和排序。
  3. 数位的剥离:展示了分离数位的两套基本方法。在 C/C++ 中使用 / 和 % 是最经典且最稳妥的做法;在 Python 中则可以利用字符串特性的快捷写法 str(X) 处理。
  4. 格式与细节防错:输出结果需要注意“每个数占一行”以及末尾保证单一换行而无多余空行。计算整数次幂时避免使用 pow 也是 C++ 中绕过由于浮点误差导致不相等的一个重要习惯。