RECURS (Методичка С++), страница 2
Описание файла
Файл "RECURS" внутри архива находится в папке "METODY". Документ из архива "Методичка С++", который расположен в категории "". Всё это находится в предмете "информатика" из 2 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "информатика" в общих файлах.
Онлайн просмотр документа "RECURS"
Текст 2 страницы из документа "RECURS"
begin if length(st)=0 then f_value:=true
else if (st[1]<='9') and (st[1]>='0') then f_value:=f_char(copy(st,2,length(st)-1))
else f_value:=false;
end;
function f_char;
begin if length(st)=0 then f_char:=true
else if (st[1]<='Z') and (st[1]>='A') then f_char:=f_value(copy(st,2,length(st)-1))
else f_char:=false;
end;
begin writeln('Введите строку'); readln(s);
if f_char(s) then writeln(' Строка корректна')
else writeln('Строка не корректна');
end.
Данная программа построена не удачно, так как размер фрейма активации V»260 байт. Для уменьшения размера фрейма следует подумать об изменении способа передачи параметра. Действительно, если гарантировать, что исходная строка изменяться не будет, то ее можно передавать по ссылке. Переход к следующему символу можно осуществить, добавив еще один параметр - индекс, передаваемый по значению. Размер фрейма активации при этом сократится (V»10). Кроме этого, в программе использована более удобная проверка (с использованием множеств).
program ex2;
var s:string;
function f_char(var st:string;i:word):boolean;forward;
function f_value(var st:string;i:word):boolean;
begin if i>length(st) then f_value:=true
else if (st[i] in ['0'..'9'])then f_value:=f_char(st,i+1)
else f_value:=false;
end;
function f_char;
begin if i>length(st) then f_char:=true
else if (st[i] in ['A'..'Z','a'..'z']) then f_char:=f_value(st,i+1)
else f_char:=false;
end;
begin writeln('Введите строку');
readln(s);
if f_char(s,1) then writeln('Строка корректна')
else writeln(' Строка не корректна');
end.
Таким образом, по возможности, в рекурсивных подпрограммах при передаче строк и массивов следует использовать передачу по ссылке, что приводит к уменьшению размера фрейма активации.
Пример 7. Из заданного массива, завершающегося нулем, распечатать сначала положительные значения, а затем - отрицательные в любом порядке.
Структура рекурсивной подпрограммы имеет в общем случае вид, представленный на рисунке 6. Операторы, которые на схеме помечены как "операторы после вызова" будут выполняться после возврата управления из рекурсивно вызванной подпрограммы. Если попытаться изобразить последовательность действий, то она будет выглядеть так, как показано на рисунке 7.
Рис 6
Рис. 7.
Таким образом, сначала выполняются операторы до вызова всех активаций, затем, при достижении условия выхода, нерекурсивная часть, а затем, в порядке, обратном порядку вызова, операторы, записанные после рекурсивного вызова (!!!). Используя это свойство, построим решение следующим образом: в области до вызова запрограммируем печать положительных чисел, в области после вызова - печать отрицательных чисел, а нерекурсивная часть будет содержать вывод звездочек.
program ex;
type mas=array[1..10] of real;
var x:mas;
i:integer;
procedure print(var x:mas;i:integer);
begin if x[i]=0 then writeln('***')
else
begin
if x[i]>0 then writeln(i,x[i]);
print(x,i+1); {рекурсивный вызов}
if x[i]<0 then writeln(i,x[i]);
end
end;
begin i:=0;
repeat i:=i+1;read(x[i]) until x[i]=0;
readln;
print(x,1);
end.
Примечание. Обратите внимание, что значение i при каждом вызове свое, и оно не меняется все время обработки данного вызова: одно и то же, как до вызова, так и после него.
Глава 2. Полный и ограниченный перебор. Рекурсия при программировании ограниченного перебора.
2.1. Понятие полного перебора. Основные приемы его осуществления.
Существует класс задач, в которых необходимо из некоторого количества вариантов выбрать наиболее подходящий. Для таких задач далеко не всегда удается найти алгоритм, который позволил бы получить решение без анализа всех или большого количества вариантов, т.е. без осуществления перебора.
В качестве примера рассмотрим классическую "задачу о сдаче".
Пример 1. Разработать программу выдачи сдачи минимальным количеством монет при ограниченном количестве монет каждого достоинства в кассе.
Попытка использовать известный алгоритм, при котором сдача выдается начиная с монет большего достоинства и включает максимальное возможное количество монет каждого достоинства, в этом случае не дает оптимального решения. Например, если необходимо выдать сдачу 47 копеек, и в кассе имеется достаточное количество монет достоинством 1,2,3, 5,10,15,20 копеек, то алгоритм работает: 47=20*2+5*1+2*1 - 4 монеты. Но при отсутствии в кассе 5 копеечных монет вариант 47=15*3+2*1 ( 4 монеты) лучше варианта 47=20*2+3*2+1*1 (5 монет). При таких условиях для решения этой задачи используется метод перебора вариантов.
К задачам, при решении которых используется перебор, относятся также задачи из области искусственного интелекта, решения которых ищутся методом "проб и ошибок"., например, задача о расстановке n ферзей на доске n*n таким образом, чтобы они не били друг друга. К этой же группе относятся задачи, в которых требуется получить все возможные перестановки каких-то элементов, например, все перестановки букв от A до F.
Существует две стратегии решения задач данного типа. При первой - мы генерируем вариант, а затем определяем его пригодность. При второй - вариант генерируется по одному элементу, и проверка пригодности осуществляется после добавления каждого элемента. Поскольку вычислительная сложность задач данного типа - nn, то есть при увеличении размерности задачи время вычислений возрастает как nn, вторая стратегия предпочтительней.
Общий алгоритм решения задачи с использованием полного перебора по первой стратегии может быть представлен следующим образом:
цикл-пока еще есть варианты
генерировать вариант
если вариант удовлетворяет условию,
то обработать набор
все-если
все-цикл
Для генерации вариантов используют либо вложенные циклы, применение которых существенно уменьшают универсальность программы, либо программно-реализуемый счетчик, который в каждом разряде считает от минимального до максимального значений элементов в данной позиции. Каждое состояние такого счетчика соответствует варианту. Для генерации следующего варианта в младший разряд счетчика добавляют 1 и "протряхивают" межразрядные переносы.
Пример 2. Написать программу, которая генерирует следующие комбинации: 1111, 1112, 1113, 1121, 1122, 1123, 1131, 1132, 1133, 1211, ..., 3333.
В процессе решения необходимо программно реализовать 4-разрядный счетчик, который в каждом разряде будет считать от 1 до 3.
program ex;
const a:array[1..4] of byte=(1,1,1,1);
var i:integer;
begin
while a[1]<4 do {условие "сброса" счетчика}
begin for i:=1 to 4 do write(a[i],' '); writeln; {вывод комбинации}
a[4]:=a[4]+1; {добавление 1 в последний разряд}
for i:=4 downto 2 do { анализ и осуществление переносов}
if a[i]>3 then
begin a[i]:=1; a[i-1]:=a[i-1]+1; end;
end
end.
Этот прием можно использовать и для решения других задач данного класса.
Пример 3. Задача о расстановке ферзей.
Разработка программы решения начинается с выявления некоторых деталей.
-
Определим форму представления данных задачи. С первого взгляда кажется, что доска должна представляться матрицей, а местоположение ферзей - индексами в матрице. Однако при некотором размышлении можно заменить, что доска может быть представлена вектором, в котором индекс соответствует номеру столбца доски, а значение - номеру строки.![]()
Рис.8.
-
Определим, что для векторного представления означает "бьет". Ферзь "бьет" другую фигуру, если она расположена на той же диагонали, вертикали или горизонтали, т.е. если
pole[ j ]=pole[ i ] или | pole[ j ]-pole[ i ] | =| j- i |
Полностью решение выглядит следующим образом:
program ex;
type p=array[1..100] of integer;
var pole:p; i,m:integer;
function new_r(m:integer;pole:p):boolean; {функция проверки комбинации}
var i,j:integer;
begin new_r:=true;
for i:=1 to m-1 do
for j:=i+1 to m do
if (pole[i]=pole[j]) or (abs(pole[j]-pole[i])=j-i) then
begin new_r:=false;
exit;
end;
end;
function Variant(m:integer; var pole:p):boolean; {генератор вариантов}
var i:integer;
begin
pole[m]:=pole[m]+1; {добавление единицы в младший разряд счетчика}
for i:=m downto 2 do {обработка переносов}
if pole[i]>m then
begin pole[i]:=1;
pole[i-1]:=pole[i-1]+1;
end;
if pole[1]<=m then Variant:=true {фиксируем наличие ранее не рассмотренных}
else Variant:=false; {вариантов}
end;
begin writeln('Введите размер доски'); readln(m);
for i:=1 to m do pole[i]:=1; {исходная комбинация}
repeat
if New_r(m,pole) then
begin for i:=1 to m do write(pole[i]:2); writeln; end;
until not Variant(m,pole);
end.
Недостаток примененного метода, как уже говорилось, заключается в mm-ой зависимости времени выполнения от значения m.
2.2. Использование рекурсии при реализации ограниченного перебора.
Попробуем сократить количество рассматриваемых вариантов за счет как можно более раннего отбрасывания неперспективных комбинаций. На рис.9 представлена часть дерева промежуточных и завершенных вариантов.
Рис. 9.
Рис. 10.
program ex;
type p=array[1..100] of integer;
var pole:p; k,integer;
function new_r(n:integer;pole:p):boolean;
var j:integer;
begin new_r:=true;
for j:=1 to n-1 do
if (pole[j]=pole[n]) or (abs(pole[j]-pole[n])=n-j) then
begin new_r:=false;
exit;
end;
end;
procedure ferz(n,m:integer; var pole:p);
var i:integer;
begin
if n=m+1 then
