Лекция: Нечисловые алгоритмы.

До сих пор мы рассматривали алгоритмы, в которых основными являются математические операции. Существует класс алгоритмов, в котором основными являются не математические вычисления, а операции сравнения и пересылки. Такие алгоритмы принято называть нечисловыми. Сюда относятся задачи связанные с:

— обработкой символьных данных;

— сортировкой данных;

— поиском данных.

3.12.1. Обработка символьных данных.

В ЭВМ можно хранить и обрабатывать не только числа, но и символы. Обычно для хранения символа используется ячейка память из восьми двоичных разрядов, в которой хранится код символа. Существуют различные системы кодирования символов, но всегда последовательности символов упорядочены и каждому символу соответствует определенный номер. Поэтому символы можно сравнивать и говорить о том, что один символ больше или меньше другого.

Существует много задач связанных с обработкой символьных данных: задачи связанные с построением редакторов; формирование сообщений программы; организация диалогового режима работы программы. При решении задач связанных с обработкой символьных данных можно использовать следующие типы данных (они имеются в языках программирования):

— символьные и строковые константы;

— символьные и строковые переменные;

— символьные и строковые массивы.

Пример 1.

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

Алгоритм. Так как символы пронумерованы последовательно в цикле будем сравнивать каждый элемент массива с символом 'A' (должно выполняться условие MS(K) >= 'A') и символом 'Z' (MS(K) <= 'Z'). Если эти два условия выполняются одновременно, то в данном элементе массива хранится буква и счетчик букв (обозначим его KS) надо увеличить на единицу.

Рис.3.11.2.

Схема алгоритма решения этой задачи приведена на рис.3.11.2. В алгоритме используются: K – счетчик элементов массива; N – количество обрабатываемых элементов массива. Заметим, что символ «И» в блоке сравнения элементов массива – это логическая операция И.

Пример 2. Алгоритм исключения символа.

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

Идея алгоритма:

— в цикле определяем номер элемента массива MS, который совпадает с заданным символом SK;

— сдвигаем все символы, расположенные справа, на одну позицию влево

— заносим пробел на последнюю позицию.

Уточнение алгоритма: После каждого сдвига символов влево правую границу можно уменьшить на единицу.

Рис.3.11.3.

Фрагмент схемы алгоритма исключения символов приведен на рис.3.11.3. В схеме алгоритма обозначено: N – количество символов в массиве MS; NE – динамическая длина массива; K, L – счетчики (параметры циклов); KS – количество исключенных символов.

3.12.2. Сортировка данных.

Существует большой класс задач, в которых надо упорядочивать данные (числа, последовательности символов) в определенном порядке – по возрастанию или по убыванию. Особенностью таких задач является то, что массив данных может быть большим – десятки и сотни тысяч данных, поэтому сортировать надо в самом массиве. Методы, использующие пересылку данных в другой массив, интереса не представляют.

Мерой эффективности алгоритмов сортировки являются количество сравнений (С) и количество пересылок данных (М). Простые методы требуют порядка С2 операций сравнения, а эффективные – порядка С log(C) операций. К настоящему времени придумано много различных алгоритмов сортировки. Все они делятся на три класса:

— сортировка выбором;

— сортировка включением;

— сортировка обменом.