主題

快樂數—如何判斷一個數字是不是happy number

別再打了我認錯就是了 | 2022-03-23 18:21:08 | 巴幣 3258 | 人氣 747




寫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

創作回應

T113
要嘛會進入n==4循環,不然就可以得到n==1
2022-03-23 20:20:31
別再打了我認錯就是了
這樣應該會更精簡,讚讚。我現在是判斷n==16 || n==37 ... 一大串or
2022-03-24 02:38:08
熊頭紳士—虐饅啦噫哈
我只是來看梗圖的讓我看數學?
2022-03-23 20:21:44
別再打了我認錯就是了
這裡是群聊,不是數學怪人俱樂部
2022-03-24 02:38:32
stia27000
我認為可以透過每個位數的平方總和是否滿足10幾次方這點判斷
2022-03-24 00:57:40
別再打了我認錯就是了
我猜應該方法直接從數字本身得知,而不用迭代。但是試來試去也找不到規律,就懶得弄了
2022-03-24 02:39:35
小海
好像很厲害!
2022-03-24 23:50:38
羽刈ㅤ
happy number friends
2022-03-25 18:40:45

相關創作

更多創作