23.%d\n Cycle Detection（循環偵測）

題目給予的條件

Input: 19
Output: true
Explanation:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
bool isHappy(int n) {
}

是謂快樂的數字(Happy Number)

Input: 20
Output: false
Explanation:
2^2 + 0^2 = 4
4^2       = 16
1^2 + 6^2 = 37
3^2 + 7^2 = 58
5^2 + 8^2 = 89
8^2 + 9^2 = 145
1^2 + 4^2 + 5^2 = 42
4^2 + 2^2 = 20

思考過程

Ex：
n = 12345；
d = 1, 2, 3, 4, 5；
12345 / 1     % 10 = 5
12345 / 10    % 10 = 4
12345 / 100   % 10 = 3
12345 / 1000  % 10 = 2
12345 / 10000 % 10 = 1
整數最多十位數
n = 12345；     (用來思考的假定數)
int r = 0；
for (int m = 1； m <= 1000000000； m *= 10) {
   int d = n / m % 10；
   printf("%d\n", d)；
   r += d * d；（乘以九次後已達等於，但想再跑一次迴圈讓它結束，卻變成溢位）
   return false；
}
int r = 0；
int m = 1；
for (int k = 1； k <= 10； k++) {
   int d = n / m % 10；
   printf("%d\n", d)；
   r += d * d；
   if(k < 10) { 
      m *= 10；（乘以九次後，k = 9，在跳進第十次迴圈時，這行不會執行）
   } 
   return false；
  
}

要將一個數字拆成各個位數的平方和，必須要有int r，並在迴圈裡將 n除以一個不斷增大十倍的m，再取餘，每次得到最後一位為d。

但這個迴圈要停下來，為m = 1000000000再乘以10，這時已經溢位而編譯錯誤。

於是改使用k，k從1~10，在k = 11時迴圈結束，但必須設置k < 10的時候，m才會乘以10，如此才不會溢位。但我們通常不希望變數太多，所以多一個k不是很方便，為了避免溢位，又不希望多一個變數，於是迴圈可以倒過來寫

int r = 0；
int m = 1；
for (int m = 1000000000； m >= 1； m /= 10) {
   int d = n / m % 10；
   r += d * d；
   printf("%d\n", r)；
   return false；
}

不過，此結果就是會做十次的d，印出十次的r，但n不會總是那麼大(十位數)，所以這個方法在n非十位數時多做了幾次，所以再用while改寫

int r = 0；
while(n != 0) {
   int d = n % 10；
   n /= 10；
   r += d * d；
}
printf("%d\n", r)；
return false；

即是在這個數還不等於0的時候，一路除以10，那麼在它變成0的時候就不會做了，這個時候，我們就可以印出想要的結果r。

但是我們不只會做一次，當想要的數字的各個位數拆出來做平方和後，得到數字後，我們還想繼續做下去，所以這段程式碼可以寫成函式。

一般解法：

int next_n(int n) {
   int r = 0；
   while(n != 0) {
      int d = n % 10；
      n /= 10；
      r += d * d；
   }
}
bool contains(int* history, int size, int n) {
   for(int i = 0； i < size； i++) { 
      if (history[i] == n) {
          return true；
      }
   }
   return false；
}
bool isHappy(int n) {
   int history[1000]；
   int size = 0；
   while( !contains(history, size, n)) { 
      history[size] = n；
      size ++；
      n = next_n(n)；
   }
   printf("%d\n", next_n(n))；
   return n == 1；
}

第一次把n加到歷史陣列裡，算出下一個n再加入歷史陣列裡，在這段歷史裡，去比對歷史元素是否有等於函式算出來的n，如果有，迴圈就結束。

陣列的size選擇1000的原因是，如果是9,999,999,999來看，9*9*10 = 810算出不同組合的數字共810個，但我們可設為1000保險點。

return n == 1；
如果n == 1，return是true，如果n != 1，return是false，完成一個解法。

雙指標循環偵測：

int next_n(int n) {
   int r = 0；
   while(n != 0) {
      int d = n % 10；
      n /= 10；
      r += d * d；
   }
}

bool isHappy(int n) {
   int turtle = n；
   int rabbit = n；
   do {
      turtle = next_n(turtle)；
      rabbit = next_n(next_n(rabbit))；
   } while (turtle != rabbit)；
   return fast == 1；
   
}

在呼叫函式兩次的兔子走到終點後，呼叫一次的烏龜還沒走到終點，當他們撞在一起時，迴圈結束，來看看結束的那個數字是否為1，如果是就是true，如果非就是false，以此來判斷快樂的數字。