水仙花數 (Narcissistic Number) C/C++ 實現大全

定義

水仙花數 (Narcissistic Number) 指一個 n 位數，其各位數字的 n 次冪之和等於該數本身。最經典的是三位數：abc = a³ + b³ + c³。三位數水仙花數只有四個：153、370、371、407。

方法一：三重循環暴力枚舉 (C 風格)

#include 

int main(void) {
    int a, b, c;
    for (a = 1; a <= 9; a++)          // 百位 1-9
        for (b = 0; b <= 9; b++)      // 十位 0-9
            for (c = 0; c <= 9; c++)  // 個位 0-9
                if (100*a + 10*b + c == a*a*a + b*b*b + c*c*c)
                    printf("%d%d%d ", a, b, c);
    return 0;
}

方法二：單循環分解數字 (C++ 風格)

#include 
using namespace std;

int main() {
    for (int n = 100; n < 1000; ++n) {
        int a = n / 100;         // 百位
        int b = (n % 100) / 10;  // 十位
        int c = n % 10;          // 個位
        if (n == a*a*a + b*b*b + c*c*c)
            cout << n << " 是水仙花數" << endl;
    }
    return 0;
}

泛化：N 位水仙花數

#include 
#include 

int is_narcissistic(int n) {
    int original = n, sum = 0, digits = 0;
    // 計算位數
    for (int t = n; t; t /= 10) digits++;
    // 計算各位 digits 次冪和
    for (int t = n; t; t /= 10) {
        int d = t % 10;
        int p = 1;
        for (int i = 0; i < digits; i++) p *= d; // 避免 pow 浮點誤差
        sum += p;
    }
    return sum == original;
}

int main() {
    for (int i = 1; i < 1000000; i++)
        if (is_narcissistic(i)) printf("%d ", i);
    // 輸出: 1 2 3 4 5 6 7 8 9 153 370 371 407 1634 8208 9474 54748 ...
    return 0;
}

性能優化技巧

• 預計算冪次表：pow10[d][k] 存儲 0-9 的 1-7 次冪，O(1) 查表。
• 避免浮點：整數乘法替代 pow()，消除精度誤差。
• 提前剪枝：最大 n 位數和為 n * 9^n，若 10^(n-1) > n * 9^n 則無解 (n≥61 時)。

總結

水仙花數是經典入門練習，展示了「數字分解」、「冪運算」、「枚舉優化」等基本編程技巧。三位數僅 4 個解，泛化後隨位數增長解極其稀疏 (OEIS A005188)。