Обратные перестановки. Алгоритмы

Каждая перестановка имеет себе обратную. Например, имеем перестановку

 

, для нее обратной будет перестановка

.

 

Алгоритм I. (Обратная перестановка на месте). Заменим перестановку X [1], X [2] … X[n], которая является перестановкой чисел {1, 2, …, n }, обратной перестановкой.

I1. [Инициализация]. Присвоить m n, j -1.

I2. [Следующий элемент]. Присвоить i X[m]. Если i < 0, перейти к шагу I5 (этот элемент уже был обработан).

I3. [Обратить один элемент]. (В этот момент j < 0 и i = X [ m ]. Если m не является наибольшим элементом своего цикла, то первоначальная перестановка давала
X [- j ] = m). Присвоить X [ m ] j, j - m, m i, i X [ m ].

I4. [Конец цикла?]. Если i > 0, перейти к шагу I3 (этот цикл не закончен); иначе — присвоить i j. (В последнем случае первоначальная перестановка давала X [- j ] = m, где m — наибольший элемент в его цикле.)

I5. [Сохранить окончательное значение]. Присвоить X [ m ] - i. (Первоначально X [- i ] было равно m).

I6. [Цикл по m ]. Уменьшить m на 1. Если m > 0, перейти к I2, в противном случае работа алгоритма заканчивается.

 

Пример. Найти обратную перестановку для строки: 6 2 1 5 4 3.

Решение.  В качестве второй строки запишем порядковые номера цифр строки, получим:

 

Переставим строки местами, получим: . Переставим столбцы местами, сохраняя порядок элементов заданной строки, получим . Таким образом, перестановка (3 2 6 4 5 1) является результатом обращения исходной строки 6 2 1 5 4 3.

 

 

Алгоритм J. (Обращение на месте). Этот алгоритм дает такой же результат, как и алгоритм I, но на основании другого подхода.

J1. [Сделать все величины отрицательными]. Присвоить X[k] -X[k] для 1 £ k £ n. Присвоить также m n.

J2. [Инициализация j ]. Присвоить j m.

J3. [Нахождение отрицательного элемента]. Присвоить i X [ j ]. Если i > 0, то присвоить j i и повторить этот шаг.

J4. [Обращение]. Присвоить X [ j ] X [- i ], X [- i ] m.

J5. [Цикл по m ]. Уменьшить m на 1, если m > 0, вернуться к шагу J2. В противном случае работа алгоритма заканчивается.

 

Хотя алгоритм J невероятно изящен, анализ показал, что алгоритм I намного его превосходит. На самом деле оказывается, что среднее время выполнения алгоритма J, в сущности, пропорционально n ln (n), а среднее время выполнения алгоритма I пропорционально n.

Запись перестановки в циклическом виде не единственна; состоящую из шести элементов перестановку (1 6 3) (4 5) (2) можно записать как (4 5) (3 1 6) (2) и другими способами, что вносит некоторую неопределенность.  Поэтому важно рассмотреть каноническую форму циклического представления, которая является единственной.

 

Для получения канонической формы перестановки выполним следующие действия:

1. Вписать в перестановку пропущенные единичные циклы.

2. Внутри каждого цикла поместить на первое место наименьшее число.

3. Расположить циклы в порядке убывания их первых элементов.

Пример. Для циклической перестановки (3 1 6) (5 4) найти каноническое

          представление.

 

Решение. (3 1 6) (5 4) (2)    ®   (1 6 3) (4 5) (2)   ®    (4 5) (2) (1 6 3).

 

Важным свойством канонической формы является то, что скобки можно опустить, а затем восстановить единственным образом.

Последовательность действий следующая:

1. Выбираем направление просмотра строки слева направо.

2. Расставляем “(“ в начале строки и “)” в конце строки.

3. Ищем минимальное число и, если перед ним еще не стоит “(“ ставим “(“

4. Перед “(“ ставим “)”.

5. Переходим к анализу нерассмотренных еще элементов строки.

6. Если еще не все элементы рассмотрены, переход к п. 3.

7. Конец алгоритма.

 

Пример. Написать каноническую форму для перестановки (6 4 3) (5 1 2)

Решение.

1. (6 4 3) (5 1 2)

2. (3 6 4) (1 2 5)

3. 3 6 4 1 2 5.

Обратный процесс введения скобок циклов будет следующим (3 6 4) (1 2 5).

 

 

Рекурсия

 

Объект называется рекурсивным, если он содержит сам себя или определен с помощью самого себя [2].

Очевидно, что мощность рекурсии связана с тем, что она позволяет определить бесконечное множество объектов с помощью конечного высказывания.

Точно так же бесконечные вычисления можно описать с помощью конечной рекурсивной программы, даже если эта программа не содержит явных циклов. Лучше всего использовать рекурсивные алгоритмы в тех случаях, когда вычисляемая функция или обрабатываемая структура данных определены с помощью рекурсии.

С процедурой принято связывать некоторое множество локальных объектов, то есть переменных, констант, процедур, которые определены локально внутри рекурсивной процедуры, а вне ее не существуют или не имеют смысла. Каждый раз, когда такая процедура вызывается рекурсивно, для нее создается новое множество локальных переменных. Хотя они имеют те же имена, что и соответствующие элементы множества локальных переменных, созданного при предыдущем обращении к этой же процедуре, их значения различны. При работе с рекурсивными процедурами следует помнить правило: идентификаторы всегда ссылаются на множество переменных, созданное последним. То же правило относится к параметрам процедуры.

Подобно циклическим алгоритмам, рекурсивные процедуры могут привести к бесконечным вычислениям. Поэтому необходимо решить проблему окончания работы процедур. На практике нужно обязательно убедиться, что наибольшая глубина рекурсии не только конечна, но и достаточно мала. Дело в том, что при каждом рекурсивном вызове процедуры Р выделяется память для размещения ее переменных. Кроме локальных переменных нужно еще сохранять текущее состояние вычислений.

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

 

Пример. Реализовать вычисление факториала n! рекурсивно. Решение оформим программой на языке С++.

 

// Вычисление факториала n! рекурсивно

 

#include "stdafx.h"

#include <iostream>

 using namespace std;

#include <conio.h>

 int fact(int i);

 

 

int _tmain(int argc, _TCHAR* argv[])

{

int n;

 

cout<<"Enter n = ";

cin>>n;    

  

cout<<" \n n! = "<<fact(n)<<"\n";       

 

getch();

return 0;

}

 

int fact(int i)

{

if(i<=1) return 1;

return i*fact(i-1);

}

 

 

Информационные структуры