
C/C++
Написать код на Python
335, г

В принципе, несложно, но абсолютное значение суммы растёт очень быстро. При n = 3 это уже 17-й порядок. При n = 7 цифры результата занимают полторы строки.
P.S. И хорошенько запомните пример ниже. Это то, как не надо реализовывать вычисления в программе. Пока остаётся время, подробно разберём, почему.
Вот кусок г... хм... пусть, просто кода:
1) Рекурсивное вычисление факториала. На видеокурсах какой-то дилетант сказал так делать, потому что это была единственная строчка кода, запомнившаяся ему из учебника 1970-х, и теперь все прочие дилетанты так делают.
Никогда не вычисляйте факториал таким образом. Например, onlinegdb даёт всего 1000 на глубину вызовов, и поэтому уже на 999! вместо своего факториала вы получите примерно следующее:
Traceback (most recent call last):
File "/home/main.py", line 30, in <module>
print(naiveFact(999))
File "/home/main.py", line 28, in naiveFact
def naiveFact(n): return 1 if n < 2 else n * naiveFact(n - 1)
File "/home/main.py", line 28, in naiveFact
def naiveFact(n): return 1 if n < 2 else n * naiveFact(n - 1)
File "/home/main.py", line 28, in naiveFact
def naiveFact(n): return 1 if n < 2 else n * naiveFact(n - 1)
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded in comparison
Хвостовые оптимизации Питон на onlinegdb делать не умеет, поэтому нет способа избежать переполнения стека на больших факториалах в такой реализации.
2) Избегайте целочисленных умножений, это очень дорого (а деление ещё в разы дороже). Например, зачем каждый раз вычислять полный факториал 2k²+1, когда вы уже вычислили его для 2(k-1)²+1? Надо просто домножить предыдущий факториал на оставшиеся множители.
3) Возведение в степень - это совсем дорого. В хорошей реализации возведение в степень k - это от (log₂(k)) до (2·log₂(k)) умножений, а в наивной - это (k - 1) умножений. Тем более, нет смысла возводить -1 в степень k, т.к. результатом может быть только 1 или -1, в зависимости от чётности k. Все нормальные алгоритмисты держат переменную "знак" и меняют её значение на противоположное в каждой итерации цикла. И никаких умножений тут не нужно, конечно. Арифметическая операция смены знака выполняется за долю такта (а умножение требует несколько тактов и плохо параллелится).
def partialFact(start, end):
prod = start
for m in range(start + 1, end):
prod *= m
return prod
n = int(input())
acc = 0
positive = False
kk, fact = 1, 1
for k in range(n):
step = 4 * k + 2
fact *= partialFact(kk + 1, kk + step + 1)
kk += step
acc += fact if positive else -fact
positive = not positive
print(acc)
P.S. И хорошенько запомните пример ниже. Это то, как не надо реализовывать вычисления в программе. Пока остаётся время, подробно разберём, почему.
Вот кусок г... хм... пусть, просто кода:
def Factorial(n):
if n == 1:
return 1
return n * Factorial(n-1)
n = 6
print((-6+ ((-1)**n)*Factorial(2*n*n+1))*n/2)
Что в нём плохо, помимо того, что он вместо суммы ряда вычисляет лишь последний его член, т.е. попросту, не работает?1) Рекурсивное вычисление факториала. На видеокурсах какой-то дилетант сказал так делать, потому что это была единственная строчка кода, запомнившаяся ему из учебника 1970-х, и теперь все прочие дилетанты так делают.
Никогда не вычисляйте факториал таким образом. Например, onlinegdb даёт всего 1000 на глубину вызовов, и поэтому уже на 999! вместо своего факториала вы получите примерно следующее:
Traceback (most recent call last):
File "/home/main.py", line 30, in <module>
print(naiveFact(999))
File "/home/main.py", line 28, in naiveFact
def naiveFact(n): return 1 if n < 2 else n * naiveFact(n - 1)
File "/home/main.py", line 28, in naiveFact
def naiveFact(n): return 1 if n < 2 else n * naiveFact(n - 1)
File "/home/main.py", line 28, in naiveFact
def naiveFact(n): return 1 if n < 2 else n * naiveFact(n - 1)
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded in comparison
Хвостовые оптимизации Питон на onlinegdb делать не умеет, поэтому нет способа избежать переполнения стека на больших факториалах в такой реализации.
2) Избегайте целочисленных умножений, это очень дорого (а деление ещё в разы дороже). Например, зачем каждый раз вычислять полный факториал 2k²+1, когда вы уже вычислили его для 2(k-1)²+1? Надо просто домножить предыдущий факториал на оставшиеся множители.
3) Возведение в степень - это совсем дорого. В хорошей реализации возведение в степень k - это от (log₂(k)) до (2·log₂(k)) умножений, а в наивной - это (k - 1) умножений. Тем более, нет смысла возводить -1 в степень k, т.к. результатом может быть только 1 или -1, в зависимости от чётности k. Все нормальные алгоритмисты держат переменную "знак" и меняют её значение на противоположное в каждой итерации цикла. И никаких умножений тут не нужно, конечно. Арифметическая операция смены знака выполняется за долю такта (а умножение требует несколько тактов и плохо параллелится).
Sniper Killer
Ну да.. Мой ошибочный... Но оставлю для истории...
def Factorial(n):
if n == 1:
return 1
return n * Factorial(n-1)
n = 6
print((-6+ ((-1)**n)*Factorial(2*n*n+1))*n/2)
Похожие вопросы
- Написать код на языке си
- Помогите пожалуйста написать код.(C++)
- Написал код для языка C, но работает не правильно
- Написать код на языке C++
- Написать код для задачи C++
- Задание на c++ ответить на вопросы и написать код
- Помогите пожалуйста написать код на c++, выводящий имя, фамилию и дату рождения нескольких человек
- Написать код на языке Си
- Нужно написать код на с++
- Написать код для задачи на C++