Как я получаю Математическое уравнение Алгоритма Python?
хорошо, таким образом, я чувствую себя немного глупым для того, чтобы не знать это, но коллега спросил, таким образом, я спрашиваю здесь: Я записал алгоритм Python, который решает его проблему. данные x> 0 добавляют все числа вместе от 1 до x.
def intsum(x):
if x > 0:
return x + intsum(x - 1)
else:
return 0
intsum(10)
55
сначала то, каков этот тип уравнения, является этим и что корректный путь состоит в том, чтобы получить этот ответ, поскольку это - ясно более легкое использование некоторого другого метода?
8 ответов
Это рекурсия, хотя по какой-то причине вы обозначаете ее как факториал.
В любом случае сумма от 1 до n также просто:
n * (n + 1) / 2
(Вы можете использовать специальный регистр для отрицательных значений, если хотите.)
Учтите, что N + 1, N-1 + 2, N-2 + 3 и так далее в сумме дают одно и то же число, и есть примерно N / 2 таких случаев (ровно N / 2, если N четное).
Преобразование рекурсивно определенных последовательностей целых чисел в те, которые могут быть выражены в замкнутой форме, - увлекательная часть дискретной математики - я настоятельно рекомендую Конкретная математика: основа компьютерных наук Рональда Грэма, Дональда Кнута и Орена Паташника (см., Например, запись в википедии об этом).
Однако конкретная последовательность, которую вы показываете, fac (x) = fac (x - 1) + x , согласно известному анекдоту, была решена Гауссом, когда он был ребенком в первом классе - - учитель дал ученикам такск суммирования чисел от 1 до 100, чтобы они успокоились на некоторое время, но через две минуты появился молодой Гаусс с ответом, 5050, и объяснением: «Я заметил, что могу суммировать первое, 1, и последнее, 100, это 101; второе, 2, и предпоследнее, 99, и это снова 101; и, очевидно, это повторяется 50 раз, так что 50 раз 101, 5050 ". Не строгие доказательства, но вполне правильные и подходящие для 6-летнего ребенка ;-).
Таким же образом (плюс действительно элементарная алгебра) вы можете видеть, что общий случай, как многие уже сказали, (N * (N + 1)) / 2 (произведение всегда четное, так как одно из чисел должно быть нечетным, а одно четным; поэтому деление на два всегда дает целое число, по желанию, без остатка).
Вот как доказать закрытую форму для арифметической прогрессии
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
OP попросил в комментарии ссылку на рассказ о Гауссе, когда он был школьником.
Он может захотеть прочитать эту увлекательную статью Брайана Хейса . Это не только довольно убедительно предполагает, что история Гаусса может быть современной выдумкой, но и показывает, как было бы довольно сложно не увидеть закономерности, участвующие в суммировании чисел от 1 до 100. Фактически, единственный способ пропустить эти закономерности - это заключается в том, чтобы решить проблему, написав программу.
В статье также говорится о различных способах суммирования арифметических прогрессий, что лежит в основе вопроса OP. Здесь также есть версия без рекламы .
Ларри очень корректен в своей формуле, и это самый быстрый способ вычислить сумму всех целых чисел до n.
Но для полноты картины, есть встроенные функции Python, которые выполняют то, что вы сделали, на списках с произвольными элементами. Например,
То, что у вас есть, называется арифметической последовательностью, и, как предлагается, вы можете вычислить ее напрямую, без дополнительных затрат, которые могут возникнуть в результате рекурсии.
И я бы сказал, что это домашнее задание, несмотря на то, что вы говорите.
Мне пока не разрешено комментировать, поэтому я просто добавлю, что вам нужно быть осторожным в использовании range(), поскольку его база равна 0. Вам нужно использовать range(n+1), чтобы получить желаемый эффект.
Извините за дублирование...
sum(range(10)) != 55
sum(range(11)) == 55