Số vui (Happy Numbers) trong Python

Cho số n, kiểm tra xem có phải số vui (happy number) hay không. Số vui: bắt đầu từ số dương bất kỳ, thay số bằng tổng bình phương các chữ số, lặp lại cho đến khi thành 1, nếu không sẽ lặp vô tận trong chu kỳ. Những số đạt được 1 là số vui.

Ví dụ, 19 -> True:

1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Các bước giải quyết (đệ quy + nhớ trạng thái):

Cơ sở: nếu n == 1, trả về True.
Nếu n đã thăm, trả về False.
Đánh dấu n đã thăm.
n thành chuỗi, l danh sách chữ số.
temp := tổng bình phương chữ số.
Gọi đệ quy với temp và tập đã thăm.

Ví dụ minh họa

class Solution(object):
    def isHappy(self, n):
        return self.solve(n, {})

    def solve(self, n, visited):
        if n == 1:
            return True
        if n in visited:
            return False
        visited[n] = 1
        n = str(n)
        l = list(n)
        l = list(map(int, l))
        temp = 0
        for i in l:
            temp += (i ** 2)
        return self.solve(temp, visited)

ob = Solution()
print(ob.isHappy(19))

Đầu vào

Đầu ra

True