double arrow

Пример 1. Найти заданный элемент в линейной таблице

Найти заданный элемент в линейной таблице.

Дано: линейная таблица А(n), заданный элемент L.

Найти: k – номер этого элемента.

Задача состоит в том, чтобы определить, имеется ли в этой таблице элемент, значение которого совпадает с заданным числом L. Если такой элемент существует, то необходимо в качестве ответа получить порядковый номер этого элемента. В противном случае необходимо выдать номер, равный нулю. Будем просматривать подряд все элементы таблицы, начиная с первого, и сравнивать их значения с L. Такой просмотр надо продолжать до тех пор, пока не будет найден элемент таблицы, равный L, или до тех пор, пока не будет просмотрена вся таблица (если такого элемента не существует).

Опишем алгоритм поиска в таблице. Он будет использовать величины i (число просмотренных элементов) и k (номер искомого элемента).

Вначале i будет равно 0, так как мы еще не просмотрели ни одного элемента таблицы. Затем i будет возрастать: мы будем просматривать все новые и новые элементы таблицы, пытаясь найти среди них элемент, равный L. Если такой элемент обнаружится, то k станет равным его номеру, а до тех пор k будет равно 0. Если числа L в таблице нет, то k так и останется равным нулю. Таким образом, значение переменной k будет сигнализировать об успехе (k > 0) поиска.

алг нахождение заданного элемента (вещтаб А(n); вещ L; цел n; цел k)

арг А(n), n, L

рез k

начцел i

i=1

k=0

пока i<>n и k=0

нц

если A(i)=L

то k=i

i=i+1

кц

вывод k

Кон

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

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

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


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: