实验4-2-9 水仙花数

题目描述

如果一个三位数的各位数字的立方和等于该数本身，则称这个数为水仙花数。例如：$153$是一个水仙花数，因为$1^3+5^3+3^3=153$。

输入格式

无

输出格式

按升序输出所有的三位水仙花数，每个数一行。

样例输出

153
370
371
407

算法1

(暴力枚举) $O(n)$

枚举 $100$ 到 $999$ 之间的所有三位数，然后判断其是否为水仙花数，如果是则输出。

时间复杂度

最坏情况下需要枚举 $900$ 个数，时间复杂度为 $O(n)$。

空间复杂度

只需要常数个变量，空间复杂度为 $O(1)$。

C++ 代码

#include <iostream>
using namespace std;

int main() {
    for (int i = 100; i <= 999; i++) {
        int a = i / 100;        // 分离出百位
        int b = i / 10 % 10;    // 分离出十位
        int c = i % 10;         // 分离出个位
        if (a * a * a + b * b * b + c * c * c == i) {    // 判断是否为水仙花数
            cout << i << endl;  // 输出水仙花数
        }
    }
    return 0;
}

算法2

(暴力枚举优化) $O(n)$

在算法1的基础上，可以发现水仙花数的个位数字只可能是 $0,1,5,6$，因此在枚举的时候只需要枚举这几种情况即可。

时间复杂度

最坏情况下需要枚举 $400$ 个数，时间复杂度为 $O(n)$。

空间复杂度

只需要常数个变量，空间复杂度为 $O(1)$。

C++ 代码

#include <iostream>
using namespace std;

int main() {
    for (int i = 100; i <= 999; i++) {
        int c = i % 10;     // 分离出个位
        if (c != 0 && c != 1 && c != 5 && c != 6) continue;   // 判断个位是否合法
        int a = i / 100;        // 分离出百位
        int b = i / 10 % 10;    // 分离出十位
        if (a * a * a + b * b * b + c * c * c == i) {    // 判断是否为水仙花数
            cout << i << endl;  // 输出水仙花数
        }
    }
    return 0;
}