Основы программирования. Файлы. Рекурсия - 28 стр.

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

Составители: 

Рубрика: 

30
procedure MoveTown(n,f,t,w: integer);
begin
if n=0 then exit;
MoveTown(n-1,f,w,t);
MoveDisk(f,t);
MoveTown(n-1,w,t,f);
end;
Процедура
MoveDisk, обеспечивающая перемещение одного диска, либо вы-
дает текстовую информацию о том, с какого на какой диск было осуществлено
перемещение, либо перемещает диск графически, меняя рисунок с изображения-
ми штырей и дисков, подобный приведенному в начале данного примера.
Нетрудно показать, что глубина рекурсии равна
n, а количество перемеще-
ний дисков составляет
12 −
n
.
Пример 2. Сгенерировать все перестановки длины
n.
Заполним массив тождественной перестановкой. Будем менять первый эле-
мент с каждым последующим, включая себя, после этого совершать те же дейст-
вия с оставшейся частью массива и менять элементы обратно:
for i:=1 to n do
begin
Swap(A[i],A[1]);
...
Swap(A[i],A[1]);
end;
В итоге каждый элемент побывает на первом месте. Вместо многоточия вы-
зовем аналогичную процедуру для элементов
со второго по последний. Таким об-
разом, мы реализовали следующую идею: получить все перестановки n элементов
можно, поставив на первое место каждый элемент и дописав к нему все переста-
новки из оставшихся элементов. Очень важным шагом здесь является последний
оператор цикла, возвращающий обратно элемент, переставленный на первом шаге
цикла. Это гарантирует, что
в начале каждой итерации цикла мы имеем дело с од-
ной и той же перестановкой.
Поскольку рекурсивные вызовы необходимо совершать для элементов с ин-
дексами от 2 по
n, затем от 3 по n и т.д., в качестве параметра рекурсивной проце-
дуры будем передавать
k – начальный индекс переставляемого элемента (таким
образом, перестановка будет совершаться для элементов с номерами от k до n). В
результате наша рекурсивная процедура примет вид:
procedure Permutation0(k: integer);
var i: integer;
begin
for i:=k to n do
begin

Страницы