问题
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3856 访问。
编写一个算法来判断一个数是不是“快乐数”。
一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。
Write an algorithm to determine if a number is "happy".
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
示例
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3856 访问。
public class Program {
public static void Main(string[] args) {
int nums = 19;
var res = IsHappy(nums);
Console.WriteLine(res);
nums = 26;
res = IsHappy2(nums);
Console.WriteLine(res);
nums = 65;
res = IsHappy3(nums);
Console.WriteLine(res);
Console.ReadKey();
}
private static bool IsHappy(int n) {
//递归法
var set = new HashSet<int>();
return ComputerHappy(n, set);
}
private static bool ComputerHappy(int n, HashSet<int> set) {
if(n == 1) return true;
if(set.Contains(n)) return false;
set.Add(n);
//计算各位数平方和
//int sum = 0;
//for(int i = 0; i < n.ToString().Length; i++) {
// sum += (int)Math.Pow(n / (int)Math.Pow(10, i) % 10, 2);
//}
return ComputerHappy(SquareSum(n), set);
}
private static int SquareSum(int n) {
//计算各位数平方和
var sum = 0;
while(n > 0) {
sum += (n % 10) * (n % 10);
n = n / 10;
}
return sum;
}
private static bool IsHappy2(int n) {
//若一个数不是快乐数，其必定死在4手上，最终进入以下死循环
//4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
//4的各数位平方是16，将y进行2次各位数平方和计算
//若相等，则到达了4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
//这样的死循环或到达了1这样的快乐数结束值
//返回x == 1即可判定是不是快乐数
var x = n;
var y = n;
do {
x = SquareSum(x);
y = SquareSum(SquareSum(y));
} while(x != y);
return x == 1;
}
private static bool IsHappy3(int n) {
//参考IsHappy2
while(n != 1 && n != 4) {
var sum = 0;
while(n > 0) {
sum += (n % 10) * (n % 10);
n /= 10;
}
n = sum;
}
return n == 1;
}
}以上给出3种算法实现，以下是这个案例的输出结果：
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3856 访问。
True
False
False分析：
该题的时间复杂度分析依赖于一些数学知识，若有看官知道如何分析请给我留言，不胜感激！