题目描述

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.

Example: 19 is a happy number

• 12 + 92 = 82
• 82 + 22 = 68
• 62 + 82 = 100
• 12 + 02 + 02 = 1

• 题目理解

• 本题就是求一个正整数是否是happy number.一个正整数，求在各个位上的数字的平方和，再求平方和各个位上的平方和，依次不断重复，若平方和为0，则是Happy number.否则不是，并且不是happy number的那些数字按照上述计算所得的平方和结果构成一个圆，这个圆中没有1.即如果不是happy number计算平方和的过程一直在进行不断重复也没有一个平方和等于1。

• 解题思路

• 原正整数为n，取n的各个位上的数字，求平方和，若不是1，则令n=平方和，继续进行，一旦等于1，退出，并返回true。

• 这点不难，关键问题是如果这个正整数不是happy number，上面求平方和的过程一直在进行，所有结果构成一个圆。所以我们要找到这个圆的接点，一旦发现本次的平方和结果与之前的平方和有一个重复的，立即退出，并返回false.

• 具体代码如下

• #include <iostream>
  #include <vector>
  #include <iterator>
  using namespace std;
  bool isHappy(int n) ;
  void main()
  {
  	int n=7;
  	cout<<isHappy(n); 
  }
  bool isHappy(int n) {
  	if (n<=0) return false;
  	if (n==1) return true;
  	vector<int> bit_num,recode;
  	bool flag=false;
  	int res=0;
  	while(n)
  	{
  		bit_num.clear();
  		res=0;
  		while(n/10)
  		{
  			int temp=n%10;
  			bit_num.push_back(temp);
  			res+=temp*temp;
  			n=n/10;
  		}
  		if (n%10!=0)
  		{
  			
  			bit_num.push_back(n%10);
  			res+=(n%10)*(n%10);
  		}
  		recode.push_back(res);
  		cout<<res<<endl;
  		if (res==1)
  		{
  			flag=true;
  			break;
  		}
  		else
  		{
  			vector<int>::iterator iter;
  			for (iter=recode.begin();iter!=recode.end()-1;iter++)
  			{
  				if (res==*iter&&recode.size()>1)
  				{
  					flag=false;
  					return flag;
  				}
  			}
  			n=res;
  		}
  	}
  	return flag;
  }

  
  其中，我们用recode数组记录算出来的平方和，一旦有重复的，且无1，立即退出返回false.