Оригинальный DVD-ROM: eXeL@B DVD !
eXeL@B ВИДЕОКУРС !

ВИДЕОКУРС ВЗЛОМ
выпущен 2 сентября!


УЗНАТЬ БОЛЬШЕ >>
Домой | Статьи | RAR-cтатьи | FAQ | Форум | Скачать | Видеокурс
Новичку | Ссылки | Программирование | Интервью | Архив | Связь

ПРОГРАММИРОВАНИЕ НА C и С++



Давно заметил, что всё-таки языки С/C++ это не самый лучший вариант программирования под Windows. Сейчас появилась масса более современных и удобных языков, например тот же Python - кроссплатформенный язык, очень легок в изучение. Я его изучил буквально за несколько дней по этому курсу - ссылка. Автор постарался, там видеоуроки на удивление легкие и понятные.

Вычисление суммы степеней последовательных чисел без использования функции 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. В. Яблонский "Введение в Дискретную Математику".



<< ВЕРНУТЬСЯ В ПОДРАЗДЕЛ

<< ВЕРНУТЬСЯ В ОГЛАВЛЕНИЕ




Материалы находятся на сайте https://exelab.ru/pro/



Оригинальный DVD-ROM: eXeL@B DVD !


Вы находитесь на EXELAB.rU
Проект ReactOS