類型： 哈希表
原題：
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+的數組即可。
對於出現過的數字， 就在相應的數組下標那個元素標志為true
[cpp]
/*
* UVa 10591 - 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", N);
else printf("%d is an Unhappy number.\n", N);
}
return 0;
}
