Как я могу получить математическое уравнение алгоритма Python?

Question

хорошо, поэтому я чувствую себя немного глупо, что не знаю этого, но коллега спросил, поэтому я спрашиваю здесь: я написал алгоритм python, который решает его проблему. при заданном x> 0 сложите все числа от 1 до x.

def intsum(x):
  if x > 0:
    return x + intsum(x - 1)
  else:
    return 0

intsum(10)
55

Во-первых, что это за уравнение такого типа, и как правильно получить этот ответ, поскольку с помощью какого-то другого метода явно легче?

Answer 1

Это рекурсия, хотя по какой-то причине вы обозначаете ее как факториальную.

В любом случае сумма от 1 до n также просто:

n * ( n + 1 ) / 2

(Вы можете использовать его в особых случаях, если хотите.)

Answer 2

Преобразование рекурсивно определенных последовательностей целых чисел в последовательности, которые можно выразить в замкнутой форме, является увлекательной частью дискретной математики - я искренне рекомендую Конкретная математика: основа компьютерных наук , автор Рональд Грэм , Дональд Кнут и Орен Паташник (см., Например, статью Википедия об этом).

Однако конкретная последовательность, которую вы показываете, fac(x) = fac(x - 1) + x, согласно известному анекдоту, была решена Гауссом, когда он был ребенком в первом классе - учитель дал ученикам такс суммирования чисел от 1 до 100 чтобы держать их в покое на некоторое время, но через две минуты появился молодой Гаусс с ответом 5050 и объяснением: «Я заметил, что могу сложить первое, 1 и последнее, 100, это 101; и второе , 2, и предпоследний, 99, и это снова 101, и ясно, что повторяется 50 раз, то есть, 50 раз 101, 5050 ". Не строгое доказательство, но вполне правильное и подходящее для 6-летнего ребенка; -).

Таким же образом (плюс действительно элементарная алгебра) вы можете видеть, что общий случай, как уже сказали многие, (N * (N+1)) / 2 (произведение всегда четное, поскольку одно из чисел должно быть нечетным, а другое - четным; поэтому деление на два всегда будет приводить к целому числу, по желанию, без остатка).

Answer 3

Вот как доказать закрытую форму для арифметической прогрессии

S  = 1 +   2   + ... + (n-1) + n
S  = n + (n-1) + ... +   2   + 1
2S = (n+1) + (n+1) + ... + (n+1) + (n+1)
     ^ you'll note that there are n terms there.
2S = n(n+1)
S = n(n+1)/2

Answer 4

ОП попросил в комментарии ссылку на рассказ о Гауссе как школьнике.

Он может захотеть проверить эту увлекательную статью Брайана Хейса . Это не только довольно убедительно говорит о том, что история Гаусса может быть современной выдумкой, но и показывает, как было бы довольно трудно не видеть закономерности суммирования чисел от 1 до 100. Это фактически единственный способ пропустить эти схемы чтобы решить проблему, написав программу.

В статье также говорится о различных способах суммирования арифметических прогрессий, что лежит в основе вопроса ОП. Существует также версия без рекламы здесь .

Answer 5

Мне пока не разрешено комментировать, поэтому я просто добавлю, что вам нужно быть осторожным при использовании range (), поскольку он равен 0.Вам нужно будет использовать диапазон (n + 1), чтобы получить желаемый эффект.

Извините за дублирование ...

сумма (диапазон (10))! = 55

сумма (диапазон (11)) == 55

Answer 6

Ларри очень корректен с его формулой, и это самый быстрый способ вычислить сумму всех целых чисел до n.

Но для полноты картины есть встроенные функции Python, которые выполняют то, что вы сделали, в списках с произвольными элементами. Э.Г.

• sum()

  >>> sum(range(11))
  55
  >>> sum([2,4,6])
  12
  

• или более общий, reduce()

  >>> import operator
  >>> reduce(operator.add, range(11))
  55
  

Answer 7

То, что у вас есть, называется арифметической последовательностью, и, как предлагается, вы можете вычислить ее напрямую, без дополнительных затрат, которые могут возникнуть в результате рекурсии.

И я бы сказал, что это домашнее задание, несмотря на то, что вы говорите.

Answer 8

Учтите, что N + 1, N-1 + 2, N-2 + 3 и т. Д. Все складываются в одно и то же число, и существует примерно N / 2 таких случаев (точно N / 2, если N даже).