PAT 基礎編程 循環-11：水仙花數（Narcissistic Number）高效求解與算法優化全攻略

PAT 基礎編程 循環-11：水仙花數（Narcissistic Number）高效求解與算法優化全攻略

水仙花數是「位運算與數學性質結合」的經典算法題。PAT「循環-11」要求找出所有 N 位水仙花數（N≥3）。本文從定義建模、暴力枚舉、預計算優化、數學剪枝、多語言實現五個維度，提供完整解題體系。

數學定義精準建模

N 位十進制正整數 x，若滿足：

x = d_{N-1} d_{N-2} ... d_1 d_0
x = Σ_{i=0}^{N-1} (d_i)^N

則 x 為 N 位水仙花數。關鍵約束： N≥3，無前導零（即最高位 d_{N-1} ∈ [1,9]）。

已知水仙花數分佈（N≤7 完整表）

規律： 隨 N 增加，水仙花數極其稀疏，N=39 後不存在（證明基於 9^N * N < 10^{N-1}）。

方案一：標準暴力枚舉（教學基準，N≤6 可接受）

#include <stdio.h>
#include <math.h>

int N;

int is_narcissistic(int x) {
    int original = x;
    int sum = 0;
    while (x > 0) {
        int digit = x % 10;
        sum += (int)pow(digit, N);  // pow 返回 double，需轉換
        x /= 10;
    }
    return sum == original;
}

int main() {
    scanf("%d", &N);
    
    int start = (int)pow(10, N-1);
    int end = (int)pow(10, N);
    
    for (int i = start; i < end; i++) {
        if (is_narcissistic(i)) {
            printf("%d\n", i);
        }
    }
    return 0;
}

方案二：預計算冪值表優化（消除重複 pow 調用，關鍵加速）

#include <stdio.h>
#include <math.h>

int N;
int pow_table[10];  // 0^N ~ 9^N

int is_narcissistic_fast(int x) {
    int original = x;
    int sum = 0;
    while (x > 0) {
        sum += pow_table[x % 10];
        x /= 10;
    }
    return sum == original;
}

int main() {
    scanf("%d", &N);
    
    // 預計算 0~9 的 N 次冪
    for (int d = 0; d <= 9; d++) {
        pow_table[d] = (int)pow(d, N);
    }
    
    int start = 1;
    for (int i = 1; i < N; i++) start *= 10;  // 10^(N-1) 整數運算
    int end = start * 10;                     // 10^N
    
    for (int i = start; i < end; i++) {
        if (is_narcissistic_fast(i)) {
            printf("%d\n", i);
        }
    }
    return 0;
}

性能提升： 將 pow() 從內層循環（每數字調用 N 次）提升到預計算階段（僅 10 次），N=7 時速度提升 ~100 倍。

方案三：數學剪枝 + 組合生成（理論最優，實現複雜）

利用 數字多重集合 性質：水仙花數只取決於數字組成，不取決於排列順序。

1. 生成所有 10 進制數字的 N 元多重組合（非遞減序列）
2. 計算該組合的冪和 S
3. 檢查 S 的數字組成是否與原組合一致
4. 若一致，輸出 S 的所有排列（去重）

搜索空間從 9×10^{N-1} 降為 C(N+9, 9)，N=7 時從 900萬降至 11440，指數級剪枝。

三重循環專用解法（N=3 專用，極簡）

#include <stdio.h>

int main() {
    for (int i = 1; i <= 9; i++) {       // 百位 1-9
        for (int j = 0; j <= 9; j++) {   // 十位 0-9
            for (int k = 0; k <= 9; k++) { // 個位 0-9
                int num = 100*i + 10*j + k;
                int sum = i*i*i + j*j*j + k*k*k;
                if (num == sum) {
                    printf("%d\n", num);
                }
            }
        }
    }
    return 0;
}

Java 版本實現要點

import java.util.Scanner;

public class Narcissistic {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        
        int[] pow = new int[10];
        for (int d = 0; d <= 9; d++) {
            pow[d] = (int)Math.pow(d, N);
        }
        
        int start = 1;
        for (int i = 1; i < N; i++) start *= 10;
        int end = start * 10;
        
        for (int i = start; i < end; i++) {
            int sum = 0, x = i;
            while (x > 0) {
                sum += pow[x % 10];
                x /= 10;
            }
            if (sum == i) System.out.println(i);
        }
    }
}

常見錯誤避坑指南

複雜度對比總結

水仙花數問題展示了「預計算空間換時間」與「數學性質剪枝」兩大算法優化核心思想。對於 PAT 考試，預計算冪值表版本已足夠應對 N≤7 的測試數據；若挑戰更大 N，組合生成剪枝是理論最優路徑。建議動手實現預計算版並測量 N=7 耗時，體會數量級優化的快感。