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
......

// 打表的代码，就是将范围之内的全部举出来即可以
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

#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 阅读(230) 评论(0) 编辑收藏引用

只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

美妙的acm

DFS(交的时候有点问题)

DFS

My Links

留言簿

随笔档案

最新随笔

搜索

最新评论