Рекурсивные алгоритмы — это алгоритмы, решающие необходимые проблемы при помощи сведения их к решению набора аналогичных задач, но в более сжатом представлении.
Введение
Задачи из области дискретной математики иногда можно свести к задаче перебора разных комбинаций объектных конфигураций и методике выбора наилучшей из них, удовлетворяющей условиям рассматриваемой задачи. То есть владение алгоритмами генерации самых известных комбинаторных конфигураций считается обязательным аспектом, позволяющим успешно решать такие задачи. Необходимо также иметь информацию о числе разных вариантов для всех типов комбинаторных конфигураций, поскольку это даёт возможность реальной оценки вычислительной трудоёмкости найденного алгоритмического решения поставленных задач перебором вариантов и возможности его применения для решения конкретной задачи при учёте её размеров. Помимо этого, в этих случаях может оказаться полезным суметь для всех комбинаторных конфигураций осуществлять такие операции:
- По исходной конфигурации находить очередную конфигурацию, идущую вслед за ней в лексикографической очерёдности.
- Находить нумерацию текущей конфигурации в перечне лексикографических номеров всех конфигураций.
- Определять по нумерации конфигурацию, которая ему соответствует.
Приведённый выше перечень подзадач в программировании как относят к следующим комбинаторным конфигурациям:
- Перемещение компонентов множества.
- Перестановки сочетаний из n компонентов множества по k компонентов.
- Другие возможные перестановки.
Оптимальным для решения таких задач является использование рекурсивных алгоритмов, которые позволяют решить подобные проблемы в более краткой и прозрачной форме.
Генерация k-элементных подмножеств
В комбинаторике подобные подмножества определяются как сочетания из n компонентов по k компонентов и обозначаются Cnk. В силу характера компьютерных арифметических операций, не всегда есть возможность точного вычисления величины Cnk, даже если она не превышает максимально допустимое целочисленное значение. Если величина n фиксирована, то максимальное значение количества сочетаний будет достигнуто при k = n/2. Если предположить, что за временной интервал, предоставленный для решения задачи, возможно пересмотреть приблизительно 106 вариантов, то значит генерацию всех комбинаций из n компонентов для всякого постоянного значения k можно выполнять для n ≤ 24.
Как правило, генерацию всех подмножеств, состоящих из k компонентов, выполняют в лексикографическом порядке, поскольку это не ведёт ни к более сложному алгоритму, ни к возрастанию трудоёмкости его вычислений. Порядок подмножеств считается лексикографическим, если для любой пары подмножеств выполняется требование, что раньше должна быть выполнена генерация того из них, из индексов компонентов которого возможно сформировать более маленькое число из k знаков в n-ричной системе счисления (если n меньше десяти, то в десятичной системе).
Сформируем рекурсивный алгоритм решения такой задачи. Свести такую задачу к задаче с меньшей размерностью, можно следующим образом. В качестве первого компонента подмножества можно выбрать любые компоненты, то есть с самого первого и кончая (n – k + 1)-м компонентов. После фиксации индекса первого компонента подмножества, нужно сделать выбор k – 1 компонент из оставшегося набора компонентов, имеющих индексы больше первого. Затем процедура повторяется. Выбор последнего компонента означает достижение последнего рекурсивного уровня и можно приступить к обработке найденного подмножества. То есть выполнить его анализ или отправить на печать. В приведённой ниже программе, массив а состоит из значений компонентов начального множества и заполняется в произвольном порядке. В массиве р формируется текущее сочетание из k компонентов.
const nmax = 24;
type list = array[1..nmax] of integer;var k, i,j,
n,q : integer; a, p : list;procedure print(k : integer);
var i:integer;begin for j:=1 to k do write(p[j]:4);
writelnend;{print}
procedure cnk(n, k : integer);
procedure gen(m, L : integer);
var i:integer;
begin if m=0 then print(k) else for i:=L to n-m+1 do begin
p[k-m+1]:=a[i];
gen(m-1,i+1)
end
end;{gen}
begin {cnk} gen(k,1)end;
{cnk}begin {main} readln(n, k);
for i:=1 to n do a[i]:=i;{заполнить массив можно и по-другому}
cnk(n, k)
end.
Следует отметить, что непосредственно генерируются сочетания при помощи рекурсивной подпрограммы gen. У нё есть такие параметры:
- m определяет число компонентов из множества, подлежащих выборке.
- L определяет начальный элемент исходного множества, с которого нужно начать выборку этих m компонентов.
Отметим, что как раз вложенная структура, которая описывает процедуры cnk и gen, даёт возможность не транслировать при вызовах рекурсии величины n и k. А из главной ветви программы выполнять обращение к операции cnk с параметрами, которые соответствуют условиям задачи, без анализа подробностей её решения.
Генерация всех подмножеств данного множества
Очень часто нет информации о том, какое количество компонентов начального множества должно войти в определяемое подмножество, что означает необходимость выполнения перебора всего набора подмножеств. Но, когда необходимо определить самое маленькое подмножество, то есть имеющее минимальное количество компонентов, то оптимальной будет организация перебора так, чтобы вначале осуществлялась проверка всех подмножеств, которые состоят из единственного компонента, потом из двух и так далее. В таком случае, первое подмножество, которое удовлетворяет условиям задачи, и станет итоговым, что означает окончание процесса перебора. Когда будет получено очередное сочетание, вместо его распечатки следует выполнить процедуру его проверки, определяющую значение флага. В этом случае начальная процедура выглядит таким образом:
procedure gen(m, L:integer);
var i:integer;
begin
if m=0 then
begin
check(p, k,flag);
if flag then exit
end
else...
