水仙花数

水仙花数 一个三位数abc如果满足abc = a^3 + b^3 + c^3 那么就把这个数叫做水仙花数。 如果一个N位数所有数码的N次方的和加起来等于这个数字本身，我们把这样的数叫做广义水仙花数， 容易看出来N = 3是广义水仙花数。 现在，我们的任务是，输入一个m (m < 7) ， 让你求出所有满足N = m的广义水仙花数。 3  (153 370 371 407) 5 

(54748 92727 93084)

题解：

利用深度优先搜索，求出M位数的广义水仙花数。下面程序利用深度优先搜索基本框架，递归的出结果。

#include <iostream> using namespace std; int m; //m位数含有的水仙花数 int Pow(int x,int n) //x的n次方 { int num=1; while(n--) { num=num*x; } return num; } void dfs(int deep,int curNum, int curSum) //DFS搜索水仙花数 { if(deep>m) { if(curNum==curSum) //满足条件水仙花数打印输出 { cout<<curNum<<" "; } } else { int start=(deep==1);//第一位不为0 for(int i=start;i<=9;i++) { dfs(deep+1,curNum*10+i,curSum+Pow(i,m)); } } } int main() { while(cin>>m) { dfs(1,0,0); } return 0; }