uva10591 - Happy Number ——水题

April 15, 2013
Uva

题目链接：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，可以用一个数组标记这个数字是否被访问过。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
int visit[1000];
int solve(int n){
  int m = 0;
  while (n){
    m += (n%10)*(n%10); n /= 10;
  }
  return m;
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("uva10591.in", "r", stdin);
#endif
  int t, n;
  scanf("%d", &t);
  for (int i = 1; i <= t; ++i){
    scanf("%d", &n);int se = n; memset(visit, 0, sizeof(visit));
    while (1){
      n = solve(n);
      if (visit[n]) {
        printf("Case #%d: %d is an Unhappy number.\n",i,se);
        break;
      }
      if (n == 1) {
        printf("Case #%d: %d is a Happy number.\n",i,se); break;
      }
      visit[n] = 1;
    }
  }

  return 0;
}

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


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};

int main(void){
#ifndef ONLINE_JUDGE
  freopen("uva10591.in", "r", stdin);
#endif
  int t; scanf("%d", &t);
  map<int, bool> m; int n;
  for (int i = 1; i <= t; ++i){
    scanf("%d", &n);
    m.clear();
    printf("Case #%d: %d is",i, n);
    m[n] = true;
    while (1){
      int sum = 0;
      while (n){
        sum += (n%10) * (n%10); n /= 10;
      }
      //下面两个if位置不能调换，要先判断是不是等于1，然后再
      //判断这个值以前是不是用过，因为，当n == 1的时候，它
      //从一开始就被标记了，如果把后面一个if放在前面，就错了
      // 注意这种边界条件产生的逻辑错误
      if (sum == 1){
        printf(" a Happy number.\n");
        break;
      }
      if (m[sum] == true) {
        printf(" an Unhappy number.\n");
        break;
      }
      n = sum;
      m[sum] = true;
    }
  }

  return 0;
}

第一次用map，赶脚好神奇~ 另外，还有一个代码用到了sprintf这个函数，这个东西以前听说过，但是一直没用过，所以自己也写了一下，学习了一下用法，貌似挺好用的~ 在OJ上代码比第一个用数组标记的快。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
map<int, bool> m;
int main(void){
#ifndef ONLINE_JUDGE
  freopen("uva10591.in", "r", stdin);
#endif
  int t, n; scanf("%d", &t);
  for (int i = 1; i <= t; ++i){
    scanf("%d", &n); m.clear(); m[n] = true;
    printf("Case #%d: %d is", i, n);
    while (n!= 1){
      char s[20]; sprintf(s, "%d", n);
      int sum = 0;
      for (int j = 0; isdigit(s[j]); ++j){
        sum += (s[j] - '0') * (s[j] - '0');
      }
      if (m[sum]){
        printf(" an Unhappy number.\n"); break;
      }
      else m[sum] = true;
      n = sum;
    }
    if (n == 1) printf(" a Happy number.\n");
  }

  return 0;
}

计算各位平方和的时候，先把数字转化成字符串，然后再转化成整数一位一位地算。另外还可以用set判重，也学习了一下，不过在OJ上测试说明貌似set判重比map慢一点儿


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};

int main(void){
#ifndef ONLINE_JUDGE
  freopen("uva10591.in", "r", stdin);
#endif
  int t; scanf("%d", &t);
  for (int i = 1; i <= t; ++i){
    int n; scanf("%d", &n);
    printf("Case #%d: %d is ", i, n);
    set<int> se;
    while (1){
      int sum(0);
      while (n){
        sum += (n%10) * (n%10); n /= 10;
      }
      if (se.count(sum)){
        printf("an Unhappy number.\n"); break;
      }
      if (sum == 1){
        printf("a Happy number.\n"); break;
      }
      n = sum;
      se.insert(sum);
    }
  }

  return 0;
}

STL继续认真学……

Read more