Избранные алгоритмы

8. Избранные алгоритмы

В этой главе Юрген Плате рассматривает наиболее распространенные и типичные виды алгоритмов, реализованные на Си.

·   Обработка строк символов(Strings)

К простым операторам строк, которые задаются с помощью <ctype.h>, автор относит следующие операторы:

islower(c)	Строчная буква
isupper(c)	Прописная буква
isalpha(c)	Строчная или прописная буква
isdigit(c)	Десятичное число
isalnum(c)	Строчная или прописная буква или десятичное число

Наряду с простыми операторами имеется ряд комплексных команд для строковых символов. Прототипы находятся в стандартной библиотеке <STRING.H>.

·           strcat (char *a, char *b) – Последовательность символов b прибавляется к a.

·           strncat ( char *a , char *b , int n ) – прибавляются к а n символов b.

·           strcpy ( char *a , char *b ) – строка b копируется после a

·           strncpy ( char *a , char *b , int n ) – n символов строки b копируется после a

·           int n = strlen ( char *a ) – возвращает длину строки

·   Арифметика дат

В этом параграфе автором собраны достаточно простые алгоритмы, связанные с использованием даты и времени.

В первую очередь автор рассказывает о юлианском датоисчислении. При этом не имелось бы никакой проблемы 2000 года. Вместо этого дата сохранялась в компьютерах как строка символов (TTMMJJ) и это привело к тому, чтобы после 99 шел год 00. Причина такого датоисчисления была связана с необходимостью экономии памяти.

Алгоритм расчета даты по Юлианскому стилю можно представить следующим образом:

Y = год, М = месяц, D = день

Если M> 2, то Y и М остаются неизменными. Если М = 1 или М = 2, то

Y = Y - 1

М = М + 13

Для нахождения текущей даты имеем:

JD = INT (365 .25 * (Y + 4 716)) + INT (3 0.6001 * (М + 1)) + D + B - 1524.5

·   Числовой тип

Здесь профессор приводит некоторые алгоритмы, которые работают с числовыми данными.

Достаточно часто в алгоритмах необходимо определить является ли число простым. Чтобы это устанавить, необходимо делить число X на числами, которые больше 2 и меньше X. Если число ни на какое из них не делится, оно должно быть простым.

Затем автор рассказывает о нахождении нулей функций. Для этого применяют методы аппроксимации. Если задан интервал (a;b), на котором определена функция, то необходимо каждый раз делить интервал пополам и проверять где находится нуль. Повторяется действие до тех пор, пока интервал не станет достаточно мал.

Еще один типичный пример рассмотрен в этом параграфе автором – решение систем линейных уравнений методом Гаусса.

Пусть задана система уравнений вида Ax = b. Считается, что если k-е уравнение будет решено, то:

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

·   Статистическая мера

В этом параграфе автор затрагивает статистический метод обработки информации и построение программ на основе этого метода. Статистика обрабатывает эмпирические числа и на основании этой обработки делаются прогнозы и принимаются решения.

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

Наряду с функцией частоты основную совокупность данных можно охарактеризовать с помощью среднего значения и дисперсии. Арифметическое среднее значение определяется так:

а дисперсия следующим образом:

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

При линейной интерполяции выполняют аппроксимацию функциональных значений f (x) на промежутке (x₁,x₂) из известных значений f (x₁) и f (x₂).

Поиск и сортировка

В этом параграфе автор рассказывает о наиболее распространенных в программировании операций с данными – поиске и сортировке.

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

Различают несколько основных методов поиска, зависящих от типа данных:

1.         Табличный поиск осуществляется по индексу данных в таблице.

2.         Линейный поиск предполагает просмотр всех элементов по порядку до нахождения нужного.

3.         Бинарный поиск осуществляется после проведения сортировки, суть которого состоит в проверке среднего элемента последовательности и определения по ключу в какую сторону двигаться для нахождения нужного элемента.

Сортировка является одной из самых важных операций с данными. Профессор приводит такое определение сортировки:

Сортировка - процесс упорядочения заданного множества объектов в определенном порядке. Выделяют следующие виды алгоритмов сортировки:

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

-    Сортировка выбором. В этом случае берут первый элемент последовательности и ищут самый маленький элемент, с которым его и меняют местами. Затем начинают со второго и его меняют на самый маленький в оставшейся последовательности и т.д.

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

-    Сортировка методом Шелла. Сначала массив разделяется на несколько групп, между членами которых имеется равное расстояние. Пусть, например, используется расстояние 3, тогда компоненты 1, 4, 7 принадлежат одной группе, так же как и 2, 5, 8..., 3, 6, 9... и т.д. эти группы упорядочиваются в отдельности, затем расстояние уменьшается и действия повторяется до расстояния 1.

-    Быстрая сортировка. Выбирают любой компонент массива - к примеру, средний - и массив делится на 2 группы: одна с компонентами, которые больше чем выбранный, а другая с меньшими. Эти обе группы делятся вновь по заданному алгоритму. Таким образом, получается рекурсивная функция, которая достаточно быстро сортирует данные.

·   Реализация множеств

Автор в этой главе упоминает о множествах – достаточно важной структуре программирования. Другие языки программирования (например, Паскаль) имеют тип данных множества. В языке C такого не имеется.

Однако множества возможно представить с помощью битовых массивов. Элементы массива нумеруются, и каждый элемент множества представляет собой 1 бит. Если соответствующий бит установлен (1), то элемент содержится в множестве, если бит равен 0, соответствующий элемент не содержится в множестве. Пересечение и объединение можно использовать с помощью логических операторов UND и ODER. Так как переменные величины типа int или char только относительно маленькие множества могут представлять, то получить к ним доступ можно с помощью указателя на битовый массив.

8.2 Экскурс: процессы или сигналы

В этом параграфе профессор несколько уходит от программирования и пытается объяснить, как выполняются программы в операционной системе на примере ОС Linux.

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

Если под Linux запускается программа, она получает однозначный идентификационный номер ID, который лежит в диапазоне между 1 и 32 767. Посредством этого номера ОС может идентифицировать находящиеся в памяти программы и получить доступ к ним. Для работы с ID используются две функции, которые определены в файле заголовка unistd.h: