double arrow

Пример 2. Пусть задана линейная таблица А, элементы которой нумеруются от К до N (К < N).Построим алгоритм поиска наименьшего элемента линейной таблицы


Пусть задана линейная таблица А, элементы которой нумеруются от К до N (К < N).Построим алгоритм поиска наименьшего элемента линейной таблицы. В этом алгоритме элементы таблицы будут просматриваться по порядку, от первого до последнего. Для этого будет использоваться переменная i — номер первого непросмотренного элемента таблицы. Кроме i, будут использоваться еще две переменные: МИН — «минимум из уже просмотренных элементов»; L — «номер элемента, минимального среди уже просмотренных».

Работа алгоритма начинается с серии команд, в которой мы присваиваем переменной МИН значение начального элемента таблицы. Этот элемент уже просмотрен, и мы берем К в качестве значения для l; просмотрен один элемент А [К],и он минимален среди просмотренных. Берем K + 1 в качестве значения для i — номера первого непросмотренного элемента.

Работа алгоритма завершается, когда вся таблица просмотрена, и номер ее минимального элемента найден. Этот номер и является результатом.

Алгоритм имеет следующий вид:

алг МИНЭЛЕМЕНТ (целК, N, вещтабА[К : N], целl)

аргА, К, N

резl

начцелi, вещМИН

МИН := А[К]; l := К; i:=K + 1

покаi< N

нц

еслиMИH := A[i]

тоМИН := А[i]; l := i

Все

i := i + 1

кц

Кон

Построим теперь алгоритм упорядочения линейной таблицы, используя алгоритм МИНЭЛЕМЕНТ в качестве вспомогательного. Задача упорядочения таблицы формулируется следующим образом. Пусть задана линейная таблица С, элементы которой нумеруются от п до М (п <.М): вещтабС [п : М].

Необходимо переставить элементы этой таблицы так, чтобы они шли в порядке возрастания. Идея алгоритма упорядочения состоит в следующем. Применив алгоритм МИНЭЛЕМЕНТ к таблице С [п : М], мы определим номер l элемента этой таблицы, имеющего наименьшее значение. После этого поменяем значения элементов С [пС [I]. Тогда на n-м месте таблицы С окажется самый маленький по величине элемент. На следующем шаге применяем алгоритм МИНЭЛЕМЕНТ к таблице С [п + 1 : М]и снова определяем номер l минимального элемента этой таблицы. Поменяем местами элементы С [п + 1 ] и С [l], тогда на п + 1-м месте окажется самый маленький из оставшихся элементов. Далее будем применять алгоритм МИНЭЛЕМЕНТ к таблицам С [п + 2 : М], С [п + 3 : М],... ...,С [М − 1, М] и менять местами элементы С [п + 2] и С [l], С [n + 3] и С [l] и, наконец, С [М − 1] и С [l]. В результате таблица С окажется упорядоченной.

На алгоритмическом языке алгоритм упорядочения будет выглядеть следующим образом:

aлгупорядочение (целп, М, вещтабС[п : М])

арг С, n, M

рез С

начцел i, l, вещ R

i := n

пока i < M

нц

МИНЭЛЕМЕНТ (i, M, C, l)

R := C [i]

C [i] := C [l]

C [l] := R

i := i + 1

кц

Кон


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