VII Международная студенческая научная конференция Студенческий научный форум - 2015

Во многих прикладных задачах требуется найти оптимальное решение среди очень большого (но конечного!) числа вариантов. Иногда удается построить это решение сразу, но в большинстве случаев единственный способ его отыскать состоит в переборе ВСЕХ возможных вариантов и сравнении их между собой. Поэтому так важно научиться строить алгоритмы ПЕРЕБОРА различных комбинаторных объектов - последовательностей, перестановок, подмножеств и т.д. Задачи о подсчете числа их возможных комбинаций и расположений с определенными условиями называются комбинаторными.

Например: Сколькими способами можно расположить в ряд три различных предмета? (предметы будем кодировать цифрами)

Ответ: (перестановки из трех элементов)

123; 132; 213; 231; 312; 321.

Классической задачей комбинаторики является задача о числе перестановок, содержание которой можно выразить вопросом: сколькими способами можно переставить n различных предметов, расположенных на n различных местах? Формула для количества различных перестановок: n!.

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

Решим следующую задачу:

Hапечатать (сгенерировать) все перестановки чисел 1..n (то есть последовательности длины n, в которые каждое из чисел 1..n входит ровно по одному разу).

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

Рассмотрим две программы генерации перестановок из n чисел: с применением рекурсии и без неё. Используя обращение к системным часам, зафиксируем время в начале и в конце работы программы, по разнице определим время работы программы. Сделаем выводы о времени работы программ и сложности поставленной задачи.

Программа №1 (с применением рекурсии):

Program laksikogr_perest;

usescrt, dos;

const n=12;

type mas=array[1..n] of byte;

var a:mas;

i,j:byte;

s:longint;

dt:integer;

h:boolean;

h0,m0,s0,hs0,h1,m1,s1,hs1:word;

procedure Recursion(k:integer);

vari,j:byte;

procedure Swap(vara,b:byte);

var p:byte;

begin

p:=a; a:=b; b:=p;

end;

begin

if k=n then begin

for i:=1 to n do write(a[i]:2);

writeln;

inc(s);

end;

for i:=k to n do

begin

Swap(a[k],a[i]);

Recursion(k+1);

Swap(a[k],a[i]);

end

end;

Begin

clrscr;

GetTime(h0,m0,s0,hs0);

for i:=1 to n do a[i]:=i;

writeln;

Recursion(1);

GetTime(h1,m1,s1,hs1);

dt:=360000*(h1-h0)+6000*(m1-m0)+100*(s1-s0)+(hs1-hs0);

writeln('Vsegoperestanovok ',s);

writeln('Time ',dt,' milisekund');

readln;

End.

Программа №2 (без применения рекурсии):

Programlaksikogr_perest;

usescrt,dos;

const n=3;

type mas=array [1..n] of integer;

var a:mas;

i,g,s,k,j,dt:integer;

h0,m0,s0,hs0,h1,m1,s1,hs1:word;

h:boolean;

Begin

clrscr;

GetTime(h0,m0,s0,hs0);

for i:=1 to n do a[i]:=i; writeln; {vvodelementovmassiva}

repeat

for i:=1 to n do write(a[i]:3);writeln; {vyvodtekuheyperestanovki}

i:=n-1; g:=1; inc(s);

while (i>0) and (a[i]>a[i+1]) dodec(i); {poiski}

ifi>0 then

begin

j:=i+1;

while (j1,5 часа

247

198

12

>8 часов

 

27464

 

>8 часов

 

3043

 

Таблица показывает, сколько времени (в миллисекундах) было затрачено на выполнение программы с рекурсией и без неё с выводом на экран и соответственно без вывода. Результаты представлены в ней. На домашнем компьютере установлена операционная система Windows 7, а на аудиторном – WindowsXp, процессор Intel Core 2 CPU 1,66Ггц.

В данном примере программа с использованием рекурсии работает гораздо медленнее, чем без её использования. Если выводить промежуточные результаты на экран, то разницы в работе алгоритмов не заметно, так как время расходуется на вывод на экран. Даже для небольшого числа элементов (начиная с 10) время работы алгоритмов оказывается ощутимым, что говорит о сложности задачи.

5

Код для цитирования: Скопировать