7-4 水仙花数

水仙花数是指一个N位正整数（N≥3），它的每个位上的数字的N次幂之和等于它本身。例如：153=1³+5³+3³。本题要求编写程序,计算所有N位水仙花数。

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

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

输入样例:

3

输出样例:

153
370
371
407

相信许多小伙伴第一眼看到这道题目就想到用循环嵌套了，然后调用一个C语言的次方函数pow()，代码如下：

#define _CRT_SECURE_NO_DEPRECATE 0
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main(){int n, m;scanf("%d", &n);for (int x = 0; x<=9; x++){for (int y = 0; y <= 9; y++){for (int z = 0; z <= 9; z++){for (int j = 0; j <= 9; j++){for (int i = 0; i <= 9; i++){for (int k = 0; k <= 9; k++){for (int h = 0; h <= 9; h++){if (n == 3 && i * 100 + k * 10 + h == pow((double)i, (double)n) + pow((double)k, (double)n) + pow((double)h, (double)n)){if ((i * 100 + k * 10 + h)>=100)printf("%d\n", i * 100 + k * 10 + h);}else if (n == 4 && j * 1000 + i * 100 + k * 10 + h == pow((double)j, (double)n) + pow((double)i, (double)n) + pow((double)k, (double)n) + pow((double)h, (double)n)){if ((j * 1000 + i * 100 + k * 10 + h)>=1000)printf("%d\n", j * 1000 + i * 100 + k * 10 + h);}else if (n == 5 && z * 10000 + j * 1000 + i * 100 + k * 10 + h == pow((double)z, (double)n) + pow((double)j, (double)n) + pow((double)i, (double)n) + pow((double)k, (double)n) + pow((double)h, (double)n)){if ((z * 10000 + j * 1000 + i * 100 + k * 10 + h)>=10000)printf("%d\n", z * 10000 + j * 1000 + i * 100 + k * 10 + h);}else if (n == 6 && y * 100000 + z * 10000 + j * 1000 + i * 100 + k * 10 + h == pow((double)y, (double)n) + pow((double)z, (double)n) + pow((double)j, (double)n) + pow((double)i, (double)n) + pow((double)k, (double)n) + pow((double)h, (double)n)){if ((y * 100000 + z * 10000 + j * 1000 + i * 100 + k * 10 + h)>=100000)printf("%d\n", y * 100000 + z * 10000 + j * 1000 + i * 100 + k * 10 + h);}else if (n == 7 && x * 1000000 + y * 100000 + z * 10000 + j * 1000 + i * 100 + k * 10 + h == pow((double)x, (double)n) + pow((double)y, (double)n) + pow((double)z, (double)n) + pow((double)j, (double)n) + pow((double)i, (double)n) + pow((double)k, (double)n) + pow((double)h, (double)n)){if ((x * 1000000 + y * 100000 + z * 10000 + j * 1000 + i * 100 + k * 10 + h)>=1000000)printf("%d\n", x * 1000000 + y * 100000 + z * 10000 + j * 1000 + i * 100 + k * 10 + h);}}}}if (n == 3){scanf("%d", &m);exit(0);}}if (n == 4){scanf("%d", &m);exit(0);}}if (n == 5){scanf("%d", &m);exit(0);}}if (n == 6){scanf("%d", &m);exit(0);}}system("pause");return 0;
}

结果就是，代码运行超时了…

然后，我又换了个思路，优化了一下代码，用一重循环来做，代码如下：

#define _CRT_SECURE_NO_DEPRECATE 0
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main(){int n, i = 0, j = 1;scanf("%d", &n);if (n == 3){i = 100;j = 999;}if (n == 4){i = 1000;j = 9999;}if (n == 5){i = 10000;j = 99999;}if (n == 6){i = 100000;j = 999999;}if (n == 7){i = 1000000;j = 9999999;}for (; i <= j; i++){if (n == 3 && i == pow((double)((i / 100) % 10),(double)(n)) + pow((double)((i / 10) % 10),(double)(n)) + pow((double)(i % 10),(double)(n))){printf("%d\n", i);}if (n == 4 && i == pow((double)((i / 1000) % 10),(double)(n)) + pow((double)((i / 100) % 10),(double)(n)) + pow((double)((i / 10) % 10),(double)(n)) + pow((double)(i % 10),(double)(n))){printf("%d\n", i);}if (n == 5 && i == pow((double)((i / 10000) % 10), (double)(n)) + pow((double)((i / 1000) % 10), (double)(n)) + pow((double)((i / 100) % 10), (double)(n)) + pow((double)((i / 10) % 10), (double)(n)) + pow((double)(i % 10), (double)(n))){printf("%d\n", i);}if (n == 6 && i == pow((double)((i / 100000) % 10), (double)(n)) + pow((double)((i / 10000) % 10), (double)(n)) + pow((double)((i / 1000) % 10), (double)(n)) + pow((double)((i / 100) % 10), (double)(n)) + pow((double)((i / 10) % 10), (double)(n)) + pow((double)(i % 10), (double)(n))){printf("%d\n", i);}if (n == 7 && i == pow((double)((i / 1000000) % 10), (double)(n)) + pow((double)((i / 100000) % 10), (double)(n)) + pow((double)((i / 10000) % 10), (double)(n)) + pow((double)((i / 1000) % 10), (double)(n)) + pow((double)((i / 100) % 10), (double)(n)) + pow((double)((i / 10) % 10), (double)(n)) + pow((double)(i % 10), (double)(n))){printf("%d\n", i);}}system("pause");return 0;
}

结果…还是超时
我一琢磨，这应该问题出在pow()这个次方函数上面，于是上网一查，发现这个函数的时间复杂度比我们直接用乘号更大，所以…我直接舍弃了pow()函数，直接用乘号计算次方。

#define _CRT_SECURE_NO_DEPRECATE 0
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main(){int n, i = 0, j = 1;scanf("%d", &n);if (n == 3){i = 100;j = 999;}if (n == 4){i = 1000;j = 9999;}if (n == 5){i = 10000;j = 99999;}if (n == 6){i = 100000;j = 999999;}if (n == 7){i = 1000000;j = 9999999;}for (; i <= j; i++){if (n == 3 && i == ((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10) + ((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10) + (i % 10)*(i % 10)*(i % 10)){printf("%d\n", i);}if (n == 4 && i == ((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10) + ((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10) + ((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10) + (i % 10)*(i % 10)*(i % 10)*(i % 10)){printf("%d\n", i);}if (n == 5 && i == ((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10) + ((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10) + ((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10) + ((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10) + (i % 10)*(i % 10)*(i % 10)*(i % 10)*(i % 10)){printf("%d\n", i);}if (n == 6 && i == ((i / 100000) % 10)*((i / 100000) % 10)*((i / 100000) % 10)*((i / 100000) % 10)*((i / 100000) % 10)*((i / 100000) % 10) + ((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10) + ((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10) + ((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10) + ((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10) + (i % 10)*(i % 10)*(i % 10)*(i % 10)*(i % 10)*(i % 10)){printf("%d\n", i);}if (n == 7 && i == ((i / 1000000) % 10)*((i / 1000000) % 10)*((i / 1000000) % 10)*((i / 1000000) % 10)*((i / 1000000) % 10)*((i / 1000000) % 10)*((i / 1000000) % 10) + ((i / 100000) % 10)*((i / 100000) % 10)*((i / 100000) % 10)*((i / 100000) % 10)*((i / 100000) % 10)*((i / 100000) % 10)*((i / 100000) % 10) + ((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10)*((i / 10000) % 10) + ((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10)*((i / 1000) % 10) + ((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10)*((i / 100) % 10) + ((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10)*((i / 10) % 10) + (i % 10)*(i % 10)*(i % 10)*(i % 10)*(i % 10)*(i % 10)*(i % 10)){printf("%d\n", i);}}system("pause");return 0;
}

虽然代码看起来很长，但是有效地减少了运行时间

注：其实用七重循环嵌套来做也是可以的通过的，只要你将pow()函数改成乘号。