[b]实验题目[/b]：水仙花数
[b]题目简介[/b]：水仙花数是一个n(n>=3)位数字的数，它等于每个数字的n次幂的和。例如153是水仙花数（具有3位数字且等于），试编写一个程序，求小于999的另外三个水仙花数。（提示：完成程序后，讨论你的设计的程序的可扩充性。如果程序改为4位或5位的水仙花数。（提示：完成程序后，讨论你的程序的可扩充性。如果程序改为求4位或5位的水仙花数。你的程序需要修改很多地方吗？）
[b]需要解决问题[/b]：
1.考虑程序的可扩充性，应该做到让程序修改最少或不用修改能够求4位或5位的水仙花数。
2.如何分别得到一个数各个位上的数。
3.对各个位数的求幂。
4.判断是否是水仙花数。
5.当求的水仙花数较大时，程序求解很慢。
[b]问题解决[/b]：
1.可让用户输入一个数n（n代表数字的位数）。
2.可先用一个临时变量temp储存需要判断的数，对temp取模10得到个位上的数，然后使tmep /= 10，重复循环得到各个位上的数。
3.求幂运算可使用C++标准库cmath里面的pow函数，或者不知道有这个函数的可以自己用for循环实现一个。考虑到pow函数的第一个参数为浮点数，我们这里要求的是整数，还需要强制转换。这里我就自己写了一个。
4.只需简单地将各个位上的幂相加判断是否等于原数，是的话就输出，然后继续寻找下一个。
5.看下面算法优化。
[b]算法优化[/b]：
1.涉及到幂的运算，为优化时间，避免数据的重复计算，可开一个数组保存1到9的n次幂。
2.判断一个数是否是水仙花数需要拆解各个位上的数，如果反向思考，讲各个位上的数合起来，时间复杂度就会从O(10 ^ n)降为O(n ^ 10)。
3.对题目进行简单的分析，可以得出以下结论：
假设：为水仙花数
结论：除外其他的排列都不是水仙花数。
例如：假设123是水仙花数，那么213,312,321等等都不是水仙花数，稍微一想就能明白。
故本来需要搜索n!次的变为1次，时间大大减少。
[b]算法实现[/b]：
1.最主要生成0~9的n-可重组合，将组合表示为数组
2.将组合求幂取和得到x，将x拆分成各个位数用数组表示，如果表示x的数列与组合的数列相同，那么x就是水仙花数
测试数据： 测试结果：
① 3 time: 0ms
② 9 time: 40ms
③ 14 time: 680ms
④ 19 time: -1429ms(时间溢出了。。大概运行时间为6~7s)
C++代码如下：
#include <iostream>#include <cstring>#include <iomanip>#include <ctime>using namespace std;long long pow[10]; //保存从~9的n次幂int n;int b[10]; //记录~9的可重复组合void check(int n, int *b); //判断是否是水仙花数并输出void dfs(int, int); //生成~9的n-可重组合int main(void) { clock_t time1, time2; cout << "Please enter the digit --> "; cin >> n; int i, j; time1 = clock(); for (i = 0; i < 10; ++i) { //计算幂 pow[i] = i; for (j = 1; j < n; ++j) pow[i] *= i; } dfs(0, n); time2 = clock(); cout << "time: " << (time2 - time1) * 1000 / CLOCKS_PER_SEC << "ms" << endl; return 0;}void check(int n, int *b) { long long result = 0; //存放各位位数的幂的和 int i, cmp[10]; //cmp为result各个位上的组合 for (i = 0; i < 10; ++i) cmp[i] = 0; bool same = true; for (i = 0; i < 10; ++i) result += pow[i] * b[i]; long long temp = result; for (; temp > 0; temp /= 10) cmp[temp % 10]++; for (i = 0; i < 10; ++i) { if (cmp[i] != b[i]) { //如果cmp,b完全相等，则result为水仙花数 same = false; break; } } if (same) cout << result << endl;}void dfs(int num, int d){ //递归生成~9的n-可重组合 int i; if (num == 9) { b[9] = d; check(n, b); } else { for (i = d; i >= 0; i--) { b[num] = i; dfs(num+1, d-i); } }}
相关资源：汇编语言课程设计（水仙花数）
