Сборник по задачам и примерам Assembler




Сортировка массивов - часть 9


mov di,k

emp al ,mas[di-l]

jna @@m6

inc di

emp al.mas[di-l]

jna @@m6

jmp @@m2

@@m6: ;условие выполнилось:

;2j+l+<M AND (mas[j]<mas[2j] OR mas[j]<mas[2j+l]) :обмен с mas[j]

mov di,k

mov al ,mas[di-1] ;ax:=mas[k]

inc di

emp al,mas[di-l] :mas[k]>mas[l]

jna ШтЗ

mov al ,raas[si-l]

movx.al ;x:=rnas[j]

dec di

mov al ,mas[di-l]

movmas[si-l].al :mas[j]:=mas[k]

movj.di :j:=k

mov al .x

movmas[di-l],al :mas[k]:=x

jmp @?m4

:@@m3: x:=mas[j] ;ПЕРЕЙТИ_НА @@ml №m3: :mas[k] =< mas[l]

mov al,mas[si-l]

movx.al :x:=mas[j]

mov al,mas[di-l]

movmas[si-l].al ;mas[j]:=mas[l]

movj.di :j:=l

mov al ,x

movmas[di-l].al ;mas[l]:=x

jmp @@m4 Шт2: ; условие не выполнилось: 2j+l+<M AND (mas[j]<mas[2j] OR mas[j]<mas[2j+l])

mov ax.k

emp ax.m

Нахождение медианы

Медиана - элемент последовательности, значение которго не больше значений одной половины этой последовательности. Например, медианой последовательности чисел 38 7 5 90 65 8 74 43 2 является 38.

оответствующая отсортированная последовательность будет выглядеть так: 2 5 7 8 38 43 65 74 90.

Задачу нахождения медианы можно решить просто — предварительно отсортировать исходный массив и выбрать средний элемент. Но К. Хоор предлагает метод, который решает задачу нахождения медианы быстрее и соответственно может рассматриваться как вспомогательный для реализации других задач. Достоинство метода К. Хоора заключается в том, что с его помощью можно эффективно находить не только медиану, но и значение k-го по величине элемента последовательности. Например, третьим по величине элементом приведенной выше последовательности будет 7.

Значение k-го элемента массива определяется по формуле k=n/2, где п — длина исходной последовательности чисел.

Ниже приведена программа prg4_123.asm, которая находит элемент-медиану массива. Аналогичную функцию выполняет и процедура median, но процедура отличается тем, что ее можно вызывать динамически во время работы программы, в которой она используется.

ПРОГРАММА prg4_123




Содержание  Назад  Вперед