hamming number 解法メモ#
問題：Codewars サイト#
solutions#
***自分の最初の考え方：***ある数を素因数分解し、その素因数が 2、3、5 だけかどうかを確認すればよい。#
def is_hamming_number(num):
"""判断一个数是否是 Hamming 数"""
while num % 2 == 0:
num //= 2
while num % 3 == 0:
num //= 3
while num % 5 == 0:
num //= 5
return num == 1
def generate_hamming_numbers(n):
"""生成前 n 个 Hamming 数"""
hamming_numbers = []
num = 1
while len(hamming_numbers) < n:
if is_hamming_number(num):
hamming_numbers.append(num)
num += 1
return hamming_numbers
def nth_hamming_number(n):
"""查询第 n 个 Hamming 数"""
hamming_numbers = generate_hamming_numbers(n)
return hamming_numbers[-1] if n <= len(hamming_numbers) else Noneこの考え方は単純明快です。ひたすら数を走査し、素因数が 2、3、5 だけの数を見つけたらリストに入れていきます。
その後、上の solutions と自分の考え方を比べると、明らかな最適化が見えます。solutions は余計な操作をせず、直接次の Hamming number を見つけています。これができるのは、数字の規則性を簡単に分析し、少し数学的分析と数論の知識を使っているからだと思います。以下は自分なりの簡単な分析証明です。
アルゴリズムの正しさに関する自分の証明
最後に自分が「不可能」と思ったのは、当時は思いつかなかったからです。実際には、その数が 2、3、5 の倍数であればよい、というだけでした。
