47597 (Механизм бектрекинга), страница 2
Описание файла
Документ из архива "Механизм бектрекинга", который расположен в категории "". Всё это находится в предмете "информатика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "рефераты, доклады и презентации", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "47597"
Текст 2 страницы из документа "47597"
a: array [1. .100] of record
cost,ves: word;
end;
sum_ves,sum_cost,max,money,level, i,n: integer;
procedure back;
begin
s [level]: =0;
b [level]: =level;
level: =level-1;
end;
function add_element (d: integer): integer;
var
i: integer;
q: boolean;
begin
repeat
q: =true;
for i: =1 to level do
if s [i] >=d then q: =false;
if q then add_element: =d
else
begin
d: =d+1;
if d>n then
begin
add_element: =0;
q: =true;
end;
end;
until q
end;
begin
clrscr;
read (n);
for i: =1 to n do
begin
writeln ('Элемент номер - ', i);
write ('Введите его вес - '); read (a [i]. ves);
write ('Введите его цену - '); read (a [i]. cost);
b [i]: =i;
end;
write ('Сколько денег в наличии - '); read (money);
clrscr;
level: =1; max: =0;
while b [1] begin {Поиск элемента не использованного на этом уровне} b [level]: =add_element (b [level]); if b [level] >0 then begin s [level]: =b [level] ; level: =level+1; sum_ves: =0; sum_cost: =0; for i: =1 to n do if s [i] <>0 then begin sum_ves: =sum_ves+a [s [i]]. ves; sum_cost: =sum_cost+a [s [i]]. cost; end; if sum_cost>money then back else if (max end else back; end; write ('Наибольший вес - ',max); end. Описанный метод выглядит достаточно специфически и кажется, что не так много задач подходят под его возможности. Однако рассмотрим задачу, которая как кажется на первый взгляд довольно далека от описанной выше. Условие: Дана фигура из картона. Можно ли её разрезать на заданные фигуры (и по форме и по размеру) Определим понятие разреза следующим образом: разрез это линия определённой длины проведённая по фигуре с началом в определённой точке и в определённом направлении. Дополнительные знания формы исходной фигуры и форм требуемых фигур позволят сократить множество допустимых разрезов и сделать его пусть большим, но конечным. Тогда задача становится задачей полного перебора. Бектрекинг накладывается на неё очень просто и естественно. Пусть мы провели очередной разрез. Проверим, дал ли он в совокупности с другими разрезами фигуру. Если да, то проверим, входит ли эта вырезанная фигура в множество искомых. Если нет, то данное множество разрезов тупиковое. Вострикова З.П. и др. "Программирование на языке "БЕЙСИК" для персональных ЭВМ". Машиностроение, 1993г. Гохман А.В. и др. "Сборник задач по математической логике и алгебры множеств", издательство Саратовского Университета, 1969г. Гусев В.В. Основы импульсной техники. М. Советское радио, 1975 Касаткин В.Н. "Информация, алгоритмы, ЭВМ", М. Просвещение, 1991г. Машовцев В.А. Вступительные экзамены по информатике // Информатика. 1997, №13 Орлов В.А. О вступительных экзаменах по информатике // Информатика, 1997, №15 Яснева Г.Г. Логические основы ЭВМ // Информатика и образование, 1998, №2 Лыскова В.Ю., Ракитина Е.А. Логика в информатике, М. Информатика и образование 1999 Шауцкова Л.З. “Решение логических задач средствами алгебры логики”, газета Информатика 1999, №5.
Заключение
Литература
