题目描述：
水仙花数是指一个N位正整数（N>=3），它的每个位上的数字的N次幂之和等于它本身。例 如：153 = 1^3 + 5^3+ 3^3。
 本题要求编写程序,计算所有N位水仙花数。
输入格式：
输入在一行中给出一个正整数N（3<=N<=7）。
输出格式：
按递增顺序输出所有N位水仙花数，每个数字占一行。
输入样例：
3
输出样例：
153
370
371
407
算法分析：
本题是穷举法的典型应用。我们可以设置一个数组来存储每一位数字，然后采用深度优先搜索（类似穷举全排列的方法），组合出每一个n位数，然后判断其是否为水仙花数。我实现了递归和非递归两种算法，并对求幂的算法进行了优化。奇怪的是非递归算法竟然比递归算法还要慢，真是不得其解，还望大牛指点。
说明：
算法思想：穷举法，深度优先搜索
数据结构：数组。
时间复杂度： O(10^n);

#include<stdio.h>
#include<stdlib.h>
#include <time.h>

int Num[10] = {0};

void dfs(int top, int n);//回溯法求水仙花数 
int pow(int a, int n);//递归法求幂 
void DaffodilNumber(int n);//穷举法求水仙花数（非递归） 

int main(void)
{
    clock_t start, finish;  
       double  duration;  
       int i, n;
       
       scanf("%d", &n);
       start = clock(); 
       for (i=1; i<10; i++) //回溯法求水仙花数,最高位不能为0 
    {
        Num[0] = i;
        dfs(1, n);
    }
    finish = clock();  
       duration = (double)(finish - start) / CLOCKS_PER_SEC;  
       printf( "%f seconds\n", duration );  
    
       start = clock(); 
       DaffodilNumber(n);//穷举法求水仙花数（非递归） 
       finish = clock();  
       duration = (double)(finish - start) / CLOCKS_PER_SEC;  
       printf( "%f seconds\n", duration );  
    
    return 0;
}

void dfs(int top, int n)//回溯法求水仙花数 
{
    int i, s1, s2;
    
    if (top == n)
    {
        s1 = s2 = 0;
        for (i=0; i<n; i++)
        {
            s1 += pow(Num[i], n);
            s2 = s2 * 10 + Num[i];
        }
        if (s1 == s2)
        {
            for (i=0; i<n; i++)
                printf("%d", Num[i]);
            printf("\n");
        }
        return ;
    }
    
    for (i=0; i<10; i++)
    {
        Num[top] = i;
        dfs(top+1, n);
    }
}

int pow(int a, int n)//递归法求幂 
{
    int s;
    
    if (a == 0 || a == 1 || n == 1)
        return a;
    if (n == 0)
        return 1;
        
    s = pow(a, n/2);
        
    return (n%2 == 0) ? (s * s) : (s * s * a);
}

void DaffodilNumber(int n)//穷举法求水仙花数（非递归） 
{
    int i, j, top, s1, s2;
    
    for (i=1; i<10; i++)
    {
        Num[0] = i;
        Num[1] = -1;
        top = 1;
        while (top > 0)
        {
            if (top == n)
            {
                s1 = s2 = 0;
                for (j=0; j<n; j++)
                {
                    s1 += pow(Num[j], n);
                    s2 = s2 * 10 + Num[j];
                }
                if (s1 == s2)
                {
                    for (j=0; j<n; j++)
                        printf("%d", Num[j]);
                    printf("\n");
                }
                --top; //返回上一个数字 
            }
            else if (Num[top] < 9)
            {
                Num[top++]++;
                Num[top] = -1;
            }
            else
            {
                --top;
            }
        }
    }
}