Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
До сих пор мы рассматривали алгоритмы, в которых основными являются математические операции. Существует класс алгоритмов, в котором основными являются не математические вычисления, а операции сравнения и пересылки. Такие алгоритмы принято называть нечисловыми. Сюда относятся задачи связанные с:
- обработкой символьных данных;
- сортировкой данных;
- поиском данных.
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) операций. К настоящему времени придумано много различных алгоритмов сортировки. Все они делятся на три класса:
- сортировка выбором;
- сортировка включением;
- сортировка обменом.
Дата публикования: 2014-12-10; Прочитано: 364 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!