Python-查找第n个丑数

 1.丑数的定义：

质因数只包含2、3、5中的一个或多个的数称为丑数

2.分析：

对任意的一个丑数（除第一个丑数 1 外）ui，必定存在一个ut < ui，使得

ui = ut * 2 或 ut * 3 或 ut * 5，

若不成立则：

1.ui % (2|3|5) 不等于 0，ui 不是整数

2.ui % (2|3|5)等于 0，ui / (2|3|5)是丑数则， ui 也是丑数，ui / (2|3|5)不是丑数，则 ui 也不是丑数

因此，对于一个已知的丑数序列a1，a2，...，ai(设为递增序列)：

新的丑数 ai + 1 为a1*2，a1*3，a1*5，a2 * 2，...，ai *5 中大于原丑数列表中最大值 ai 的最小的数

3.算法

# coding=utf-8

"""
question:
质因子只包含2、3、5中的一个或多个数称为丑数，要求按从小到大的顺序找到第 n 个丑数
1 为第一个丑数
"""


def find_num(n):
    if n < 1:
        return 0

    # 丑数列表初始化
    num_list = [1]

    t2 = t3 = t5 = 0
    """
    ti 的定义：
    1.对任意的 t < ti, i * num_list[t] <= num_list[-1]
    2.对任意的 t > ti，i * num_list[t] > num_list[-1]
    """
    while len(num_list) < n:
        num_list.append(min(num_list[t2] * 2, num_list[t3] * 3, num_list[t5] * 5))

        # 重新查找 t2、t3、t5
        while 2 * num_list[t2] <= num_list[-1]:
            t2 += 1

        while 3 * num_list[t3] <= num_list[-1]:
            t3 += 1

        while 5 * num_list[t5] <= num_list[-1]:
            t5 += 1

    return num_list[-1]


if __name__ == '__main__':
    for i in range(1, 20):
        print(find_num(i))