ASM

[RACOST]

Дан массив из десяти целых чисел. Найти и выдать на консоль значения третьих максимальных и минимальных чисел.
Например, если массив содержит [0,1,2,3,4,5,6,7,8,9], то искомыми значениями являются 2 и 7.

[rlib]

Сортируете массив (если неотсортирован), потом берете 3-ой элемент с начала и 3-ий элемент с конца массива.

[s-andriano]

Нерационально решение - сложность в лучшем случае O(n*log(n)).
Достаточно 6 простых переменных и одного прохода по массиву (сложность O(n)).

[BDA]

rlib, если массив достаточно большой, то сортировка будет не оптимальным вариантом.
RACOST, вам понадобится 6 дополнительных переменных. (s-andriano, опередили )
Все шесть инициализируются первым элементом массива.
(Пусть это будут max1, max2, max3, min1, min2, min3)
Затем циклом от 2 элемента до конца идем по массиву.
Сравниваем число с max1.
Если больше, то переносим max2 в max3, max1 в max2, а элемент заносим в max1.
Если первое условие не выполнилось, то сравниваем с max2.
Если больше, то max2 в max3, а в max2 элемент.
Иначе сравниваем с max3 и если больше, то заносим в max3.
Тоже самое делаем с минимумами.
На печать выводим max3 и min3.

[rlib]

Каюсь! Но ведь о complexity речь не шла, а отсортированный массив может сгодится на будущее

[s-andriano]

Сообщение от rlib

Каюсь! Но ведь о complexity речь не шла, а отсортированный массив может сгодится на будущее

1. Исключительно IMHO: писать оптимально нужно всегда, а не только когда "зайдет речь".
2. Если Вам нужен массив из 10 чисел, вы объявляете его на 100000? А вдруг сгодится на будущее...

[rlib]

Сообщение от s-andriano

1. Исключительно IMHO: писать оптимально нужно всегда, а не только когда "зайдет речь".

Отвечу вам рекомендацией Роберта Круза, автора "Data Structures
and Program Design in C++":

134. Don’t optimize code unless it is absolutely necessary.



Оптимизация всегда усложняет алгоритм, а для спрашивающего простота, думаю, на первом месте.

[BDA]

В данном случае (на асме), написать сортировку не легче (особенно если не обычный пузырек), чем сделать сложный if, имхо.
Хотя, наверное, я "загнул". В условии всего 10 чисел, так что можно написать и обычную сортировку пузырьком, но она будет не намного короче сложного if. Однако лучше сразу думать оптимально (оптимальным алгоритмом), чем переписывать программу при незначительном увеличении входных данных. Т.е. не выжимать различными извращенными оптимизациями лишние пару секунд из неоптимального алгоритма, а сразу писать на качественно более высоком уровне без оптимизаций самого кода.

[rlib]

Все, конечно, зависит от конкретной задачи, но, когда можно воспользоваться стандартным решением, даже если оно не самое оптимальное, лично я им воспользуюсь. Потому что bubbleSort(array); print array[2], array[N-2] очень читабелен.

[Serge_Bliznykov]

Правы и те, кто собирается использовать сортировку для решения данной задачи (я на стороне rlib)
Но правы и те, кто выступает за оптимальное нахождение решения за один проход массива (используя 6 доп.переменных для накопления результата).

Парадокс в том, что не существует УНИВЕРСАЛЬНОГО ответа, какое решение лучше/быстрее/надёжнее.

решение через сортировку достаточно просто ("просто" - насколько это можно говорить применительно к ассемблеру, конечно! ). Используем код сортировки. Он прост и отработан. Готовый код сортировки легко найти и использовать. Его легко отлаживать.
Преимущество - если в задаче нужно будет найти не 3-и по порядку, а 4-е экстремальные числа (или даже номер этих чисел будет задаваться оператором в диалоговом режиме) - это абсолютно никак не повлияет на алгоритм - доработка будет минимальнейшей.
Недостатки: неоптимальность/неэффективность с точки зрения быстродействия (проявится, только при достоточно больших размерах исходного массива. При N=10 (или 50,100,1000 элементов) разницы в быстродействии пользователь программы явно не заметит!

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

И, кстати, рекомендую ознакомится с небольшой дискуссией по такой же проблеме здесь - 3 максимальных элемента массива (pascal)


p.s. RACOST, если бы Вам нужно было на языке Паскаль, то Вы бы давно уже или написали код самостоятельно или получили тут на форуме советы/подсказки/готовый код, но писать такую муть на Ассемблере - нудно и скучно...