Сортировка простыми включениями

В этом методе элементы массива условно разделяются на готовую последовательность a ₁,..., a_{i -1} и входную последовательность a ₁,..., a_n. На каждом шаге, начиная с i = 2 и увеличивая i на единицу, берется i -й элемент x = a_i входной последовательности и вставляется в готовую последовательность после элемента, меньшего, чем x.

При поиске подходящего места чередуют сравнения и пересылки, то есть как бы «просеивают» x, сравнивая его с очередным элементом a_j и либо вставляя x, либо пересылая a_j направо и передвигаясь налево. «Просеивание» может закончиться при двух различных условиях:

1. Найден элемент a_j меньше, чем x.

2. Достигнут левый конец готовой последовательности.

Для проверки окончания «просеивания» можно воспользоваться либо двойной проверкой с объединением логической операцией, либо приемом фиктивного элемента, – «барьера». В этом случае устанавливают «невидимый барьер» a ₀ = x с расширением диапазона индексов в описании a до 0.. n. При этом убирается она проверка, но добавляется одно присваивание.

Вариант сортировки по возрастанию приведен на рис.10.1.

Рис.10.1. Пример сортировки простыми включениями.

Сортировка бинарными включениями

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

Хотя число сравнений и уменьшится, но количество перестановок и их порядок по сравнению с рис.8.1 не изменятся.

Сортировка простым выбором

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

 

1. Выбирается наименьший элемент;

2. Он меняется местами с первым элементом;

3. Меняется на наименьший из оставшихся второй, третий и так далее, элемент.

 

Вариант сортировки приведен для тех же исходных данных на рис.10.2.

Рис.10.2. Пример сортировки простым выбором.

Сортировка методом пузырька

Метод пузырька основан на сравнении и обмене двух соседних пар элементов, поэтому его иногда еще называют методом простого обмена. Если массив элементов расположить вертикально, а значение элемента сопоставить с «весом» пузырька в резервуаре с водой, то каждый проход по массиву приводит к «всплыванию пузырька» на соответствующий его весу уровень, как изображено на рис.10.3.

Рис.10.3. Пример сортировки методом пузырька.

Так как три последних прохода никак не влияют на порядок расположения элементов, то обычно запоминается, проводился ли на данном проходе какой-либо обмен. Если нет, то алгоритм сортировки заканчивается. Это относится и к следующему методу.

Метод шейкер - сортировки

При использовании метода пузырька возникает асимметрия, связанная с направлением сортировки. Один неправильно расположенный «пузырек» в «тяжелом» конце отсортированного массива всплывет на место за один проход, а неправильно расположенный элемент в «легком» конце будет опускаться на свое место только на один шаг на каждом проходе. Для устранения данной асимметрии и используют метод шейкер - сортировки, в котором направление проходов меняется на каждом шаге (от англ. shake – трясти), как изображено на рис.10.4.

Рис.10.4. Пример шейкер - сортировки.

Более сложные типы сортировок массивов элементов в данной лабораторной работе не рассматриваются.

Варианты заданий приведены в табл.10.1.

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

 

Таблица 10.1. Варианты заданий

№ вар.	Метод сортировки	Максимальное кол-во элементов	Направление сортировки	Тип сортируемых элементов
	Простые включения		по возрастанию	целый
	Простые включения с барьером		по убыванию	вещественный
	Простой выбор		по возрастанию	вещественный
	Бинарные включения		по убыванию	целый
	Метод пузырька		по возрастанию	литерный
	Шейкер - сортировка		по убыванию	целый
	Простые включения с барьером		по возрастанию	целый
	Шейкер - сортировка		по возрастанию	литерный
	Простые включения		по убыванию	вещественный
	Простой выбор		по убыванию	литерный
	Шейкер - сортировка		по убыванию	вещественный
	Метод пузырька		по убыванию	целый
	Простые включения с барьером		по убыванию	вещественный
	Простые включения		по возрастанию	литерный
	Простой выбор		по возрастанию	целый
№ вар.	Метод сортировки	Максимальное кол-во элементов	Направление сортировки	Тип сортируемых элементов
	Шейкер - сортировка		по убыванию	вещественный
	Бинарные включения		по убыванию	литерный
	Простые включения с барьером		по возрастанию	целый
	Метод пузырька		по возрастанию	вещественный
	Простой выбор		по убыванию	целый
	Простые включения		по убыванию	вещественный
	Метод пузырька		по убыванию	целый
	Шейкер - сортировка		по возрастанию	целый
	Простые включения с барьером		по убыванию	вещественный
	Простые включения		по возрастанию	целый
	Шейкер - сортировка		по убыванию	литерный
	Метод пузырька		по возрастанию	вещественный
	Простой выбор		по возрастанию	целый
	Бинарные включения		по убыванию	вещественный
	Простые включения с барьером		по возрастанию	литерный

 

Лабораторная работа № 8.
Подпрограммы – функции

Целью данной работы является ознакомление с использованием подпрограмм – функций.

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

В подпрограммах могут вычисляться несколько значений, например преобразование матрицы, тогда это будут подпрограммы - процедуры. Если же в подпрограмме вычисляется единственное значение, то используются подпрограммы – функции. Как следствие, работа с функциями и процедурами в языке Паскаль различна:

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

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

3. Из основной программы обращение к подпрограмме – функции производится так же, как и к стандартным функциям, то есть указанием в выражении имени и в скобках аргументов.

Например, чтобы вычислить выражение

,

достаточно определить оператор

S=F(N)*F(M)/F(N+M),

при этом подпрограмму F можно записать в разделе описания функций следующим образом:

 

Function F(K: integer): real;

Var Fak:real;

Begin

Fak:=1;

if K>1 then

for I:=2 to K do

Fak:=Fak*I;

F:=Fak

end;

 

В лабораторной работе необходимо определить общую формулу для вычисления всех выражений. В программе вычисляются три значения X, Y, Z с использованием одной подпрограммы - функции. Ее аргументами будут являться как простые переменные, так и массивы:

 

A = { 0,12; 0,8; 0,2; 0,38; 0,11 } N =5

B = { 1,5; 0,09; 0,82; 1,13 } N =4

C = { 0,85; 1,4; 1,12; 3,24 } N =4

D = { 0,25; 0,21; 0,12; 0,39 } N =4

E = { 2,2; 3,1; 1,8 } N =3

 

Верхние границы зависят от размера массивов N.

Использование массивов как параметров функции в данной работе обязательно.

Варианты заданий приведены в табл.11.1.

Таблица 11.1. Варианты заданий

№ вар.	Значение X	Значение Y	Значение Z
№ вар.	Значение X	Значение Y	Значение Z
№ вар.	Значение X	Значение Y	Значение Z
№ вар.	Значение X	Значение Y	Значение Z

 

Лабораторная работа № 9.
Подпрограммы – процедуры

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

При обращении к подпрограмме – процедуре просто указывается ее имя со списком фактических параметров. Примером стандартных процедур могут быть подпрограммы ввода - вывода writeln, readln и другие.

 

Написать программу с использованием подпрограммы-процедуры, вычисляющую три вектора или матрицы X, Y, Z, являющиеся комбинацией трех векторов по два:

,

если заданы исходные вектора:

 

A = {3; 0; -1; 5; 7}

B = {8; 4.2; 8.8; 5.5}

C = {-1; 6; -1.8; 6.7}

D = {0.7; -1.1; 5.1; 6}

E = {-0.09; 10; 2.2; 4.5}

F = {5.5; 3.1; 2.4; 7}.

 

В вариантах приводится одна формула для вычисления трех массивов X, Y, Z:

,

где соответственно k = 1, 1, 2 и l = 2, 3, 3.

Например, формула с используемыми векторами A, B, C, приводит к трем матрицам (разные индексы i и j):

 

 

Во всех вариантах i и j изменяются от 1 до 4.

Варианты заданий приведены в табл.12.1.

 

Таблица 12.1. Варианты заданий

№ вар.		Используемые вектора
		А, B, C
		D, E, F
		A, C, E
		B, D, F
		B, C, D
		C, D, E
		A, B, C
		D, E, F
		B, C, D
		C, D, E
№ вар.		Используемые вектора
		A, C, E
		B, D, F
		A, B, C
		D, E, F
		B, C, D
		C, D, E
		A, C, E
		B, D, F
		A, B, C
		D, E, F
№ вар.		Используемые вектора
		B, C, D
		C, D, E
		A, C, E
		B, D, F
		F, B, C
		D, E, F
		B, C, D
		C, D, E
		A, C, E
		B, D, F

 

Лабораторная работа № 10.
Работа с файлами и строками

Целью работы является приобретение навыков работы с файловыми структурами при работе с модулем System (для Pascal ABC – PABCSystem). Модуль Dos в данной лабораторной работе не рассматривается. А так же изучаются операции работы со строками.

Прежде, чем использовать файлы, им надо поставить в соответствие файловые переменные процедурой Assign. Например:

 

Assign (f,’D:/student/002175/myfile.dat’);

Assign (f,’myfile.dat’);

 

Во втором случае файл находится в текущем каталоге. Это единственная структура, которая подчиняется непосредственно операционной системе, всё остальное (кроме комментариев) в тексте программы принадлежит правилам языка Паскаль.

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

 

Var <список_файловых_переменных>: FILE OF <тип_компонент>

 

Так как строки являются особенными структурами данных, то для их хранения используется специальное описание файловых переменных:

 

Var < имя_файловой_переменной >: text;

 

Например:

 

Var File, OutF: text;

 

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

В дальнейшем в первом случае в них можно записывать обычной процедурой Write, во втором – читать процедурой Read. Если же используются текстовые файлы, то так же можно использовать процедуры WriteLn и ReadLn.

Для процедур Write/ WriteLn и Read/ ReadLn консоль является стандартным устройством ввода-вывода, поэтому имена файлов для клавиатуры и экрана монитора можно не указывать. Во всех остальных случаях в строке ввода-вывода на первом месте должна стоять файловая переменная. Например:

 

WriteLn(OutF,’Я помню чудное мгновенье’);

 

Над символьными массивами разрешены только операции сравнения. Над строками разрешено гораздо больше операций. Они могут быть оформлены не только в виде знаков, таких как + (конкатенация), но и в форме процедур или функций.

Например, функция Copy (<строка>, <номер первого символа>, <количество символов>) позволяет копировать или выделять фрагмент строки.

Функция Pos (<искомая подстрока>, <строка>) позволяет произвести поиск определенного фрагмента в некоторой строке и определить номер символа, с которого начинается вхождение подстроки.

Функция Length (<строка>) позволяет определить не предельную, а фактическую длину строки. Результат – целое число.

Процедура Delete (<строка>, <номер первого удаляемого символа>, <количество символов>) удаляет в исходной строке фрагмент определенной длины.

Прочие функции (но не процедуры) приведены в Приложении А.

Более того, можно получить доступ к любому символу строки, указав ее в виде элемента массива с индексом. В описании строки можно указывать предельное значение количества символов, но можно и не указывать:

 

Var st,at: string;

St1,st2:string[20];

Если длина не задана, то по умолчанию (автоматически) принимается максимально возможная – 255 символов.

Задание

В данной лабораторной работе используются две программы: одна для формирования текстового файла с расширением.txt, другая для работы с ним.

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

Таблица 13.1. Варианты заданий

№ варианта	Задание
	Вывести в файл количество слов, начинающихся с разных букв, упорядоченных по алфавиту. То есть результат должен содержать таблицу, в первой графе которой название буквы, во второй – количество слов, начинающихся с этой буквы. Если слов, начинающихся с данной буквы, нет, то строка пропускается.
	Использовать шифрование методом простой перестановки с длинной блока 3. Размер текста должен быть кратен 3, в противном случае текст дополняется пробелами. В данном случае местами меняются только крайние буквы, средняя остается на месте. Пример: До шифрования:|МАМ|А М|ЫЛА| РА|МУ | После шифрования: |МАМ|М А|АЛЫ|АР | УМ|
	Подсчитать количество слов, пробелов и знаков препинания в файле. Записать результат в файл в виде «количество слов= <число>, количество пробелов= <число>, количество знаков препинания= <число>».
	Провести анализ вхождения букв начала алфавита А, Б, В, Г. То есть определить отношение появления этих букв ко всем буквам текста. Результат вывести на экран в виде таблицы с графами буква – частота появления.
	Использовать шифрование с применением шифра Цезаря с величиной сдвига 4 по алфавиту в сторону убывания. Используется кольцевой сдвиг: буква А меняется на Ь, Б – на Э, В – на Ю, Г – на Я. Пробелы и знаки препинания не изменяются. Пример: До шифрования: МАМА МЫЛА РАМУ После шифрования: ИЬИЬ ИЧЗЬ МЬИП
	Задать размер строки (не менее самой длинной) и выровнять все строки по ширине (как это делается в Word) вставкой пробелов.
	Удалить из текста все гласные буквы.
	Переставить местами строки со сдвигом: первую на место второй, вторую на место третьей и т.д., последнюю на место первой.
	Использовать шифрование с применением шифра Цезаря и величиной сдвига 3 по алфавиту в сторону возрастания. Используется кольцевой сдвиг: буква Э меняется на А, Ю – на Б, Я – на В. Пробелы и знаки препинания не изменяются. Пример: До шифрования: МАМА МЫЛА РАМУ После шифрования: ПГПГ ПЮОГ УГПЦ
	Поменять слова со сдвигом на 2 слова: первое на место третьего, второе на место четвертого и т.д., предпоследнее на место первого, последнее на место второго.
	Продублировать все гласные буквы: везде, где встречается буква А записать АА, везде, где Е – ЕЕ и т.д.
	В каждой строке поменять местами первые и последние 3 буквы.
	Использовать шифрование методом циклической перестановки с длинной блока 4. Размер текста должен быть кратен 4, в противном случае текст дополняется пробелами. Текст по блокам сдвигается вправо, последняя буква помещается на место первой. Пример: До шифрования: |МАМА| МЫЛ|А РА|МУ | После шифрования:|АМАМ|Л МЫ|АА Р| МУ |
	Удалить из текста все знаки препинания и прочие специальные символы, оставив только пробелы. Каждую строку заканчивать точкой, если ее там не было.
	Поменять слова со сдвигом: первое на место второго и т.д., последнее на место первого.
	Продублировать буквы начала алфавита А, Б, В, Г, Д: везде, где встречается буква А записать АА, везде, где Б – ББ и т.д.
	Провести анализ вхождения символов-разделителей: пробелов, табуляции, перехода на новую строку. То есть определить отношение появления этих символов как ко всем буквам текста, так и ко всем символам файла.
	Использовать шифрование с применением шифра Цезаря и величиной сдвига 4 по алфавиту в сторону возрастания. Используется кольцевой сдвиг: буква Ь меняется на А, Э – на Б, Ю – на В, Я – на Г и т.д. Пробелы и знаки препинания не изменяются. Пример: До шифрования: МАМА МЫЛА РАМУ После шифрования: РДРД РЯПД ФДРЧ
	Поменять слова со сдвигом на 3 слова: первое на место четвертого, второе на место пятого и т.д., последнее на место третьего.
	Продублировать буквы начала и конца алфавита А, Б, В, Э, Ю, Я: везде, где встречается буква А записать АА, везде, где Б – ББ и т.д.
	Задать размер строки (не менее самой длинной) и выровнять все строки по ширине (как это делается в Word) вставкой пробелов.
	Удалить из текста все согласные буквы.
	Провести анализ вхождения знаков препинания: запятой, точки, точки с запятой, многоточия, восклицательного и вопросительного знаков. То есть определить отношение появления этих символов как ко всем буквам текста, так и ко всем символам файла.
	Использовать шифрование с применением шифра Цезаря с величиной сдвига 3 по алфавиту в сторону убывания. Используется кольцевой сдвиг: буква А меняется на Э, Б – на Ю, В – на Я. Пробелы и знаки препинания не изменяются. Пример: До шифрования: МАМА МЫЛА РАМУ После шифрования: ЙЭЙЭ ЙШИЭ НЭЙР
	Сделать анализ частоты появления букв в файле, упорядоченных по алфавиту. То есть результат – это таблица из 33 строк, в одной графе которой название буквы, в другой – количество появлений в файле.
	Подсчитать количество слов, пробелов и знаков препинания в файле. Результат с сопровождающими надписями вывести на экран. Записывать результат в файл не надо.
	Использовать шифрование методом циклической перестановки с длинной блока 3. Размер текста должен быть кратен 3, в противном случае текст дополняется пробелами. Текст по блокам сдвигается вправо, последняя буква помещается на место первой. Пример: До шифрования: |МАМ|А М|ЫЛА| РА|МУ | После шифрования:|АММ| МА|ЛАЫ|РА |У М|
	Отсортировать все слова по алфавиту, учитывая все буквы. Получить файл из строк по количеству слов, удалив все пробелы и знаки препинания.
	Провести анализ вхождения гласных А, Е, И, О, У, Э, Ю, Я. То есть определить отношение появления этих букв ко всем буквам текста.
	Использовать шифрование методом простой перестановки с длинной блока 4. Размер текста должен быть кратен 4, в противном случае текст дополняется пробелами. В данном случае местами меняются только крайние буквы, средняя остается на месте. Пример: До шифрования:|МАМА| МЫЛ|А РА|МУ | После шифрования: |АМАМ|ЛЫМ |АР А| УМ|