Метод 2. Алгоритм Дейкстры построения следующей по алфавиту перестановки

Шаг 1. Выдать первую по алфавиту перестановку p= 1, 2, 3, ... N.

Шаг 2. Пусть p = a_1, a₂, ..., a_N — перестановка, полученная на предыдущем шаге.

i := N – 1;

Найти первую с конца пару элементов перестановки, упорядоченную по возрастанию:

пока a_i > a_i+1 выполнять

i := i – 1;

конец пока

Найти наименьший элемент a_j, такой что a_j > a_i при j>i:

j := i + 1;

пока a_j > a_i выполнять

j := j + 1;

j := j – 1;

a_j и a_i поменять местами в перестановке p:

x := a_i;

a_i := a_j;

a_j := x;

Отсортировывать хвост перестановки, начиная с (i+1)-го элемента, в порядке возрастания:

цикл по k от 1 до ((N-i) div 2) с шагом 1

x := a_i+k;

a_i+k := a_N-k+1;

a_N-k+1 := x;

конец цикла

Выдать на экран или в файл полученную перестановку p.

Шаг 3. если перестановка p равна N, N–1,...,3, 2, 1 ,

то конец работы алгоритма

иначе перейти на Шаг 2.

Метод 3. Инверсионный

Шаг 1.

Построить начальную таблицу инверсий B длины N, состоящую из нулей: 0, 0,...,0.

Выдать на экран или в файл соответствующую ей перестановку: 1, 2, 3, ..., N.

Шаг 2.

Пусть B = b₁, b₂, ..., b_N – таблица инверсий, построенная на предыдущем шаге. Тогда следующая таблица инверсий получается из нее прибавлением к ней единицы:

i := N;

flag := истина;

пока flag выполнять

x := b_i + 1;

если x > N – i

то

начало

b_i := 0;

i := i–1;

конец

иначе

начало

b_i := x;

flag := ложь;

конец

конец пока

Построить перестановку, соответствующую полученной таблице инверсий:

Пусть А — массив длины N, заполненный 0 (0 обозначает пустое место).

цикл по i от 1 до N с шагом 1 выполнять

//для каждого i пропустить b_i пустых мест

j := 0;

k := 0;

пока j  b_i выполнять

k := k + 1;

если A[k] = 0

то j := j + 1;

конец пока

//и поместить i на следующее пустое место:

A[k] := i;

конец цикла

Выдать полученную перестановку на экран или в файл.

Требования к реализации

Язык программирования, на котором следует выполнять работу – С.

Лабораторная работа № 6. Поиск подстроки в строке

Задание

Написать программу, которая находит первое вхождение подстроки в за­дан­ную строку. Использовать алгоритм Бойера-Мура поиска подстроки в стро­ке, описанный в [1, 2].

Входные данные

На вход программе подаются две строки s и q. Длина s больше либо равна длине q.

Выходные данные

Нужно выдать на экран номер позиции элемента в строке s, с которого начи­нается первое вхождение строки q в строку s. Если q не является подстрокой s, то вывести 0.

Метод. Алгоритм Бойера-Мура

Пусть L — длина строки s, а M — длина строки q.

Шаг 1. Построить по q таблицу сдвигов D[0..255]такую, что:

если литера, имеющая код i, не входит в q,

то D[i]:= М

иначе D[i]:= М – j,

где код q[j] равен i, 0<j<M, и нет такого k (j<k<M), что

q[k] = q[j]

Шаг 2. Совместить начало строки q c началом строки s.

Пусть i — текущее положение первого элемента строки q

относительно строки s.

i := 1;

Шаг 3. Пусть j – счетчик элементов строки q, а k – счетчик элементов строки s.

j := M;

k := i + M – 1;

Шаг 4. Сравнить поэлементно q и s:

пока (q[j] = s[k]) и ( j > 0) выполнять

//сдвинуться на одну позицию влево:

j := j – 1;

k := k – 1;

конец пока

если j = 0

// первое вхождение строки q в строку s найдено

то

начало

выдать i;

перейти на Шаг 6;

конец

иначе перейти на Шаг 5.

Шаг 5. Вычислить новый сдвиг начала образца q относительно оcновной строки s:

i := i + D[ код(s[i + M – 1])];

если i + M –1  L //не вышли за границу строки s

то переход на Шаг 3

иначе выдать 0;

// – вхождение строки q в строку s не найдено

Шаг 6. Конец работы алгоритма

Требования к реализации

Язык программирования, на котором следует выполнять работу – С.

Лабораторная работа № 7. Простые сортировки

Задание

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

Использовать два из следующих алгоритмов, описанных в [1, 2]:

• сортировка выбором,

• сортировка вставками,

• сортировка обменом (шейкер-сортировка),

• сортировка подсчетом.

Входные данные

Длина массива задается либо в программе константой, либо вводится с клавиатуры. Исходный массив заполняется программой с помощью датчика случайных чисел.

Выходные данные

Нужно выдать на экран элементы исходного массива, а затем с новой строки выдать элементы этого массива после применения к нему алгоритма сортировки

Методы

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

Пусть А – массив длины N, содержащий целые числа, который нужно отсортировать. Описанная ниже процедура Обмен(i, j) меняет местами элементы массива c номерами i и j.

процедура Обмен (i, j)

// i и j – номера элементов массива A

начало процедуры

// Пусть x — вспомогательная переменная, посредством

// которой данные элементы меняются местами

x := A[i];

A[i]:= A[j];

A[j]:= x;

конец процедуры