uva10591 Happy Number —

uva10591 Happy Number ——水题

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1532

题目大意：

　　给一个数字，各位数字的平方和相加，依次循环，如果最后得到1，那么这个数字就是happy number，如果不能，就是unhappy number。

思路：

　　因为题目范围只有10^9，所以可以暴力求解，数字的平方和最大是9*9*9=729，可以用一个数组标记这个数字是否被访问过。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cctype>
 6 #include <stack>
 7 #include <queue>
 8 #include <cmath>
 9 #include <algorithm>
10 #define lson l, m, rt<<1
11 #define rson m+1, r, rt<<1|1
12 using namespace std;
13 typedef long long int LL;
14 const int MAXN =  0x3f3f3f3f;
15 const int  MIN =  -0x3f3f3f3f;
16 const double eps = 1e-9;
17 const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
18   {1,1},{1,-1},{-1,-1}};
19 int visit[1000];
20 int solve(int n){
21   int m = 0;
22   while (n){
23     m += (n%10)*(n%10); n /= 10;
24   }
25   return m;
26 }
27 int main(void){
28 #ifndef ONLINE_JUDGE
29   freopen("uva10591.in", "r", stdin);
30 #endif
31   int t, n;
32   scanf("%d", &t);
33   for (int i = 1; i <= t; ++i){
34     scanf("%d", &n);int se = n; memset(visit, 0, sizeof(visit));
35     while (1){
36       n = solve(n);
37       if (visit[n]) {
38         printf("Case #%d: %d is an Unhappy number.\n",i,se);
39         break;
40       }
41       if (n == 1) {
42         printf("Case #%d: %d is a Happy number.\n",i,se); break;
43       }
44       visit[n] = 1;
45     }
46   }
47 
48   return 0;
49 }

本来是想做http://122.207.68.93/OnlineJudge/problem.php?cid=2031&pid=7 这道数位DP题目的，结果搜到了一道题目背景类似的题目，顺便做了，可惜是一道水题，数据范围太小。计算各位数字的平方和的时候，从低位向高位算，先对10取余，平方，然后把原来的数字除以10，循环。直到原来的数字为0为止。

看了一下别人的代码，有用map的，为了学习一下map，也写了一下~

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cctype>
 6 #include <stack>
 7 #include <set>
 8 #include <vector>
 9 #include <map>
10 #include <queue>
11 #include <cmath>
12 #include <algorithm>
13 #define lson l, m, rt<<1
14 #define rson m+1, r, rt<<1|1
15 using namespace std;
16 typedef long long int LL;
17 const int MAXN =  0x3f3f3f3f;
18 const int  MIN =  -0x3f3f3f3f;
19 const double eps = 1e-9;
20 const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
21   {1,1},{1,-1},{-1,-1}};
22 
23 int main(void){
24 #ifndef ONLINE_JUDGE
25   freopen("uva10591.in", "r", stdin);
26 #endif
27   int t; scanf("%d", &t);
28   map<int, bool> m; int n;
29   for (int i = 1; i <= t; ++i){
30     scanf("%d", &n);
31     m.clear();
32     printf("Case #%d: %d is",i, n);
33     m[n] = true;
34     while (1){
35       int sum = 0;
36       while (n){
37         sum += (n%10) * (n%10); n /= 10;
38       }
39       //下面两个if位置不能调换，要先判断是不是等于1，然后再
40       //判断这个值以前是不是用过，因为，当n == 1的时候，它
41       //从一开始就被标记了，如果把后面一个if放在前面，就错了
42       // 注意这种边界条件产生的逻辑错误
43       if (sum == 1){
44         printf(" a Happy number.\n");
45         break;
46       }
47       if (m[sum] == true) {
48         printf(" an Unhappy number.\n");
49         break;
50       }
51       n = sum;
52       m[sum] = true;
53     }
54   }
55 
56   return 0;
57 }

第一次用map，赶脚好神奇~

另外，还有一个代码用到了sprintf这个函数，这个东西以前听说过，但是一直没用过，所以自己也写了一下，学习了一下用法，貌似挺好用的~

在OJ上代码比第一个用数组标记的快。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cctype>
 6 #include <stack>
 7 #include <queue>
 8 #include <map>
 9 #include <set>
10 #include <vector>
11 #include <cmath>
12 #include <algorithm>
13 #define lson l, m, rt<<1
14 #define rson m+1, r, rt<<1|1
15 using namespace std;
16 typedef long long int LL;
17 const int MAXN =  0x3f3f3f3f;
18 const int  MIN =  -0x3f3f3f3f;
19 const double eps = 1e-9;
20 const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
21   {1,1},{1,-1},{-1,-1}};
22 map<int, bool> m;
23 int main(void){
24 #ifndef ONLINE_JUDGE
25   freopen("uva10591.in", "r", stdin);
26 #endif
27   int t, n; scanf("%d", &t);
28   for (int i = 1; i <= t; ++i){
29     scanf("%d", &n); m.clear(); m[n] = true;
30     printf("Case #%d: %d is", i, n);
31     while (n!= 1){
32       char s[20]; sprintf(s, "%d", n);
33       int sum = 0;
34       for (int j = 0; isdigit(s[j]); ++j){
35         sum += (s[j] - '0') * (s[j] - '0');
36       }
37       if (m[sum]){
38         printf(" an Unhappy number.\n"); break;
39       }
40       else m[sum] = true;
41       n = sum;
42     }
43     if (n == 1) printf(" a Happy number.\n");
44   }
45 
46   return 0;
47 }

计算各位平方和的时候，先把数字转化成字符串，然后再转化成整数一位一位地算。

另外还可以用set判重，也学习了一下，不过在OJ上测试说明貌似set判重比map慢一点儿

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cctype>
 6 #include <stack>
 7 #include <queue>
 8 #include <map>
 9 #include <set>
10 #include <vector>
11 #include <cmath>
12 #include <algorithm>
13 #define lson l, m, rt<<1
14 #define rson m+1, r, rt<<1|1
15 using namespace std;
16 typedef long long int LL;
17 const int MAXN =  0x3f3f3f3f;
18 const int  MIN =  -0x3f3f3f3f;
19 const double eps = 1e-9;
20 const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
21   {1,1},{1,-1},{-1,-1}};
22 
23 int main(void){
24 #ifndef ONLINE_JUDGE
25   freopen("uva10591.in", "r", stdin);
26 #endif
27   int t; scanf("%d", &t);
28   for (int i = 1; i <= t; ++i){
29     int n; scanf("%d", &n);
30     printf("Case #%d: %d is ", i, n);
31     set<int> se;
32     while (1){
33       int sum(0);
34       while (n){
35         sum += (n%10) * (n%10); n /= 10;
36       }
37       if (se.count(sum)){
38         printf("an Unhappy number.\n"); break;
39       }
40       if (sum == 1){
41         printf("a Happy number.\n"); break;
42       }
43       n = sum;
44       se.insert(sum);
45     }
46   }
47 
48   return 0;
49 }

STL继续认真学……