首页 / 软件开发 / 数据结构与算法 / UVa 10591：Happy Number

UVa 10591：Happy Number2014-10-09 csdn博客 shuangde800题目链接：

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1532

类型： 哈希表

原题：

Let the sum of the square of the digits of a positive integer S0 be represented by S1. In a similar way, let the sum of the squares of the digits of S1 be represented by S2 and so on. If Si = 1 for some i ≥ 1, then the original integer S0 is said to be Happy number. A number, which is not happy, is called Unhappy number. For example 7 is a Happy number since 7 -> 49 -> 97 -> 130 -> 10 -> 1 and 4 is an Unhappy number since 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4.

Input

The input consists of several test cases, the number of which you are given in the first line of the input. Each test case consists of one line containing a single positive integer N smaller than 10^9.

Output

For each test case, you must print one of the following messages:
Case #p: N is a Happy number.
Case #p: N is an Unhappy number.
Here p stands for the case number （starting from 1）. You should print the first message if the
number N is a happy number. Otherwise, print the second line.

样例输入：

3

7

4

13

样例输出：

Case #1: 7 is a Happy number.

Case #2: 4 is an Unhappy number.

Case #3: 13 is a Happy number.

题目大意：

所谓的Happy数字，就是给一个正数s， 然后计算它每一个位上的平方和，得到它的下一个数， 然后下一个数继续及选每位上的平方和……如果一直算下去，没有出现过之前有出现过的数字而出现了1， 那么恭喜，这就是个Happy Number.

如果算下去的过程中出现了一个之前出现过的，那么就不Happy了。

思路与总结：

这题算是最简单的一种hash应用， 学术一点的说法就是直接寻址表

这题最大的数是10^9, 那么各个位数上都最大的话就是9个9， 平方和为9*9*9 = 729,  所以只要开个730+的数组即可。

URL：http://www.bianceng.cn/Programming/sjjg/201410/45665.htm

对于出现过的数字， 就在相应的数组下标那个元素标志为true

/** UVa10591 - Happy Number* Time: 0.008s （UVa）* Author: D_Double*/#include<iostream>#include<cstdio>#include<cstring>using namespace std;int hash[810]; inline int getSum（int n）{int sum=0;while（n）{int t = n%10;sum += t*t;n /= 10;}return sum;} int main（）{int T, cas=1;scanf（"%d", &T）;while（T--）{int N, M;memset（hash, 0, sizeof（hash））;scanf（"%d", &N）;M = N;bool flag=false;int cnt=1;while（M=getSum（M））{if（M==1） {flag=true; break;}else if（hash[M] || M==N）{break;}hash[M] = 1;} printf（"Case #%d: ", cas++）;if（flag） printf（"%d is a Happy number.
", N）;else printf（"%d is an Unhappy number.
", N）;}return 0;}