a863: 3. Happy Numbers

內容

大多數的人認為數字是冷酷無情的，事實上某些數字是充滿活力的，學會判斷一個數是否快樂其實很簡單。挑選一個正整數，求其所有位數平方的總和，持序這個動作直到所有位數的平方和為 1 或是進入循環，可以收斂到 1 則為快樂的，循環則為不快樂。可以假定所有循環週期不超過 100。

例如：
以 32 為例
32 → 33+22=13
13 → 11+33=10
10 → 11+00=1
故 32 是快樂的數

輸入

輸入包含一個正整數 n

32
4565

輸出

輸出”n is a happy number” 或”n is an unhappy number”(不含引號)

32 is a happy number
4565 is an unhappy number

解題思路

參考上圖，任何無法收斂到 1 ，也就是"非"快樂數都會進入以下循環

4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4

而由於不管是從哪一點進入循環，只要不斷的求出該數的所有位數平方的總和，最後都會變成 4 ，所以只要判斷是否收斂到 1 (快樂數) 或是出現 4 (進入循環，非快樂數) 即可確認狀態跳出迴圈後輸出答案即可。

完整程式碼

AC (2ms, 92KB)

#include <stdio.h>

int main()
{
    int n, now, tmp;
    while (scanf(" %d", &n) == 1)
    {
        for (now = n; now != 1 && now != 4; now = tmp)
        {
            tmp = 0;
            while (now)
            {
                tmp += (now % 10) * (now % 10);
                now /= 10;
            }
        }
        if (now == 1)
            printf("%d is a happy number\n", n);
        else if (now == 4)
            printf("%d is an unhappy number\n", n);
    }
    return 0;
}