[202] Happy Number

原來最後有這個偷吃步的方法XD 也太happy了吧！！！

先貼一下結果，細節等我把龜兔賽跑寫完再來繼續XD

bool isHappy(int n){

    int num=n;

    int sum=0;

    while (1)

    {

        if (num == 4)

            return false;

        while(num > 0)

        {

            sum+=pow(num%10,2);

            num=num/10;

        }

        if (sum==1)

            return true;

        else

        {

            num =sum;

            sum=0;

        }

    }

    return false;

}

好的龜兔賽跑就是說～在經過一段起始之後～它們會進入一個迴圈;

你可以用一個hashset 去存哪個數字已經出現過了, 但是大家都知道 C 寫這個會累死吧XD

所以龜兔賽跑就讓兩個判斷同時跑, 烏龜一次跑一步, 兔子一次跑兩步, 如果他們形成回圈了, 那麼這兩隻一定會有值相同的那天, 那麼就return false , 除非他們都等於一, 也就是在此例中等於一是一個收斂的情況

然後聽說這個又叫做Floyd Cycle detection algorithm 啦. 

int checkSum(int n)

{

    int num=n;

    int sum=0;

    while(num > 0)

    {

        sum+=pow(num%10,2);

        num=num/10;

    }

    return sum;

}

bool isHappy(int n){

    int num=n;    

    int sum=0;

    int slow=n, fast=n;

    while(fast != 1)

    {

        slow = checkSum(slow);

        fast = checkSum(checkSum(fast));

        if ((slow == fast) && (fast != 1))

            return false;    

    }

    return true;

}