|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
09.06.2012, 15:41 | #1 |
Пользователь
Регистрация: 09.06.2012
Сообщений: 11
|
ASM
Дан массив из десяти целых чисел. Найти и выдать на консоль значения третьих максимальных и минимальных чисел.
Например, если массив содержит [0,1,2,3,4,5,6,7,8,9], то искомыми значениями являются 2 и 7. |
09.06.2012, 17:38 | #2 |
Форумчанин
Регистрация: 22.05.2012
Сообщений: 352
|
Сортируете массив (если неотсортирован), потом берете 3-ой элемент с начала и 3-ий элемент с конца массива.
|
09.06.2012, 18:10 | #3 |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Нерационально решение - сложность в лучшем случае O(n*log(n)).
Достаточно 6 простых переменных и одного прохода по массиву (сложность O(n)). |
09.06.2012, 18:13 | #4 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,291
|
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.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
09.06.2012, 18:49 | #5 |
Форумчанин
Регистрация: 22.05.2012
Сообщений: 352
|
Каюсь! Но ведь о complexity речь не шла, а отсортированный массив может сгодится на будущее
|
09.06.2012, 19:51 | #6 | |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Цитата:
2. Если Вам нужен массив из 10 чисел, вы объявляете его на 100000? А вдруг сгодится на будущее... |
|
10.06.2012, 00:32 | #7 | |
Форумчанин
Регистрация: 22.05.2012
Сообщений: 352
|
Цитата:
and Program Design in C++": 134. Don’t optimize code unless it is absolutely necessary. Оптимизация всегда усложняет алгоритм, а для спрашивающего простота, думаю, на первом месте. |
|
10.06.2012, 00:36 | #8 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,291
|
В данном случае (на асме), написать сортировку не легче (особенно если не обычный пузырек), чем сделать сложный if, имхо.
Хотя, наверное, я "загнул". В условии всего 10 чисел, так что можно написать и обычную сортировку пузырьком, но она будет не намного короче сложного if. Однако лучше сразу думать оптимально (оптимальным алгоритмом), чем переписывать программу при незначительном увеличении входных данных. Т.е. не выжимать различными извращенными оптимизациями лишние пару секунд из неоптимального алгоритма, а сразу писать на качественно более высоком уровне без оптимизаций самого кода.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
Последний раз редактировалось BDA; 10.06.2012 в 00:41. |
10.06.2012, 00:54 | #9 |
Форумчанин
Регистрация: 22.05.2012
Сообщений: 352
|
Все, конечно, зависит от конкретной задачи, но, когда можно воспользоваться стандартным решением, даже если оно не самое оптимальное, лично я им воспользуюсь. Потому что bubbleSort(array); print array[2], array[N-2] очень читабелен.
|
10.06.2012, 12:38 | #10 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Правы и те, кто собирается использовать сортировку для решения данной задачи (я на стороне rlib)
Но правы и те, кто выступает за оптимальное нахождение решения за один проход массива (используя 6 доп.переменных для накопления результата). Парадокс в том, что не существует УНИВЕРСАЛЬНОГО ответа, какое решение лучше/быстрее/надёжнее. решение через сортировку достаточно просто ("просто" - насколько это можно говорить применительно к ассемблеру, конечно! ). Используем код сортировки. Он прост и отработан. Готовый код сортировки легко найти и использовать. Его легко отлаживать. Преимущество - если в задаче нужно будет найти не 3-и по порядку, а 4-е экстремальные числа (или даже номер этих чисел будет задаваться оператором в диалоговом режиме) - это абсолютно никак не повлияет на алгоритм - доработка будет минимальнейшей. Недостатки: неоптимальность/неэффективность с точки зрения быстродействия (проявится, только при достоточно больших размерах исходного массива. При N=10 (или 50,100,1000 элементов) разницы в быстродействии пользователь программы явно не заметит! Решение с дополнительными (в данном случае шестью ) переменными. Оптимальное с точки зрения быстродействия/эффективности. Неоптимальное с точки зрения сложности алгоритма, модификации (гибкости) и отладки. Просто представьте, сколько потребуется изменений, если нужно будет найти не третьи, а, скажем, 5-е экстремальные числа... И, кстати, рекомендую ознакомится с небольшой дискуссией по такой же проблеме здесь - 3 максимальных элемента массива (pascal) p.s. RACOST, если бы Вам нужно было на языке Паскаль, то Вы бы давно уже или написали код самостоятельно или получили тут на форуме советы/подсказки/готовый код, но писать такую муть на Ассемблере - нудно и скучно... |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
asm? | Tymchuk | C++ Builder | 1 | 18.05.2012 21:29 |
Передача параметров asm-asm | Maksimall89 | Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM | 0 | 22.12.2011 11:54 |
asm | dosha | Фриланс | 2 | 04.03.2011 01:59 |
Asm в С++ | ge4r | Помощь студентам | 0 | 17.10.2010 17:26 |
с++ и ASM | breate | Общие вопросы C/C++ | 4 | 04.11.2009 20:56 |