Смекни!
smekni.com

Алгоритмы и структуры данных. Программирование в Cи (стр. 6 из 7)

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) на промежутке (x1,x2) из известных значений f (x1) и f (x2).


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

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

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

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

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:

1. pid_t getpid(void) – возвращает PID 2. pid_t getppid(void) – возвращает родителей PID-процесса.

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

В таблице автор приводит список чаще всего подаваемых Unix сигналов.

Имя Значение Функция
SIGHUP 1 Выход из системы
SIGINT 2 Прерывание пользователя (клавиши Ctrl+C)
SIGQUIT 3 Запрос пользователя на окончание (клавиша CTRL + &bsol;)
SIGFPE 8 Ошибка с плавающей запятой
SIGKILL 9 Принудительное завершение процесса

9. Стиль программирования. Ловушки

9.1 Стиль программирования в C

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