Мішатронік

Нахождение числа сочетаний

Эту формулу несложно вывести. Расставить n предметов в ряд можно n! способами. Рассмотрим все n! расстановок и будем считать, что первые k предметов в ряду мы выбрали, а оставшиесяn - k предметов -- нет. Тогда каждый способ выбрать k предметов мы посчитали k!(n - k)! раз, поскольку k выбранных предметов можно переставить k! способами, а n - k невыбранных -- (n - k)! способами. Поделив общее количество перестановок на количество повторов каждой выборки, получим число выборок: C_n^k = .

Наивный метод

Как же вычислить значение C_n^k по данным n и k? Воспользуемся выведенной формулой. Функция factorial(n) возвращает факториал числа n, а функция C(n,k) возвращает значение C_n^k.

int factorial(int n)
{
 int f=1;
 for(int i=2;i<=n;++i)
 f=f*i;
 return f;
}

int C(int n, int k)
{
 return factorial(n)/factorial(k)/factorial(n-k);
}

Данный алгоритм понятен, очень быстр (его вычислительная сложность O(n), поскольку вычисление значения n! требует n - 1 умножение), использует ограниченный размер дополнительной памяти. Но у него есть существенный недостаток: он будет корректно работать только для небольших значений n и k. Дело в том, что величина n! очень быстро растет с увеличением n, например, значение 13! = 6 227 020 800 превосходит максимальное возможное значение, которое можно записать в 32-разрядном целом числе, а величина

Рекурсивный метод

Действительно, выбрать из n предметов k можно C_n^k способами. Пометим один из данных n предметов. Тогда все выборки можно разбить на две группы: в которые входит помеченный предмет (их будет C_{n - 1}^{k - 1}) и не содержащие помеченного предмета (таких выборок будет C_{n - 1}^k).

Добавив к этой формуле краевые значения: C_nⁿ = C_n⁰ = 1 (выбрать все предметы или не выбрать ни одного предмета можно единственным способом), можно написать рекурсивную функцию вычисления числа сочетаний:

int C(int n, int k)
{
 if (k==0 || k==n)
 return 1;
 else
 return C(n-1,k-1)+C(n-1,k);
}

При таком решении задачи проблем с переполнением не возникнет: если значение конечного ответа не приводит к переполнению, то поскольку при его нахождении мы суммируем меньшие натуральные числа, все промежуточные значения, возвращаемые функцией C(n,k) тоже не будут приводить к переполнению, и такая программа, например, сможет вычислить значение C₃₀¹⁵.

Но это решение крайне плохо тем, что работать оно будет очень долго, поскольку функция C(n,k) будет вызываться многократно для одних и тех же значений параметров n и k. Например, если мы вызовем функцию C(30,15), то она вызовет функции C(29,14) и C(29,15). Функция C(29,14) вызовет функции C(28,13) и C(28,14), а C(29,15) вызовет функции C(28,14) и C(28,15). Мы видим, что функция C(28,14) будет вызвана дважды. С увеличением глубины рекурсии количество повторяющихся вызовов функции быстро растет: функция C(27,13) будет вызвана три раза (дважды ее вызовет функция C(28,14) и еще один раз ее вызовет C(28,13) и т. д.

При этом каждая функция C(n,k) может либо вернуть значение 1, либо вернуть сумму результатов двух других рекурсивных вызовов, а, значит, любое значение, которое вернула функция C(n,k) получается сложением в различных комбинациях чисел 1, которыми заканчиваются все рекурсивные вызовы. Значит, при вычислении C_n^k инструкция return 1 в приведенной программе будет выполнена ровно C_n^k раз, то есть сложность такого рекурсивного алгоритма для вычисления C_n^k не меньше, чем само значение C_n^k.

Метод динамического программирования

Полученная числовая таблица, составленная из значений C_n^k, в которой каждый элемент равен сумме двух элементов, стоящих над ним, называется треугольником Паскаля.

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

int C(int n, int k)
{
 int B[n+1][n+1]; // Создаем массив B из n+1 строки
 for(int i=0;i<=n;++i) // Заполняем i-ю строку массива
 {
 B[i][0]=1; // На концах строки стоят единицы
 B[i][i]=1;
 for(int j=1;j<i;++j)
 { // Заполняем оставшиеся элементы i-й строки
 B[i][j]=B[i-1][j-1]+B[i-1][j];
 }
 }
 return B[n][k];
}

Приведенный алгоритм для вычисления C_n^k требует объем памяти O(n²) и такая же его временная сложность (для заполнения одного элемента массива требуется O(1) операций, всего же элементов в массиве O(n²)).

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

Тем не менее, приведенный алгоритм тоже имеет небольшие недостатки. Мы вычисляем значения всех элементов последней строки, хотя нам необходим только один из них -- B[n][k]. Аналогично, в предпоследней строке нас интересуют только два элемента -- B[n-1][k-1] и B[n-1][k], в строке, стоящей над ней -- три элемента, и т. д., в то время, как мы вычисляем все элементы во всех строках. Кроме того, мы не используем почти половину созданного массива B[n+1][n+1], а именно все элементы, стоящие выше главной диагонали. От этих недостатков можно избавиться, более того, можно уменьшить объем используемой памяти до O(n), идея для построения такого алгоритма будет изложена в разделе «Маршруты на плоскости».

Если же в программе часто возникает необходимость вычисления числа сочетаний C_n^k для каких-то ограниченных значений n, то лучше всего создать глобальный массив для хранения всевозможных значений C_n^k для нужных нам значений n, заполнить его в начале программы, а затем сразу же брать значение числа сочетаний из этого массива, не вычисляя его каждый раз заново.

Промежуточные итоги

Составим план решения задачи методом динамического программирования.

1. Записать то, что требуется найти в задаче, как функцию от некоторого набора аргументов (числовых, строковых или еще каких-либо).

    

2. Свести решение задачи для данного набора параметров к решению аналогичных подзадач для других наборов параметров (как правило, с меньшими значениями). Если задача несложная, то полезно бывает выписать явное рекуррентное соотношение, задающее значение функции для данного набора параметров.

    

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

    

4. Создать массив (или другую структуру данных) для хранения значений функции. Как правило, если функция зависит от одного целочисленного параметра, то используется одномерный массив, для функции от двух целочисленных параметров -- двумерный массив и т. д.

    

5. Организовать заполнение массива с начальных значений, определяя очередной элемент массива при помощи выписанного на шаге 2 рекуррентного соотношения или алгоритма.

Далее мы рассмотрим несколько типичных задач, решаемых при помощи динамического программирования.