wangshuo'blog

wangshuo'blog

算法 | -水仙花数代码优化

Published on
Last updated on

算法 | -水仙花数代码优化

水仙花数字（Narcissistic number）是指一个 n 位数（n ≥ 1），其各位数字的 n 次幂之和等于该数本身。例如，当 n = 3 时，153 是一个水仙花数字，因为 1³ + 5³ + 3³ = 153。

下面就对一个水仙花数的 Python

以下是一个简单使用 Python 实现的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import time


def main():
    n = 7
    results = []
    for i in range(10 ** (n - 1), 10 ** n):
        total = 0
        k = i
        for j in range(n):
            y = k % 10
            total = total + y ** n
            k = k // 10
        if total == i:
            results.append(i)
    print("所有的 {} 位水仙花数字为：".format(n), results)


if __name__ == '__main__':
    for i in range(10):
        start_time = time.time()
        main()
        end_time = time.time()
        execution_time = end_time - start_time
        print("执行时间：{:.2f} 秒".format(execution_time))

耗时

image-20230609042152583

后面会逐步对上面算法进行优化。

减少计算重复

在计算水仙花数字时，可以避免对每个数字都进行幂次计算。可以提前计算好所有可能的数字的幂次值，并存储在一个字典中。然后，通过查找字典来获取数字的幂次值，避免重复计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import time


def main():
    n = 7
    power_dict = {str(i): i ** n for i in range(10)}
    results = []
    for i in range(10 ** (n - 1), 10 ** n):
        num_str = str(i)
        total = sum(power_dict[digit] for digit in num_str)
        if total == i:
            results.append(i)
    # print("所有的 {} 位水仙花数字为：".format(n), results)


if __name__ == '__main__':
    for i in range(10):
        start_time = time.time()
        main()
        end_time = time.time()
        execution_time = end_time - start_time
        print("执行时间：{:.2f} 秒".format(execution_time))

image-20230609042559202

引入多线程

将任务划分成多个小任务，每一个小任务创建一个线程来处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import threading
import time

def main():
    n = 7
    power_dict = {str(i): i ** n for i in range(10)}
    lock = threading.Lock()
    results = []

    def check_narcissistic(start, end):
        for i in range(start, end):
            num_str = str(i)
            total = sum(power_dict[digit] for digit in num_str)
            if total == i:
                with lock:
                    results.append(i)

    # 设置线程数量（根据实际情况调整）
    num_threads = 8
    total_numbers = 10 ** n - 10 ** (n - 1)
    numbers_per_thread = total_numbers // num_threads

    threads = []

    for i in range(num_threads):
        start = 10 ** (n - 1) + i * numbers_per_thread
        end = start + numbers_per_thread
        thread = threading.Thread(target=check_narcissistic, args=(start, end))
        threads.append(thread)
        thread.start()

    for thread in threads:
        thread.join()

    results.sort()
    # print("所有的 {} 位水仙花数字为：".format(n), results)


if __name__ == '__main__':
    for i in range(10):
        start_time = time.time()
        main()
        end_time = time.time()
        execution_time = end_time - start_time
        print("执行时间：{:.2f} 秒".format(execution_time))

耗时

image-20230609042913636