Epoch

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

  1^2 + 9^2 = 82

  8^2 + 2^2 = 68

  6^2 + 8^2 = 100

  1^2 + 0^2 + 0^2 = 1

題意

  找出題目定義的 happy number，若數字位數大於個位，就用迴圈拆解成一個一個，再算出各個數字的平方和，這個數字，會是新的數字，經過若數回合，若這個數字等於1，那他就是 happy number。

想法

  原本想用遞迴做，想出下面的 code

  if(n==1)

    return true

  else{

    拆解算平方和，n=平方和

    return isHappy(n);

  }

  寫到這發現，不知道什麼時候要 return false

  拆解平方和就用取餘數和除以十的方法做

  跑一次後，看哪個 case 失敗，就用紙筆去 trace 看看

  首先 2 就發生錯誤，下面來 trace 看看錯誤的原因

    2 -> 4

    4 -> 16

    16 -> 37

    37 -> 58

    58 -> 89

    89 -> 145

    145 -> 42

    42 -> 20

    20 -> 4

  發現到這邊 4 就重複出現，所以有個想法，就是紀錄第一個的平方，若之後再出現即回傳 false，但沒想到到其他數字還是會發生錯誤，仔細觀察我存的變數，發現他循環不一定會從第一個開始循環，所以改用 array 儲存出現過的數字，之後一一比對，最後終於 AC

程式碼如下

  bool isHappy(int n) {
    int sum, i;
    int count=0;
    int save[100];
    while(1){
        if(count>1)
        {
            for(i=0; i<count-1; i++){
                if(n==save[i])
                    return false;
            }
        }
        if(n==1)
            return true;
        else{
            sum=0;
            while(n>9){
                sum+=pow(n%10, 2);
                n/=10;
            }
            sum+=pow(n, 2);
            n=sum;
            save[count]=n;
            count++;
        }
    }
}

解法還是很粗糙，需要多多加強