Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Конечные суммы вида


Автор: Cr@$h 6.5.2005, 23:25
Необходимо эффективно вычислять суммы типа: Сумма/по i от 1 до N/{i^p}, т. е. 1^p + 2^p + 3^p + ... + N^P.
Например, для p = 2 нужно вычислить: 1^2 + 2^2 + 3^2 + ... + N^2. Дело в том, что для таких сумм существуют хитрые формулы. Приведенный пример равен N(N+1)(2N+1)/6. Для p = 1 вообще имеем арифметическую прогрессию. Знаю формулы до p = 8. А вот хотелось бы для p, эдак, 100.
Может между ними существует некая рекурентная связь. Хотя, глядя, на формулы (до p = 8) не вижу такой.

Очень надо.

P. S. Интересно: (1 + 2 + 3 + ... + N )^2 = 1^3 + 2^3 + 3^3 + ... + N^3. Дальше так уже не катит

Автор: Remiznik 7.5.2005, 00:06
или я что то не догоняю или ...... но это же вроди простой цикл .....

Автор: Illuminaty 7.5.2005, 00:18
Remiznik тут все дело в слове
Цитата(Cr @ 6.5.2005, 23:25)
эффективно

Автор: Illuminaty 7.5.2005, 00:30
Cr@$h посмотри http://www.mccme.ru/olympiads/lktg/2001/bernold.htm
а вообще в Гугле попробуй поискать.
Начни с изучения этого:
Цитата
Швейцарский математик Якоб Бернулли (1654-1705) изучал свойства последовательности чисел, возникающей при суммировании степеней последовательных натуральных чисел. А именно, для любого натурального k существует — и это будет доказано на лекции — такой многочлен Sk(n), что для любого натурального n сумма k-х степеней первых n натуральных чисел равна Sk(n). Числами Бернулли Bk называют коэффициент при первой степени переменной n многочлена Sk(n). Оказывается, B1 = 1/2, а все остальные числа Бернулли с нечётными номерами равны 0. Мы выведем рекуррентное соотношение, выражающее очередное число Бернулли через предыдущие, а также формулу, выражающую коэффициенты многочлена Sk(n) через числа Бернулли. И разные другие интересные формулы.

Цитата с http://mmmf.math.msu.su/lect/lect5.html (Найдено при помощи великого Гугля) smile

Автор: Remiznik 7.5.2005, 03:53
аааа я всё понял тут ешё практакуется ручной труд ))))

Автор: Cr@$h 7.5.2005, 13:31
Спасибо за ссылки, Illuminaty. За мной не заржавеет smile

Автор: Illuminaty 7.5.2005, 13:35
Да не за что.
У меня где-то книжка по занимательной математике валялась, там подобное разобрано было, но найти не смог (книгу) smile
А зачем тебе такие суммы? (Если не секрет smile )

Автор: AISIN 11.5.2005, 19:46
Цитата(Illuminaty @ 7.5.2005, 00:18)
Remiznik тут все дело в слове
Цитата(Cr @ 6.5.2005, )
эффективно

Можно и так попробывать одновремменно с двух сторон цикл (while) побегать.
А можно и еще круче с двух сторон бежим к середине и из середины бежим к концам. На много меньше итераций получается чем в обычном цикле который тупо бежит вперед!
Illuminaty спасибо классный метод!

Автор: Cr@$h 14.5.2005, 15:04
Цитата(Illuminaty @ 7.5.2005, 14:35)
А зачем тебе такие суммы?

smile В численном анализе очень надо было. Разобрался, круто. А уже через эти формулы конечных сумм вывел собственно нужные формулы для
Сумма(i<j){i*j}, Сумма(i<j<k){i*j*k}, ... и
Сумма(i<j){i^2*j^2}, Сумма(i<j<k){i^2*j^2*k^2}, ...
AISIN, понимаешь в чем дело: начиная с некоторого момента накопленная сумма перестанет чувствовать очередное слагаемое!

Автор: Akina 14.5.2005, 15:59
Сумма i^p по i от 1 до N вычисляется полиномом степени (p+1) от N - лет 20 назад где-то видел аж с доказательством. Счас уже и не упомню где - в какой-то познавательной книжуле типа "Занимательной математики"...
Добавлено @ 15:59
Цитата(Cr @ 14.5.2005, 16:04)
начиная с некоторого момента накопленная сумма перестанет чувствовать очередное слагаемое!

Видимо, упираешься в точность...

Автор: esperant0 26.5.2005, 23:38
Сумма для большого числа слагаемых находится межуд двумя интегралами

Интеграл( x^p,0,n)<=S(X)<=Интеграл( x^p,0,n+1)

то есть

x^[n+1]/[n+1]<=S(X)<x^[n+2]/[n+2]

Автор: yaja 27.5.2005, 17:39
У меня была такая задача на acm контесте smile
Я её решал динамически, т.е. пусть нам известна формула для p (отметим, что это полином), тогда для p+1 она получается следующим образом:
1) интегрируется наш полином для p и умножаем его на (p+1)
2) нормализуем полином, т.е. делим все члены на его старший член
3) получаем полином, и в нем считаем сумму слагаемых s (она должна быть меньше 1)
4) затем к нашему полиному прибавляем (1 - s)x (там сумма всех слагаемых должна быть равна 1)
И таким образом получаем формулу для p+1, там правда такие числа получаются, что не влазит в __int64 уже при p порядка 20
Если надо кому-то реализовывать, то полином должен храниться как массив его коэф-тов в целом типе, т.е. не нормализованный, иначе траблы будут из-за маленькой точности double или float

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)