gpt4 book ai didi

python - 如何优化此 Python 脚本,该脚本检查一个数字是否等于其数字总和乘以一个因数?

转载 作者:行者123 更新时间:2023-12-04 02:34:08 26 4
gpt4 key购买 nike

想深入了解如何优化 Python 脚本的速度。

挑战:“哪些正整数等于其数字和的 23 倍”>> 这是我的功能代码:

def sum_of_digits(number):
sum = 0;
for c in number:
sum += ord(c) - 48;

return sum;

upper_limit = 10000000000;
count = 0;
for i in range(1, upper_limit, 1):
if(23 * sum_of_digits(str(i)) == i):
print(i);
count += 1;

正确地吐出 207 作为答案 (2+0+7 = 9. 9 x 23 = 207)。

问题是执行时间缩放为 (n)。

虽然我可以预先计算 sum_of_digits - 这不会节省时间,我正在寻找 Python 方法来加快执行速度。

我知道我可以深入研究数论并将其“数学化”——但我对我可以从 Python 中榨取什么很感兴趣。

最后,我知道其他语言可能会更快,但我是一名高中物理老师,在暑期类(class)中使用它作为 STEM 示例。

最佳答案

首先,这是 Python,因此您不需要将 ; 放在语句的末尾。由于您正在寻找 23 的倍数的数字,因此如果您遍历 23 的倍数的数字,您可以获得一些性能:

for i in range(0, upper_limit, 23):
# 'i' will take values 0, 23, 46, ...

如果您处理 int,您的 sum_of_digits 函数会执行得更好。取自here :

def sum_digits(n):
r = 0
while n:
r, n = r + n % 10, n // 10
return r

所以最终的代码将是:

upper_limit = 10000000000
count = 0
for i in range(0, upper_limit, 23):
if (23 * sum_digits(i) == i):
print(i)
count += 1

print(count)

但是,这仍将在 O(n*m) 中执行,因为您有嵌套循环。

我们可以做一些数学运算并打破循环,而不是试图盲目地找到这样的数字。

For 1 digit numbers 23 * sum_digits(i) would be 23 * 9 = 207 at maximum.For 2 digit numbers 23 * sum_digits(i) would be 23 * 18 = 414 at maximum.For 3 digit numbers 23 * sum_digits(i) would be 23 * 27 = 621 at maximum.For 4 digit numbers 23 * sum_digits(i) would be 23 * 36 = 828 at maximum.For 5 digit numbers 23 * sum_digits(i) would be 23 * 45 = 1035 at maximum....

You can see the pattern here. We actually don't need to search for the numbers which have 4 digits or more. Because all the 4 digit numbers are greater than 828 and all the 5 digit numbers are greater than 1035 etc.So here is a better solution which breaks when we are sure that all the remaining numbers won't be valid.

def sum_digits(n):
r = 0
while n:
r, n = r + n % 10, n // 10
return r

upper_limit = 10000000000
count = 0
for i in range(0, upper_limit, 23):
number_length = len(str(i))
if number_length * 9 * 23 < i:
break
if 23 * sum_digits(i) == i:
print(i)
count += 1

print(count)

关于python - 如何优化此 Python 脚本,该脚本检查一个数字是否等于其数字总和乘以一个因数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62711993/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com