python 实现hamming numbers汉明数算法

hamming numbers汉明数算法介绍

汉明数（Hamming numbers）是形式为 $2^i\cdot 3^j\cdot 5^k$的正整数，其中 𝑖,𝑗,𝑘是非负整数。汉明数序列的前几项是 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …

在Python中，我们可以使用最小堆（Min Heap）来高效地生成汉明数序列。这是因为最小堆可以帮助我们始终选择当前可生成的最小汉明数，并基于它生成新的汉明数。

以下是使用Python的heapq库来实现生成前N个汉明数的算法：

import heapq

def generate_hamming_numbers(n):
    # 初始化一个最小堆，初始元素为(1, 0, 0, 0)，表示当前的汉明数及其因子指数
    # (hamming_number, exp_of_2, exp_of_3, exp_of_5)
    heapq.heappush(heap, (1, 0, 0, 0))
    hamming_numbers = []
    
    while len(hamming_numbers) < n:
        hamming_num, exp_2, exp_3, exp_5 = heapq.heappop(heap)
        hamming_numbers.append(hamming_num)
        
        # 生成下一个可能的汉明数
        if exp_2 + 1 < 32:  # 防止2的指数过大导致溢出
            heapq.heappush(heap, (hamming_num * 2, exp_2 + 1, exp_3, exp_5))
        if exp_3 + 1 < 20:  # 防止3的指数过大导致溢出
            heapq.heappush(heap, (hamming_num * 3, exp_2, exp_3 + 1, exp_5))
        if exp_5 + 1 < 14:  # 防止5的指数过大导致溢出
            heapq.heappush(heap, (hamming_num * 5, exp_2, exp_3, exp_5 + 1))
            
    return hamming_numbers

# 示例：生成前15个汉明数
n = 15
print(generate_hamming_numbers(n))

注意：

我们使用了元组 (hamming_number, exp_of_2, exp_of_3, exp_of_5) 来存储每个汉明数及其对应的因子指数。这样做的目的是为了在生成新的汉明数时，能够快速计算出新的汉明数，并且避免重复生成相同的数。

我们为2、3和5的指数设置了上限（分别为32、20和14），这是基于Python中整数表示的限制。在实际情况中，这些上限可能需要根据具体需求进行调整。

使用最小堆（heapq）来维护所有可能生成的汉明数，确保每次都能从所有可能中取出最小的汉明数。

hamming numbers汉明数算法python实现样例

汉明数（Hamming numbers），也称为ugly numbers，是指能够被2、3和5整除的正整数。

以下是使用Python实现汉明数算法的示例代码：

def hamming_number(n):
    hamming_numbers = [1] * n
    i2, i3, i5 = 0, 0, 0
    
    for i in range(1, n):
        hamming_numbers[i] = min(hamming_numbers[i2] * 2, hamming_numbers[i3] * 3, hamming_numbers[i5] * 5)
        
        if hamming_numbers[i] == hamming_numbers[i2] * 2:
            i2 += 1
        if hamming_numbers[i] == hamming_numbers[i3] * 3:
            i3 += 1
        if hamming_numbers[i] == hamming_numbers[i5] * 5:
            i5 += 1
            
    return hamming_numbers[-1]

# 测试
print(hamming_number(10))  # 输出 12
print(hamming_number(20))  # 输出 36

在这个算法中，我们使用了动态规划的思想。hamming_numbers列表保存了已经生成的汉明数，在开始时，我们将其都初始化为1。然后，我们使用三个索引i2、i3和i5来指示下一个汉明数可能来自的位置。

我们从1开始，依次计算下一个汉明数，每次取三个位置中的最小值。然后，我们根据最小值来更新对应的索引，以保证下一次计算时使用的是正确的位置。

最后，我们返回hamming_numbers列表中的最后一个数，即第n个汉明数。

注意，这个算法的时间复杂度是O(n)，其中n是要计算的汉明数的序号。