问题描述

水仙花数是指水仙花数是指一个N位正整数（ $3\leq N\leq 7$ ），它的每个位上的数字的N次幂之和等于它本身，例如：13+53+3^3=153。

输入格式:
输入在一行中给出一个正整数N（3≤N≤7）。

输出格式:
按递增顺序输出所有N位水仙花数，每个数字占一行

对`N=3`进行分析

#include <iostream>
using namespace std;
int main() {
	for(int i=100; i<1000 ; i++) {
		int a=i%10;
		int b=i/10%10;
		int c=i/100;
		if(a*a*a+b*b*b+c*c*c == i)
			cout<<i<<endl;
	}
  return 0;
}

分析：当N=3时，由于数值不大，且知道位数，在循环内部可直接求出其每个位上的数，可不用循环和math函数，这样只执行1000次。

对N( $3\leq N\leq 7$ )未知分析

分析：由于N未知，且 $3\leq N\leq 7$ ，继续采取上面的方法很繁杂，这时我想当然的再利用一个循环将其各个位数的值求出来，对其相加（由于N未知，就立马想到用pow()函数）代码如下(运行超时)：

#include<iostream>
#include<cmath>
using namespace std;
int main() {
    int n;
    scanf("%d",&n);
	for(int i=pow(10,n-1) ;i<pow(10,n) ; i++) {
        int b,t=0;
        b=i;
        while(b) {
        t+=pow(b%10,n);
            b/=10;
        }
        if(i == t)
        	printf("%d\n",i);
    }
    return 0;
}

分析：
这时问题就来了，N=7这个测试点显示运行超时，网上给的答案是频繁调用pow()函数。
解决方案：自定义一个power()函数(*只进行整数的次方运算*)来代替Pow()函数的功能。

原因： pow()函数原型double pow(double x,double y);
故它要处理的不只是关于整数次的次方也有可能是0.5等小数次的次方，所以它在运算时会考虑很多的情况，从而运算超时。并且当N=7时，需要调用pow函数的次数 $T>7\times10^6+2$ ，运算量比N=3大多了。

故优化后的AC代码如下：

#include<iostream>
#include<cmath>
using namespace std;
int power(int a,int b) {
	int s=1;
	for(int i=1 ;i<=b ; i++)
		s*=a;
	return s;
}
int main() {
    int n;
    scanf("%d",&n);
	for(int i=pow(10,n-1) ;i<pow(10,n) ; i++) {
        int  b,t=0;
        b=i;
        while(b) {
        t+=pow(b%10,n);
            b/=10;
        }
        if(i == t)
        	printf("%d\n",i);
    }
    return 0;
}

分析：这种方法虽然能够AC，但时间能达到500ms，效率不高，在网上又看到一种解法：利用数组来优化

终极解法(数组下标法)

核心代码如下：

for(int i=0 ; i<10 ; i++)
			num[i]=power(i,n);

分析：由于要将整数分解成单个的个位数，其范围是 $0\leq N\leq 9$ ，故不管怎么分解，都是这十个数之一。可以先将这是个数先进行次方运算，然后在进行循环遍历。

代码如下：

#include<iostream>
using namespace std;
int main()
{
	int power(int a,int n);
	int n;
	scanf("%d",&n);
	int num[10]={0};
	for(int i=0 ; i<10 ; i++)
			num[i]=power(i,n);
	for(int i=power(10,n-1) ; i<power(10,n) ;i++) {
		int b=i,sum=0;
		while(b) {
			sum+=num[b%10];  //将分解的数放至数组的下标，直接在数组中找出其对应的次方运算后的数
			b/=10;
		}
		if(i==sum)
			printf("%d\n",i);
	}
	return 0;
}

int power(int a,int n) {
	int s=1;
	for(int i=0 ; i<n ;i++)
		s*=a;
	return s;
}

N=7时的运算次数 T $10^6+2+10$ 效率又进一步的提升了，但测试时间仍要一百多毫秒。

将N=7单独分析的巧解

代码如下：

#include<iostream>
using namespace std;
int power(int a,int b) {
	int s=1;
	for(int i=1 ;i<=b ; i++)
		s*=a;
	return s;
}
int main() {
    int n;
    scanf("%d",&n);
    if(n == 7) {    //单独处理，时间更少
        printf("1741725\n");    
        printf("4210818\n");    
        printf("9800817\n");    
        printf("9926315\n");  
    }
    else{
        int num[10]={0};
		for(int i=0 ; i<10 ; i++)
			num[i]=power(i,n);
		for(int i=power(10,n-1) ; i<power(10,n) ;i++) {
			int b=i,sum=0;
			while(b) {
				sum+=num[b%10];
				b/=10;
			}
			if(i==sum)
				printf("%d\n",i);
		}  
    }
    return 0;
}