Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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.

Существует две стратегии решения задач данного типа. При первой - мы генерируем вариант, а затем определяем его пригодность. При второй - вариант генерируется по одному элементу, и проверка пригодности осуществляется после добавления каждого элемента. Поскольку вычислительная сложность задач данного типа - nⁿ, то есть при увеличении размерности задачи время вычислений возрастает как nⁿ, вторая стратегия предпочтительней.

Общий алгоритм решения задачи с использованием полного перебора по первой стратегии может быть представлен следующим образом:

цикл-пока еще есть варианты

генерировать вариант

если вариант удовлетворяет условию,

то обработать набор

все-если

все-цикл

Для генерации вариантов используют либо вложенные циклы, применение которых существенно уменьшают универсальность программы, либо программно-реализуемый счетчик, который в каждом разряде считает от минимального до максимального значений элементов в данной позиции. Каждое состояние такого счетчика соответствует варианту. Для генерации следующего варианта в младший разряд счетчика добавляют 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. Задача о расстановке ферзей.

Разработка программы решения начинается с выявления некоторых деталей.

1. Определим форму представления данных задачи. С первого взгляда кажется, что доска должна представляться матрицей, а местоположение ферзей - индексами в матрице. Однако при некотором размышлении можно заменить, что доска может быть представлена вектором, в котором индекс соответствует номеру столбца доски, а значение - номеру строки.

   Рис.8.

2. Определим, что для векторного представления означает "бьет". Ферзь "бьет" другую фигуру, если она расположена на той же диагонали, вертикали или горизонтали, т.е. если

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.

Недостаток примененного метода, как уже говорилось, заключается в m^m-ой зависимости времени выполнения от значения 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

Характеристики

Список файлов книги