Pythonでハッピー数（Happy Number）を判定する方法を解説

ハッピー数とは？

ハッピー数（Happy Number）とは、任意の正の整数から始めて「その数を各桁の数字の2乗の和で置き換える」という操作を繰り返し行ったとき、最終的に1に到達する数のことです。1に到達できない場合、計算結果は同じ値のサイクルを永遠に繰り返します。そして、1に到達できた数だけがハッピー数とみなされます。

具体例：19の場合

例えば、数値19がハッピー数かどうかを確認してみましょう。この場合、結果はTrue（ハッピー数である）になります。実際の計算過程は以下の通りです。

1² + 9² = 82

8² + 2² = 68

6² + 8² = 100

1² + 0² + 0² = 1

アルゴリズムの考え方

この問題を解くには、以下の手順に従います。

• メモ化（動的計画法）のアプローチを使用し、再帰的に問題を解きます。
• ベースケース：nが1のとき、Trueを返します。
• nがすでに訪問済みの場合はFalseを返します（無限ループの検知のため）。
• nを訪問済みとしてマークします。
• nを文字列に変換し、各桁の数字からなるリストを作成します。
• 各桁の2乗の合計値を計算します。
• その合計値と訪問済みリストを引数として、関数を再帰的に呼び出します。

Pythonでの実装例

それでは、より理解を深めるために実際のコードを見てみましょう。

class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        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)
ob1 = Solution()
op = ob1.isHappy(19)
print("Is Happy:",op)

入力

19

出力

Is Happy: True

このコードでは、isHappyメソッドが内部のsolveメソッドを再帰的に呼び出しています。辞書型のvisitedで一度計算した値を記録しておき、同じ値が再度現れた場合は循環に入ったと判断してFalseを返します。これにより、無限ループを確実に防ぐことができます。