При решении многих задач возникает необходимость определить, содержит ли массив определенную информацию или нет. Например, проверить, есть ли в списке студентов фамилия Петров. Задачи такого типа называются поиском в массиве.
Для организации поиска в массиве могут быть использованы различные алгоритмы. Наиболее простой — это алгоритм простого перебора. Поиск осуществляется последовательным сравнением элементов массива с образцом до тех пор, пока не будет найден элемент, равный образцу, или не будут проверены все элементы. Алгоритм простого перебора применяется, если элементы массива не упорядочены.
На практике довольно часто производится поиск в массиве, элементы которого упорядочены по некоторому критерию (такие массивы называются упорядоченными). Например, массив фамилий, как правило, упорядочен по алфавиту, массив данных о погоде — по датам наблюдений. В случае, если массив упорядочен, то применяют другие, более эффективные по сравнению с методом простого перебора алгоритмы, один из которых — метод бинарного поиска.
Пусть есть упорядоченный по возрастанию массив целых чисел. Нужно определить, содержит ли этот массив некоторое число (образец).
Метод (алгоритм) бинарного поиска реализуется следующим образом:
1. Сначала образец сравнивается со средним (по номеру) элементом массива.
* Если образец равен среднему элементу, то задача решена.
* Если образец меньше среднего элемента, то это значит, что искомый элемент расположен ниже среднего элемента, и задача сокращается на половину элементов и дальнейший поиск осуществляется в левой части массива.
* Если образец больше среднего элемента, то это значит, что искомый элемент расположен выше среднего элемента, и дальнейший поиск осуществляется в правой части массива.
Алгоритм бинарного поиска, заканчивает свою работу, если искомый элемент найден или если перед выполнением очередного цикла поиска обнаруживается, что значение минимального (по индексу) элемента больше, максимального.
Функция Генератор случайных чисел. Синтаксис #include<stdlib.h> int random(int num); Файл, содержащий stdlib.hпрототип Описание Функция random возвращает случайное число в диапазоне от 0 до num-1. random(num) это макро, определенное в виде (rand()%num). И num и возвращаемое значение целые. Возвращаемое random возвращает случайное число в диапазоне отзначение 0 до num-1. Переносимость Соответствующая функция существует в Turbo Pascal. Смотрите также rand, randomize, srand. Пример:
Функции преобразования типа
Функции преобразования данных довольно часто используются, как следует из названия, для преобразования одного типа данных в другой тип. Их прототипы описаны в библиотеке stdlib.h
Преобразует строку символов в число с плавающей точкой (double или float)
int atoi(const char *s)
Преобразует строку символов в число типа int
long atol(const char *s)
Преобразует строку символов в число типа long
char *itoa(int value, char * string, int radix);
Преобразует число типа int в строку символов
char *ltoa(long value, char *string, int radix);
Преобразует число типа long в строку символов
double strtod(char * nptr, char **endptr);
Преобразует строку символов nptr в число с плавающей точкой типа double. endptr - указатель на конец просмотра
Чаще всего данные функции используются для преобразования чисел, введенных в виде символьных строк, в числовое представление, а также для выполнения определённых арифметических операций над ними и обратное преобразование в строку символов. Рассмотрим широко используемые из них:
int atoi(const char* ptr)
Преобразует строку символов, на которую указывает ptr, в число типа int. Если встречается символ, который не может быть преобразован, данная функция возвращает 0.
Ниже приведен код программы, которая реализует некоторые функции из библиотеки stdlib.h
