- •Проектирование полнопереборных алгоритмов
- •Содержание
- •1.1. Основные понятия и определения
- •1100, 1010, 1001, 0110, 0101, 0011.
- •1.2. Общие подходы к порождению комбинаторных объектов
- •1.3. Алгоритмы порождения подмножеств
- •1.4. Алгоритмы порождения сочетаний
- •1.5. Алгоритмы порождения перестановок
- •1.6. Алгоритм порождения размещений
- •1.7. Алгоритмы порождения композиций
- •1.8. Алгоритм порождения разбиений
- •2. Проектирование алгоритмов, основанных на полном переборе траекторий задачи выбора
- •2.1. Понятие задачи выбора
- •2.2. Комбинаторный поиск
- •Поиск с возвращением
- •Метод решета
- •2.3. Использование алгоритмов порождения элементарных комбинаторных объектов при проектировании полнопереборных алгоритмов решения задач выбора
- •3. Некоторые вопросы теории сложности
- •4. Задания для самостоятельной работы
- •4.1. Порождение подмножеств
- •4.2. Порождение перестановок
- •4.3. Порождение сочетаний и размещений
- •4.4. Порождение композиций и разбиений
- •4.5. Решение комбинаторных задач
- •4.6. Проектирование полно переборных алгоритмов
- •Список литературы
- •Генерация случайных чисел
- •Приложение 2 функции времени языка Turbo Pascal
- •Текст программы на языке Turbo Pascal реализующей точный алгоритм решения задачи о рюкзаке
- •Проектирование полнопереборных алгоритмов
- •308012, Белгород, ул. Костюкова, 46.
Приложение 2 функции времени языка Turbo Pascal
Процедура GetTime.
Назначение. Возвращает установленное в операционной системе текущее время.
Описание. GetTime (Var час, минута, секунда, cот_сек: word).
Модуль. Dos.
Примечание. Возвращаемые параметры принимают следующие значения: "час" - от 0 до 23, "минута" - от 0 до 59, "секунда" - от 0 до 59 и "сот_сек" (сотая доля секунды) - от 0 до 99.
Процедура GetDate.
Назначение. Возвращает текущую дату, установленную в операционной системе.
Описание. GetDate (Var год, месяц, число, день_недели: word).
Модуль. Dos.
Примечание. Возвращаемые параметры принимают следующие значения: "год" - от 1980 до 2099, "месяц" - от 1 до 12, "число" - от 1 до 31 и "день_недели" - от 0 до 6 (где 0 соответствую воскресенью).
Процедура SetTime.
Назначение. Устанавливает в операционной системе текущее время.
Опасение. SetTime(Var час, минута, секунда, сот_сек: word).
Модуль. Dos.
Примечание. Возвращаемые параметры принимают следующие значения: "час" - от 0 до 23, "минута" - от 0 до 59, "секунда"- от 0 до 59 и "сот_сек" (сотая доля секунды) - от 0 до 99.
Процедура SetDate.
Назначение. Устанавливает текущую дату в операционной системе.
Описание. SetDate(Var год, месяц, число, день_недели: word).
Модуль. Dos.
Примечание. Возвращаемые параметры принимают следующие значения: "год" - от 1980 до 2099, "месяц" - от 1 до 12, "число" - от 1 до 31 и "день_иедели" - от 0 до 6 (где 0 соответствует воскресенью). Если дата указана неверно, то запрос игнорируется.
Приложение 3
Текст программы на языке Turbo Pascal реализующей точный алгоритм решения задачи о рюкзаке
В приложении представлено два варианта реализации точного алгоритма решения задачи о рюкзаке на языке Turbo Pascal. Алгоритм основан на полном переборе траекторий задачи, т.е. переборе всех подмножеств предметов. В первом варианте для организации перебора траекторий взят алгоритм порождения подмножеств в порядке двоичного счета (алгоритм 1), во втором – алгоритм порождения подмножеств в порядке минимального изменения (алгоритм 3). Второй вариант реализации более предпочтителен, т.к. при подсчете функционала, т.е. при нахождении суммарной массы и стоимости предметов, составляющих текущее подмножество, удалось избавиться от циклических действий (см. реализацию функции Func в первом и втором варианте).
Вариант 1.
uses CRT;
const maxN=20; {Максимальное число предметов}
type t_el_MS=record
M:real;{Масса предмета}
S:real {Стоимость предмета}
end;
t_MS=array[0..maxN-1] of t_el_MS;
t_b =array[0..maxN] of byte;
var n:byte; {Число предметов}
MS:t_MS; {Масса и стоимость предметов}
b:t_b; {Текущее подмножество предметов}
b1:t_b; {Подмножество выбранных предметов}
SM,SS:real; {Суммарная масса и стоимость предметов,
составляющих текущее подмножество}
maxSM,maxSS:real; {Суммарная масса и стоимость
выбранных предметов}
i:byte;
procedure Init(var n:byte; var MS:t_MS;
var maxSM:real);
var i:byte;
begin
write('Число предметов (не более ',maxN:2,') =');
readln(n);
writeln('Введите массу каждого предмета:');
for i:=0 to n-1 do
begin
write(i+1:2,': '); readln(MS[i].M)
end;
writeln('Введите стоимость каждого предмета:');
for i:=0 to n-1 do
begin
write(i+1:2,': '); readln(MS[i].S)
end;
write('Максимальная суммарная масса выбранных предметов =');
readln(maxSM);
end;
procedure Print(n:byte; b1:t_b;
maxSM,maxSS:real);
var i:byte;
begin
if maxSS>0 then
begin
writeln('Суммарная масса предметов со следующими номерами:');
for i:=0 to n-1 do
if b1[i]=1 then write(i+1:3);
writeln;
writeln('не превышает установленного предела равного', maxSM:9:3,',');
writeln('а суммарная стоимость этих предметов максимальна и равна ', maxSS:9:3);
end;
end;
procedure Repl(b:t_b; var b1:t_b);
var i:byte;
begin
for i:=0 to n-1 do b1[i]:=b[i]
end;
procedure Func(n:byte; MS:t_MS; b:t_b;
var SM,SS:real);
var i:byte;
begin
SM:=0; SS:=0;
for i:=0 to n-1 do
if b[i]=1 then
begin SM:=SM+MS[i].M; SS:=SS+MS[i].S end;
end;
begin
ClrScr;
writeln('ЗАДАЧА О РЮКЗАКЕ');
Init(n,MS,maxSM);
maxSS:=0;
for i:=0 to n do b[i]:=0;
while b[n]<>1 do
begin
Func(n,MS,b,SM,SS);
if (SM<=maxSM) and (SS>maxSS) then
begin maxSS:=SS; Repl(b,b1) end;
i:=0;
while B[i]=1 do
begin B[i]:=0; i:=i+1 end;
B[i]:=1
end;
Print(n,b1,maxSM,maxSS);
end.
Вариант 2.
uses CRT;
const maxN=20; {Максимальное число предметов}
maxStack=20; {Максимальный размер стека}
type t_el_MS=record
M:real;{Масса предмета}
S:real {Стоимость предмета}
end;
t_MS=array[1..maxN] of t_el_MS;
t_q =array[1..maxN] of byte;
t_S =record
St:array[1..maxStack] of byte;
t: byte
end;
var n:byte; {Число предметов}
MS:t_MS; {Масса и стоимость предметов}
q:t_q; {Текущее подмножество предметов}
q1:t_q; {Подмножество выбранных предметов}
SM,SS:real; {Суммарная масса и стоимость предметов,
составляющих текущее подмножество}
S:t_S; {Стек}
maxSM,maxSS:real; {Суммарная масса и стоимость
выбранных предметов}
i,j:byte;
procedure Init(var n:byte; var MS:t_MS;
var maxSM:real);
var i:byte;
begin
write('Число предметов (не более ',maxN:2,') =');
readln(n);
writeln('Введите массу каждого предмета:');
for i:=1 to n do
begin write(i:2,': '); readln(MS[i].M) end;
writeln('Введите стоимость каждого предмета:');
for i:=1 to n do
begin write(i:2,': '); readln(MS[i].S) end;
write('Максимальная суммарная масса выбранных предметов =');
readln(maxSM);
end;
procedure Print(n:byte; q1:t_q;
maxSM,maxSS:real);
var i:byte;
begin
if maxSS>0 then
begin
writeln('Суммарная масса предметов со следующими номерами:');
for i:=1 to n do
if q1[i]=1 then write(i:3);
writeln;
writeln('не превышает установленного предела равного', maxSM:9:3,',');
writeln('а суммарная стоимость этих предметов максимальна и равна ', maxSS:9:3);
end;
end;
procedure Repl(q:t_q; var q1:t_q);
var i:byte;
begin
for i:=1 to n do q1[i]:=q[i]
end;
procedure Func(n:byte; MS:t_MS; q:t_q;
num:byte; var SM,SS:real);
begin
if q[num]=0 then
begin SM:=SM-MS[i].M; SS:=SS-MS[i].S end
else
begin SM:=SM+MS[i].M; SS:=SS+MS[i].S end;
end;
{Помещение в стек}
procedure PutStack(var S:t_S; el:byte);
begin
S.t:=S.t+1;
if S.t>maxStack then
begin writeln('Стек переполнен'); Halt end;
S.St[S.t]:=el
end;
{Извлечение из стека}
procedure GetStack(var S:t_S; var el:byte);
begin
if S.t=0 then
begin writeln('Стек пуст'); Halt end;
el:=S.St[S.t];
S.t:=S.t-1
end;
{Проверка стека на пустоту}
function EmptyStack(S:t_S):boolean;
begin EmptyStack:=S.t=0 end;
{Инициализация стека}
procedure InitStack(var S:t_S);
begin S.t:=0 end;
begin
ClrScr;
writeln('ЗАДАЧА О РЮКЗАКЕ');
Init(n,MS,maxSM);
maxSS:=0;
SM:=0;
SS:=0;
InitStack(S);
for i:=n downto 1 do
begin q[i]:=0; PutStack(S,i) end;
while not EmptyStack(S) do
begin
GetStack(S,i);
q[i]:=1-q[i];
Func(n,MS,q,i,SM,SS);
if (SM<=maxSM) and (SS>maxSS) then
begin maxSS:=SS; Repl(q,q1); end;
for j:=i-1 downto 1 do PutStack(S,j)
end;
Print(n,q1,maxSM,maxSS);
end.
Учебное издание
Муромцев Виктор Владимирович