Project Euler # 1 Сумма кратных 3 и 5 реализации python

Дано:

  

Если мы перечислим все натуральные числа ниже 10, кратные 3 или 5, получим 3, 5, 6 и 9. Сумма этих кратных значений равна 23.   Найдите сумму всех кратных 3 или 5 ниже 1000.

Мое решение:

def sum_multiples(num, limit):
    """ Calculates the sum of multiples of a given number.
    Args:
        num: The multiple.
        limit: The upper limit.
    Returns:
        The sum of the terms of a given multiple.
    """
    sum = 0
    for i in xrange(num, limit, num):
        sum += i
    return sum

def sum(limit):
    return (sum_multiples(3, limit) +
            sum_multiples(5, limit) -
            sum_multiples(15, limit))

print sum(1000)

Есть ли какой-нибудь лучший или более pythonic способ? Я использовал генераторы для очень больших вычислений. Кроме того, как я могу получить время выполнения для данного N?

11 голосов | спросил CodeYogi 15 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 15 Sep 2015 17:59:19 +0300 2015, 17:59:19

2 ответа


11

Было бы больше pythonic использовать встроенную функцию sum, а не писать самостоятельно:

sum(xrange(num, limit, num))

Однако это по-прежнему слишком много работает - вам не нужно делать цикл for для суммарной суммы, есть решение с закрытой формой:

def sum_multiples(n, lim):
    last = (lim - 1) // n
    return n * (last) * (last+1) // 2

РЕДАКТИРОВАТЬ: Кроме того, не вызывайте свою собственную функцию sum, так как вы скрываете ее встроенную.

def sum35(limit):
    return (sum_multiples(3, limit) +
            sum_multiples(5, limit) -
            sum_multiples(15, limit))

print sum35(10)   # 23
print sum35(1000) # 233168
ответил tzaman 15 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 15 Sep 2015 18:16:53 +0300 2015, 18:16:53
7

Ваш код Python выглядит хорошо, но ваше решение может быть медленным для больших значений. Вы можете вычислить сумму кратных значений в O (1). Мы можем сначала заметить, что существуют термины floor(limit / num), которые делятся на num и меньше, чем limit. Наконец, мы можем вычислить результат, используя формулу суммы Гаусса.

def sum_multiples(num, limit):
  no_of_multiples = (limit - 1) // num
  return no_of_multiples * (no_of_multiples + 1) / 2 * num

Для вашего примера sum_multiples(3, 10), no_of_multiples будет 3 (это 3, 6, 9), и мы можем выразить их сумму как:

3 + 6 + 9 = 3 * (1 + 2 + 3) = 3 * ((3 * 4) / 2) 

Вы можете получить время работы в Linux с помощью утилиты time, записывающей в ваш терминал time python3 script.py например.

ответил Alex Palcuie 15 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 15 Sep 2015 18:15:59 +0300 2015, 18:15:59

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132