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);