- •Содержание
- •1Алгоритмы линейных структур
- •2 Циклы
- •Введение
- •1 Алгоритмы линейных структур
- •1.1 Этапы разработки программы
- •1.2 Основные понятия
- •1.3 Основная структура программы
- •1.4 Алфавит языка
- •1.5 Идентификаторы
- •1.6 Константы
- •1.7 Понятие переменной Типы
- •1.8 Оператор присваивания Арифметические выражения
- •1.9 Операторы ввода и вывода информации
- •1.10 Практические задачи
- •1.11 Примеры решения задач
- •2 Циклы
- •2.1 Цикл с предусловием
- •Цикл с постусловием
- •Цикл со счетчиком
- •2.2 Задачи
- •2.3 Примеры
- •3 Немного об алгоритмах Алгоритм Кнута - Морриса - Пратта
- •Алгоритм Бойера – Мура
- •Алгоритм Рабина
- •Алгоритмы сортировки
- •Метод пузырька.
- •Сортировка выбором
- •Метод Шелла
- •Метод Хoopа
- •3.1 Разветвляющиеся алгоритмы
- •3.2 Задачи Свойства и виды треугольников (задачи 1-4)
- •Свойства и виды четырехугольников (задачи 5, 6)
- •Каким будет значение переменной а после выполнения фрагмента программы с составным оператором?
- •4 Массивы
- •4.1 Объявление массива
- •4.2 Действия над массивами
- •4.3 Вывод массива
- •4.4 Ввод массива
- •4.5 Сортировка массива
- •4.6 Поиск в массиве
- •4.7 Поиск минимального (максимального) элемента массива
- •4.8 Многомерные массивы
- •4.9 Ошибки при использовании массивов
- •4.10 Практические задачи
- •5 Множества
- •5.1 Описание типа множество
- •5.2 Операции над множествами
- •5.3 Группы операций
- •5.4 Упражнения
- •5.5 Задачи Тема: Множества
- •6 Записи
- •6.1 Понятие записи
- •6.2 Оператор присоединения With ... Do
- •6.3 Вариантные записи
- •6.4 Работа с файлами записей
- •6.5 Задачи
- •7 Файлы
- •7.1 Работа с файлами
- •7.2 Текстовые файлы
- •7.3 Типизированные файлы
- •7.4 Нетипизированные файлы
- •7.5 Задачи
- •8 Графика
- •8.1 Графика в Турбо Паскале
- •8.2 Базовые процедуры и функции
- •Процедуры модуля Graph
- •Функции модуля Graph
- •8.3 Экран и окно в графическом режиме
- •8.4 Вывод простейших фигур
- •8.5 Графические процедуры
- •8.6 Построение прямоугольников
- •8.7 Построение многоугольников
- •8.8 Построение дуг и окружностей
- •8.9 Работа с текстом
- •8.10 Построение графиков функций
- •8.11 Циклы в графике. Построение случайных процессов
- •8.12 Создание иллюзии движения
- •Задания
- •Контрольные тесты
- •1. Программирование алгоритмов линейных структур
- •2. Программирование алгоритмов разветвляющейся структуры
- •3. Программирование алгоритмов циклических структур
- •4. Массивы
- •5. Множества
- •6. Записи
- •7. Файлы
- •8. Графика
4.5 Сортировка массива
Под сортировкой массива подразумевается процесс перестановки элементов с целью упорядочивания их в соответствии с каким-либо критерием. Например, если имеется массив целых а, то после сортировки по возрастанию должно выполняться условие:
а[1]<a[2]<…<a[size], где
size- верхняя граница индекса массива.
Так как можно сравнивать переменные типов integer, real,char,string, то можно сортировать массивы этих типов.
Задача сортировки распространена в информационных системах и используется как предварительный этап задачи поиска, так как поиск в упорядоченном массиве проводится намного быстрее, чем в неупорядоченном.
Существует много методов(алгоритмов) сортировки массивов. Здесь мы рассмотрим два метода:
метод прямого выбора;
метод прямого обмена.
Сортировка методом прямого выбора.
Алгоритм сортировки массива по возрастанию методом прямого выбора может быть представлен так:
1.Просматривая массив от первого элемента, найти минимальный элемент и поместить его на место первого элемента, а первый- на место минимального.
2.Просматривая массив от второго элемента, найти минимальный элемент и поместить его на место второго элемента, а второй- на место минимального.
3.И так далее до последнего элемента.
Сортировка методом прямого обмена.
В основе алгоритма лежит обмен соседних элементов массива. Каждый элемент массива, начиная с первого, сравнивается со следующим, и если он больше следующего, то элементы меняются местами. Таким образом, элементы с меньшим значением продвигаются к началу массива(всплывают), а элементы с большим значением- к концу массива(тонут), поэтому этот метод иногда называют методом ”пузырька”. Этот процесс повторяется на единицу меньше раз, чем элементов в массиве.
4.6 Поиск в массиве
При решении многих задач возникает необходимость установить, содержит ли массив определенную информацию или нет. Например, проверить, есть ли в массиве фамилий студентов фамилия Петров. Задача такого типа называется поиском в массиве.
Для организации поиска в массиве могут быть использованы различные алгоритмы. Наиболее простой- это алгоритм простого перебора. Поиск осуществляется последовательным сравнением элементов массива с образцом до тех пор, пока не будет найден элемент, равный образцу, или не будут проверены все элементы. Алгоритм простого перебора применяется, если элементы массива не упорядочены.
Очевидно, что чем больше элементов в массиве и чем дальше расположен нужный элемент от начала массива, тем дольше будет программа искать нужный элемент.
Так как операции сравнения применимы как к числам, так и к строкам, то данный алгоритм может использоваться для поиска как в числовых, так и в строковых массивах.
На практике довольно часто проводится поиск в массиве, элементы которого упорядочены по некоторому критерию. Например, массив фамилий, как правило, упорядочен по алфавиту, массив данных о погоде упорядочен по датам наблюдений.
Для поиска в упорядоченных массивах применяют другие, более эффективные по сравнению с методом простого перебора, алгоритмы, один из которых- метод бинарного поиска.
Суть метода бинарного поиска заключается в следующем. Выбирается средний (по номеру) элемент упорядоченного, например, по возрастанию массива, и с этим элементом сравнивается образец. Если средний элемент равен образцу, то задача решена. Если средний элемент меньше образца, то искомый элемент расположен выше среднего элемента. Если средний элемент больше образца, то искомый элемент расположен ниже среднего.
После того как определена часть массива, в которой может располагаться искомый элемент, поиск проводят в этой части, выделяя новый средний элемент. Номер среднего элемента вычисляется по формуле (niz-verh)/2+verh.