Теория:
Наиболее популярными задачами невычислительного характера в программировании являются задачи на поиск.
Типовые задачи на поиск: найти наибольший (наименьший) элемент массива; найти элемент массива, значение которого
равно заданному значению.
Компьютер не может за один раз сравнить весь ряд объектов. Каждый шаг позволяет сравнивать только два объекта. При написании программы нужно организовать последовательный просмотр каждого элемента массива и сравнить значения каждого элемента с предыдущим, или некоторым образцом в зависимости от условия задачи.
Рассмотрим задачу первого типа (нахождение наибольшего (наименьшего) элемента). Представим себе одномерный массив в виде стопки листов, на каждом из которых написано число.
Тогда идея поиска наибольшего элемента массива может быть представлена следующим образом:
1. возьмём верхний лист (первый элемент массива), запомним имеющееся на листе число (запишем его мелом на доске) как наибольшее из просмотренных;
2. уберём листок в сторону;возьмём следующий листок; сравним числа, записанные на листке и на доске; если число на листке больше, то сотрём число, записанное на доске, и напишем там то же число, что и на листке; если же новое число не больше, то на доске оставим имеющуюся запись; уберём листок в сторону;
3. повторим действия, описанные в пункте \(2\), для всех оставшихся карточек в стопке.
В итоге на доске будет записано самое большое значение просмотренного массива. Так как доступ к значению элемента массива осуществляется по его индексу, то при организации поиска наибольшего элемента в одномерном массиве правильнее искать его индекс.
Результатом решения задачи второго типа (нахождение элемента массива, значение которого равно заданному значению) может быть:
- \(n\) — индекс элемента массива такой, что \(a[n]=x\), где \(x\) — заданное число;
- сообщение о том, что искомого элемента в массиве не обнаружено.
Алгоритм поиска в сформированном нами массиве \(a\) значения, равного \(50\), может выглядеть так:
n:=0;
for i:=1 to 10 do
if a[i]=50 then n:=i;
if n=0 then write ('Нет') else write (i)
В этой программе последовательно просматриваются все элементы массива. Если в массиве несколько элементов, значения которых равны заданному числу, то программа найдет последний из них.
Во многих случаях требуется найти первый из элементов, имеющих соответствующее значение, и дальнейший просмотр массива прекратить. Для этой цели можно использовать следующую программу:
i:=0;
repeat
i:=i+1;
until(a[i]=50) or (i=10);
if a[i]=50 then write (i) else write ('Нет');
Здесь выполнение алгоритма будет прервано в одном из двух случаев:
- в массиве найден первый из элементов, равный заданному;
- все элементы массива просмотрены.
Зачастую требуется определить количество элементов, удолетворяющих некоторому условию. В этом случае вводится переменная, значение которой увеличивается на единицу каждый раз, когда найден нужный элемент.