主页 / 问题 / 1482969
Accepted
Ян Альбертович Дененберг
Asked:2023-01-02 07:07:26 +0000 UTC2023-01-02 07:07:26 +0000 UTC

如何改进解决算术问题的代码？

  • 772

下面的代码解决了以下问题：

找到最大的自然数，如果您将其数字的总和添加到它，您将得到用户输入的数字。

# Найдите наибольшее натуральное число, такое, что если прибавить
# к нему сумму  его цифр, получится число, введённое пользователем.

n = int(input())
k = n
while (k + sum(int(digit) for digit in str(k)) != n) and k!=0:
    k -= 1
if k!=0:
    print(k)
else:
    print('No such positive integer.')

我将接受任何旨在优化上述代码的建设性批评。

python-3.x

2 个回答

  1. 想到的第一个优化是任意k≤n的位数之和不超过9·<number of digits n>。换句话说，不要离n太远：

    def k(n):
    for k in range(n, max(0, n - 9 * len(str(n)) - 1), -1):
        if k + sum(map(int, str(k))) == n:
            return k
    return None

    旧版本的复杂度是n log n。第一个乘数是验证循环的重复次数，第二个是一次验证的成本（复杂性被低估了，但它会满足我们的目的）。

    新变体具有log 2  n复杂度。在最坏情况下，迭代次数已从线性减少到对数。

    如果知道相邻整数的数字之和相差不大，则可以从对数中去掉平方。由此产生的复杂度为log n，这是最佳的，因为需要对数才能读取数字的所有数字。

    PS关于按部门更换str。理论上，替换会恶化复杂性。要通过除以十从数字n中提取所有数字，需要log 2  n操作 - log n除法，每个除法也需要log n。该功能str可以更快地完成 - 数字系统之间的转换可以更复杂地完成......

    PPS ...但在 Python 中它str实现缓慢，用于对数的平方。

    • 4
  2. Best Answer

    我将举一个小例子说明如何在更短的时间内解决问题，其中包括速度测试。

    大意

    • 为了计算总和，我们只使用算术。

    代码

    import time

def test(n):
    k = n
    while (k + sum(int(digit) for digit in str(k)) != n) and k!=0:
        k -= 1
    if k!=0:
        return(k)
    else:
        return('No such positive integer.') 

def findSum(num):
    s = 0
    while num > 0: 
        s += num % 10
        num = num // 10
    return s    

def test2(n):
    k = n
    while k and (k + findSum(k) != n):
        k -= 1
    if k:
        return(k)
    return('No such positive integer.') 

start = time.time()
for i in range(10000):
    r = test(i)
end = time.time()
print(end - start, r)

start = time.time()
for i in range(10000):
    r = test2(i)
end = time.time()
print(end - start, r)

    结论：

    9.353121042251587 9972
4.550509214401245 9972

    结果，我们获得了几乎两倍的性能。

    • 3

相关问题