美妙的acm

记录acm历程

DFS(交的时候有点问题)


DFS

Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1228    Accepted Submission(s): 724

Problem Description
A DFS(digital factorial sum) number is found by summing the factorial of every digit of a positive integer.

For example ,consider the positive integer 145 = 1!+4!+5!, so it's a DFS number.

Now you should find out all the DFS numbers in the range of int( [1, 2147483647] ).

There is no input for this problem. Output all the DFS numbers in increasing order. The first 2 lines of the output are shown below.
 

Input
no input
 

Output
Output all the DFS number in increasing order.
 

Sample Output
						
1
2
......

 1 // 打表的代码，就是将范围之内的全部举出来即可以
 2 /*
 3 #include<iostream>
  4 #define MAX 5
  5 using namespace std;
  6 int data[MAX];
  7 int main()
  8 {
  9 data[0]=1;
 10 data[1]=2;
 11 data[2]=145;
 12 data[3]=40585;
 13 int i;
 14 for(i=0;i<=3;i++)
 15 cout<<data[i]<<endl;
 16 return 0;
 17 } */
18
19 #include < iostream >
20 using   namespace  std;
 21 int  f[ 11 ];
 22 void  dfs( int  n) // 深搜,判断n是否是DFS数
23 {
 24      // 拿到一个数将要把它的每一位得到,从个位开始
25      int  sum = 0 ,x = n; // 要保留住n
26      while (x)
 27      {
 28         sum += f[x % 10 ]; // 得到每一位直接求得阶层
29         x /= 10 ;
 30     }
31      if (sum == n) // 如果每一位的阶层之和和n相同则return true;
32      {
 33         cout << n << endl;
 34     }     
 35 }
36 int  main()
 37 {
 38     memset(f, 0 , sizeof (f)); // 初始化
39      int  i;
 40     f[ 0 ] = 1 ;
 41      for (i = 1 ;i <= 10 ;i ++ ) // 得到个位的阶层
42         f[i] = i * f[i - 1 ];
 43      for (i = 1 ;i <= 2147483647 ;i ++ )
 44         dfs(i);    
 45      return   0 ;
 46 }

posted on 2010-07-18 23:59 wei 阅读(234) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


My Links

留言簿

随笔档案

最新随笔

搜索

最新评论