こちらは「Happy Number」のPythonによる解答例となっております。この問題は、与えられた整数が「幸せな数」であるかどうかを判断する問題です。
問題
整数 n が与えられたとき、以下の手順を繰り返すと、1が得られる場合、nは「幸せな数」であると言われています。nが「幸せな数」である場合、真を返し、そうでない場合は偽を返します。
- 各桁を2乗し、それらの合計を取得する。
- 1が得られるまで手順1を繰り返す。
解法
この問題は、ハッシュセットを用いた1つのアプローチがあります。ハッシュセットは、要素を一意に保持するため、この問題に適しています。
アルゴリズムの概要を以下に述べます。
- ハッシュセットを初期化します。
nの各桁を2乗し、それらの合計を計算します。- 計算結果が1である場合、
nは「幸せな数」であるため、真を返します。 - 計算結果が既にハッシュセットに存在する場合、
nは永久にループするため、偽を返します。 - ハッシュセットに計算結果を追加します。
- 手順2に戻ります。
Pythonコード
以下のコードが、「Happy Number」を解くためのPythonプログラムとなります。
### Function ##################################################################
def solve(num=0):
solver = Solution().isHappy
if 1 <= num <= Input().input: id_LIST = [num]
else: id_LIST = [id+1 for id in range(Input().input)]
for id in id_LIST:
data = Input(id)
ans = solver(data.n)
result = "OK" if ans==data.ans else "NG"
print(f"[{str(id).zfill(3)}] {result}")
### Class #####################################################################
class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
known_SET = set()
while n != 1:
n = sum([int(i) ** 2 for i in str(n)])
if n in known_SET: return False
else: known_SET.add(n)
else: return True
#==============================================================================
class Input:
def __init__(self, num=0):
if num == 1:
self.n = 19
self.ans = True
elif num == 2:
self.n = 2
self.ans = False
else:
self.input = 2
### Main ######################################################################
if __name__ == "__main__":
solve()
###############################################################################