C++ C++ C# C# ASP.NET Security ASP.NET Security ASM ASM Скачать Скачать Поиск Поиск Хостинг Хостинг  
  Программа для работы с LPT портом...
Язык: .NET — ©Alexey...
  "ASP.NET Atlas" – AJAX в исполнении Micro...
Язык: .NET — ©legigor@mail.ru...
  "Невытесняющая" Многопоточность...
Язык: C/C++ — ©...
  Update World C++: Сборник GPL QT исходников
  Весь сайт целиком можно загрузить по ссылкам из раздела Скачать
Дебетовая карта Home Credit [CPS] RU

 Вычисление суммы степеней последовательных чисел без использования функции pow() или ее аналогов. / Математика / Алгоритмы

Вычисление суммы степеней последовательных чисел без использования функции pow() или ее аналогов.

Автор:Агабабов Виктор

Теоретическое обоснование.

Мы будем рассматривать задачу вычисления суммы степеней

	S(n,k)=S i=1..n ik    (1)

При этом суммирование в формуле (1) можно начинать с нуля, что не изменяет значения суммы, но зато облегчает некоторые математические преобразования.

В дальнейшем нам понадобятся числа Стирлинга второго рода, которые показывают, сколькими способами можно разбить n элементное множество на k непересекающихся подмножеств. Для вычисления чисел Стирлинга второго рода не существует закрытой формулы, как и для биноминальных коэффициентов, но есть простая рекурсивная формула:

	{n, k} = k * {n - 1, k} + {n - 1, k - 1}
	{n, 0} = {n == 0}							(2)
	{0, n} = (n == 0)
	{n, m} = 0; m > n

Начальные условия очевидны. Нет способов разбить n элементное множество на 0 множеств. А пустое множество можно разбить лишь на 0 пустых множеств.

Рекурсивный шаг тоже можно получить из соответствующих комбинаторных рассуждений (более подробно [1], [2]). Последнее условие легко получается из предущего, так как после итерирования рекурсии получается сумма типа {0, n}, где n > 0, то есть сумма 0, которая очевидно равна 0. С помощью данной формулы мы можем легко вычислять.

Основное достоинство этих чисел заключается в том, что с их помощью можно представить обычную степень, как сумму факториальных степеней:

	x m = Si=0m-1 x (m - i) * {m, i}, (2)
где
	x (m)= x(x - 1)(x - 2)*...*(x - m + 1) (3)

Теперь разделив и умножив на (x - m)!, получим биноминальные коэффициенты C(x,m), следовательно получаем следующую формулу:

	x m = Si=0m-1 C(x, i) * (m - i)! * {m, i} (4)

Итак, нам осталось лишь вычислить сумму этих чисел:

	S(n,m) = 1n + ... + m n
	S(n,m) = Si (Sj ((C(i, j) * (n - j)! * {n, j})) (5)

Представляя биноминальные коэффициенты в рекурсивном виде получим следующую формулу:

	C(n,k) = C(n - 1, k) + C(n - 1, k - 1) (рекурсивная форма)
	C(n,k) = C(n - 1, k) + C(n - 1, k - 1) =
	       = C(n - 1, k - 1) + C(n - 2, k - 1) + C(n - 2, k) + ... =
	       = Sm=0n-1 (C(m, k - 1))    (6)

Меняя порядок суммирования в формуле (5) и вынося числа Стирлинга и факториал за сумму и просуммировав отдельно биноминальные коэффиценты, получим одинарную сумму:

	S(n,m) = Sj ((n - j)! * {n, j} * Si (C(i,j))) =
	       = Sj ((n - j)! * {n, j} * C(m + 1, n - j + 1))

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

	T(n) = O(n3)

Это не очень быстрый алгоритм. Однако в [3] существует нерекурсивная формула, которая позволяет вычислять числа Стирлинга за время меньшее квадратного. Следовательно, уменьшится время для вычисления всей суммы.

Приложение 1.(Исходники)

Функция для вычисления биноминальных коэффициентов

> unsigned long binom(int n, int k)
> {
>  unsigned long t = 1;
>  for (int i = 0; i < k; i++)
>  {
>    t = (t * (n - i)) / (i + 1);
>  }
>  return t;
> }

Функция для вычисления чисел Стирлинга второго рода

> unsigned long stirling2(int n, int m)
> {
>  if (n && !m)
>  {
>    return 0;
>  }
>  if (!n)
>  {
>    return (!m);
>  }
>  return m * stirling2(n - 1, m) + stirling2(n - 1, m - 1);
> }

Функция для вычисления факториала

> unsigned long factorial(int n)
> {
>  unsigned long q = 1;
>  for (int i = 2; i <= n; i++)
>  {
>    q *= i;
>  }
>  return q;
> }

И конечная функция для вычисления суммы

> unsigned long sumNK(int n, int k)
> {
>  unsigned long s = 0;
>  for (int i = 0; i < k; i++)
>  {
>    s += binom(n + 1, k - i + 1) * stirling2(k, i + 1) * factorial(k - i);
>  }
>  return s;
> }

Эта функция не дает ощутимого результата в общем случае, однако данное решение является красивым и в иных случаях может дать гораздо лучшие результаты, чем решения в лоб.

Литература.

  1. Р. Грэхем, Д. Кнут, О. Поташник "Конкретная Математика"
  2. Д. Кнут "Искусство Программирования" том 1.
  3. В. Яблонский "Введение в Дискретную Математику".




Дебетовая карта Home Credit [CPS] RU