Java 計算 100-999 之間所有水仙花數 (阿姆斯壯數) 完整實現

水仙花數，又稱 **阿姆斯壯數** 或 **自戀數**，是指一個 n 位數，其各位數字的 n 次冪之和等於該數本身。三位數水仙花數定義：

$$ abc = a^3 + b^3 + c^3 \quad (100 \le abc \le 999) $$

本文提供標準 Java 實現、數學優化版本、以及擴展至 n 位數的通用算法。

標準實現 (教學級)

public class NarcissisticNumber {
    public static void main(String[] args) {
        int count = 0;
        for (int i = 100; i < 1000; i++) {
            int units = i % 10;           // 個位
            int tens = (i / 10) % 10;     // 十位
            int hundreds = i / 100;       // 百位
            
            if (cube(units) + cube(tens) + cube(hundreds) == i) {
                System.out.println(i);
                count++;
            }
        }
        System.out.println("共有 " + count + " 個水仙花數");
    }
    
    private static int cube(int n) {
        return n * n * n;
    }
}

輸出結果：

153
370
371
407
共有 4 個水仙花數

數學優化版 (預計算立方表、避免重複運算)

public class OptimizedNarcissistic {
    private static final int[] CUBE = new int[10];
    static {
        for (int i = 0; i < 10; i++) CUBE[i] = i * i * i;
    }
    
    public static void main(String[] args) {
        int count = 0;
        for (int h = 1; h <= 9; h++) {       // 百位 1-9
            int h3 = CUBE[h];
            for (int t = 0; t <= 9; t++) {   // 十位 0-9
                int t3 = CUBE[t];
                for (int u = 0; u <= 9; u++) { // 個位 0-9
                    int sum = h3 + t3 + CUBE[u];
                    // 反向驗證：sum 的各位是否為 h,t,u
                    if (sum >= 100 && sum <= 999 &&
                        sum / 100 == h && (sum / 10) % 10 == t && sum % 10 == u) {
                        System.out.println(sum);
                        count++;
                    }
                }
            }
        }
        System.out.println("共 " + count + " 個");
    }
}

優化點： 僅 9×10×10 = 900 次迴圈 (同原版)，但立方運算預計算，邏輯改為「構造數字 → 驗證」，分支預測更友好。

通用 n 位數水仙花數查找器

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class GeneralNarcissisticFinder {
    
    public static List find(int digits) {
        if (digits < 1) throw new IllegalArgumentException("位數必須 >= 1");
        if (digits > 19) return findBig(digits); // 超過 long 範圍用 BigInteger
        
        List result = new ArrayList<>();
        int[] powers = new int[10];
        for (int i = 0; i < 10; i++) {
            powers[i] = (int) Math.pow(i, digits);
        }
        
        int start = (int) Math.pow(10, digits - 1);
        int end = (int) Math.pow(10, digits) - 1;
        
        for (int i = start; i <= end; i++) {
            int sum = 0;
            int n = i;
            while (n > 0) {
                sum += powers[n % 10];
                n /= 10;
            }
            if (sum == i) result.add(i);
        }
        return result;
    }
    
    private static List findBig(int digits) {
        // BigInteger 版本，略...
        return List.of();
    }
    
    public static void main(String[] args) {
        for (int d = 1; d <= 7; d++) {
            System.out.println(d + " 位數水仙花數: " + find(d));
        }
    }
}

已知水仙花數分佈 (OEIS A005188)：

教學延伸：相關數學概念

• 完全數： 真因子和等於自身 (6, 28, 496...)
• 親和數： 互為對方真因子和 (220, 284)
• 迴文數： 正讀反讀相同 (121, 1331)
• 卡邁克爾數： 費馬偽素數 (561, 1105...)

面試常見變體

1. 不使用乘法/冪運算： 利用 `n*n*n` 或查表
2. 遞歸實現： 位數拆解遞歸
3. 並行查找： `IntStream.range(100, 1000).parallel().filter(...)`
4. 時間複雜度分析： O(9×10^{n-1} × n)，指數級增長，故 n>7 需數學剪枝

水仙花數雖屬數學娛樂，但其「位數拆解、冪運算、邏輯驗證」的組合，完美涵蓋了**整數拆解、查表優化、邊界處理、泛化設計**等核心程式設計技能，是新手進階的絕佳練習題。