| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Конечные суммы вида |
| Автор: 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 тут все дело в слове
|
| Автор: Illuminaty 7.5.2005, 00:30 | ||
| Cr@$h посмотри http://www.mccme.ru/olympiads/lktg/2001/bernold.htm а вообще в Гугле попробуй поискать. Начни с изучения этого:
Цитата с http://mmmf.math.msu.su/lect/lect5.html (Найдено при помощи великого Гугля) |
| Автор: Remiznik 7.5.2005, 03:53 |
| аааа я всё понял тут ешё практакуется ручной труд )))) |
| Автор: Cr@$h 7.5.2005, 13:31 |
| Спасибо за ссылки, Illuminaty. За мной не заржавеет |
| Автор: Illuminaty 7.5.2005, 13:35 |
| Да не за что. У меня где-то книжка по занимательной математике валялась, там подобное разобрано было, но найти не смог (книгу) А зачем тебе такие суммы? (Если не секрет |
| Автор: AISIN 11.5.2005, 19:46 | ||||
Можно и так попробывать одновремменно с двух сторон цикл (while) побегать. А можно и еще круче с двух сторон бежим к середине и из середины бежим к концам. На много меньше итераций получается чем в обычном цикле который тупо бежит вперед! Illuminaty спасибо классный метод! |
| Автор: Cr@$h 14.5.2005, 15:04 | ||
Сумма(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
Видимо, упираешься в точность... |
| Автор: 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 контесте Я её решал динамически, т.е. пусть нам известна формула для p (отметим, что это полином), тогда для p+1 она получается следующим образом: 1) интегрируется наш полином для p и умножаем его на (p+1) 2) нормализуем полином, т.е. делим все члены на его старший член 3) получаем полином, и в нем считаем сумму слагаемых s (она должна быть меньше 1) 4) затем к нашему полиному прибавляем (1 - s)x (там сумма всех слагаемых должна быть равна 1) И таким образом получаем формулу для p+1, там правда такие числа получаются, что не влазит в __int64 уже при p порядка 20 Если надо кому-то реализовывать, то полином должен храниться как массив его коэф-тов в целом типе, т.е. не нормализованный, иначе траблы будут из-за маленькой точности double или float |