3 Алгоритмы поиска

Всякий программист должен владеть некоторым “джентльменским набором” алгоритмов, независимо от того, на каком языке он пишет свои программы. В следующих разделах мы познакомимся с простыми, но полезными алгоритмами. Начнем с алгоритмов поиска.

3.1 Поиск наибольшего среди вводимых чисел

З а д а ч а. Ввести с клавиатуры N чисел, найти среди них наибольшее и вывести его на экран.

Р е ш е н и е.

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

Начало

Ввести первое число прямо в переменную Max;

Установить счетчик введенных чисел в 1, count = 1;

Покаcount <= Nповторять

Начало

Ввести очередное число X;

ЕслиX > Max,тоMax = X;

Увеличить на 1 счетчик чисел, count = count + 1;

Конец

Вывести на экран значение Max.

Конец

Нетрудно так изменить построенный алгоритм, чтобы он находил не наибольшее, а наименьшее из введенных чисел.

3.2 Поиск наибольшего числа в массиве

В программах часто приходится иметь дело не с отдельными переменными, а с целыми последовательностями переменных, которые программисты называют массивами. Элементы массива можно воспринимать как пронумерованные переменные. Любой элемент обозначается именем массива и номером в квадратных скобках. Например, первый элемент массива М называется M[1], n-й элемент массива BOX — BOX[n].

З а д а ч а. Задан числовой массив M из n элементов: M[1], M[2],..., M[n]. Найти набольшее число в массиве и его номер.

Р е ш е н и е.

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

Начало

Поместить первое число M[1] в переменную Max;

Установить счетчик в 2, count = 2;

Пока count <= N повторять

Начало

Если M[count] > Max, то Max = M[count];

Увеличить на 1 счетчик чисел, count = count + 1;

Конец

Вывести на экран значение Max.

Конец

Этот алгоритм получен из предыдущего при помощи минимальных переделок, но он не отвечает на вопрос задачи о месте наибольшего числа в массиве. Попробуем сохранять в переменной Max не наибольшее значение, а номер того элемента массива, который это значение содержит. Если в Max содержится номер элемента, то значение элемента всегда доступно в виде M[Max].

Начало

Поместить 1 в переменную Max, Max = 1;

Установить счетчик в 2, count = 2;

Покаcount <= Nповторять

Начало

ЕслиM[count] > M[Max],тоMax = count;

Увеличить на 1 счетчик чисел, count = count + 1;

Конец

Вывести значение наибольшего элемента M[Max] и его номер Max;

Конец

Как видим, алгоритм почти не изменился, но стал точно отвечать на вопрос задачи.

3.3 Поиск заданного числа в массиве

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

З а д а ч а. Задан числовой массив, M[1], M[2],..., M[n], и некоторое число X. Найти номер того элемента массива, который содержит число X, или сообщить, что такого элемента в массиве нет.

Р е ш е н и е.

Поскольку числа в массиве не упорядочены, нам не остается иного, как перебирать последовательно все элементы массива M и сравнивать их с искомым числом X. Для перебора элементов массива снова используем переменную – счетчик count. Сравнение с X будем выполнять в цикле, который должен повторяться пока истинны два условия: 1) значение счетчика count не достигло n – общего числа элементов массива; 2) очередной элемент M[count] не равен X.

Начало

Установить счетчик элементов в 1, count = 1;

Пока (count <= n) и (M[count] <> X) повторять

увеличить на 1 счетчик чисел, count = count + 1;

Если count = n + 1, то сообщить, что числа X в массиве нет,

иначе вывести count;

Конец

Поясним смысл последнего оператора. Когда цикл завершится (а это случится обязательно, так как, либо очередной элемент M[count] совпадет с X, либо счетчик достигнет конца массива), третий оператор выясняет, по какой причине это произошло. Если count = n + 1, то достигнута граница массива, иначе в массиве найдено число X.