寫leetcode的時候遇到一題有夠好玩的,要你判斷一個數字是不是快樂數(happy number)。
先看快樂樹 快樂數的定義
把一個整數n的每一位做平方相加,變成新的n。如果最後n=1,那這個數就叫做快樂數;反之如果最後n在好幾個數之間循環,則n不快樂。
看一個例子,假設n=19
經過一連串運算後n=1,所以19為快樂數
那麼程式就很好寫了。只要寫一個迴圈重複此運算,當n==1時跳出迴圈,這樣就好了。
不過下一個問題:如果這不是一個快樂數呢? 根據定義,不快樂數在反覆的計算過程中根本不會出現n==1這種結果,你在那邊算個兩百萬次也算不出來,然後電腦就爆了。
所以說這個問題的核心是在『如何知道這個數不快樂』
我拿了張紙開始計算,把28、29、183三個數字進行快樂運算,然後有兩個粗略的推論:
(1)
28是偶數位、各位數總和是偶數,並且為快樂數;29是偶數位、各位數總和是奇數、並且不為快樂數;183為奇數位、各位數總和為偶數、並且不為快樂數
所以我就在猜有沒有可能位數和各位數總和必須一樣(例如28兩個都是偶數)才會是快樂數。為了驗證,我計算53867是不是快樂數(五位數、總和為29)
結果53867不是快樂數,而且5386 (四位數、總和為22)也不快樂。
到這邊我就想可能不是從位數和總和來判斷的,所以集中思考第二個點。
(2)
在計算29、183和53867的時候,我注意到循環的過程只要出現某些特定數字,就會陷入循環
因為懶得再手算了,就簡單寫了個小程式來幫算,最後發現下列循環
16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16
只要計算過程出現上面的任一個數字,就會進入此循環,無法達到n==1
(P.S.如果出現61或98這種也會導致進入循環,因為快樂運算是將各個位數平方加總,因此數字順序不影響)
我也不曉得有沒有別的循環,反正試了幾十個數字,都一定會出現這個循環。
反正我寫程式也不講求優雅,就簡單粗暴一點。寫一個while迴圈重複快樂運算,只要計算途中出現這幾個數字就直接回傳false,而出現1就回傳true。
看來這個方法真的可行LUL