Найти минимум в массиве используя наиболее оптимальный алгоритм

@_Ivana · Регистрация: 01.03.2013

Студворк — интернет-сервис помощи студентам

Дан массив чисел, надо найти минимум. Препод сказал - дополнительное задание: предложить наиболее оптимальный алгоритм, написать код, реализующий его идею, и обосновать его теоретически.

IGPIGP · 06.08.2016, 09:31

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

Или я не прав?

Или. Вот тут в самом начале темы о minimax это есть:
Найти минимум в массиве используя наиболее оптимальный алгоритм
Но до вступления ValeryS, никто из читавших не признался, что это тоже 3N/2. Настолько буднично выглядит код.
Но вы не только это не прочли.

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

О чём Вы всю ночь рассуждали?

Мы о сортировке выбором усиленной данным алгоритмом рассуждали. Я задал вопрос о том, видел ли кто-нибудь подобную реализацию. На это пока ни кто не ответил положительно.
HenryDukart, составил мне хорошую компанию по сравнению алгоритмов по Кормэну и в более простой редакции предложенной мной. Дело в том, что у Кормэна выборка идёт парами в отличие от... Дальше не хочу пересказывать. Прочтите сами.
LVV, не грустите. Тут не Вы первый заходите когда уже тема надулась с воздушный шар, с фразой "Ну и что тут происходит?" (мягко говоря). Бывает.

Добавлено через 12 минут

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

IGPIGP, заметил ошибочку в алгоритме сортировки.

Отлично! Чуть позже посмотрю, спасибо)

ValeryS · 06.08.2016, 09:51

LVV, ужель бы ты посмотрел на личность ТС, то понял бы что

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

Препод сказал

явный стеб, какой ему препод, он сам в преподы годится

в поддержку этого стеба я и написал 14 пост
теперь мои рассуждения по теме
решение из 14 поста самое простое, интуитивно понятное и ошибок там наделать очень трудно(хотя и возможно

)
но имеет два узких места цикл и ветвление

что одно, что другое для процессора с конвейером, как серпом по шее
ну с циклом можно бороться разверткой цикла
а вот ветвление?
и все начали с ним бороться
но дело в том что у современных процессоров, кроме предсказания переходов, есть еще один плюс, заменять ветвление линейным кодом
например конструкция

C
1
2
3
4
if(c<a)
 c=a;
else
 c=b;

в зависимости от условия
может превратится в такую

C
1
2
 c=a;
NOP();

C
1
2
NOP();
c=b;

NOP() это "нет операции" выполняется за один такт, так же и как присвоение, такой функции разумеется в Си нет, это, так скажем, псевдокод.
и превращать этот код будет не компилятор а процессор во время исполнения
так что вполне возможно что дубовый алгоритм будет быстрее чем более продвинутый
в общем тестировать надо

Байт · 06.08.2016, 12:09

Вот такой приснился любопытный алгоритм. (Если он уже встречался в данном обсуждении - не обессудьте, прочесть всю сотню сообщений мне было не под силу).Алгоритм вообще не использует сравнений, так что по этому критерию он весьма оптимален.
Изготавливаем N шариков (можно кубиков) одинакового объема с весами, пропорциональными значениям элементов массива. Помещаем их в жидкость. Постепенно увеличиваем плотность жидкости, пока шарик (кубик) с минимальным весом не останется на поверхности в одиночестве.
Возможны варианты. Например, вместо жидкости использовать газ, что позволит технически проще менять плотность среды.
Детали типа "А если все шарики сразу потонут", я для ясности изложения опустил

IGPIGP · 06.08.2016, 12:29

Сообщение от Байт

пока шарик (кубик) с минимальным весом не останется на поверхности в одиночестве.

Это нормально. Спелые арбузы так отбирают. Рекурсивная (или циклическая) попарная последовательная перестановка до тех пор пока есть, что переставлять вполне реализует такое всплытие, $https://www.cyberforum.ru/cgi-bin/latex.cgi?N^2$ сравнений и перестановок.

Байт, Вы это знали ещё когда я и не думал программировать. Это был сарказм или философская патетика?

@Ferrari F1 · 06.08.2016, 13:23

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

Вы это знали ещё когда я и не думал программировать

а когда вы решили дать вызов всему миру и начать программировать?

IGPIGP · 06.08.2016, 13:41

Сообщение от Ferrari F1

а когда вы решили дать вызов всему миру и начать программировать?

Если не считать мелочей по производственной необходимости, в числе которых программа расчёта термодинамических свойств воды и пара (здоровущая и жуть какая плохая прога на GW-Basic которая потом переводилась на TB и QB), это случилось зимой 2011. В 2012 я написал маленькую и жуткую прогу. В 13-м зарегистрировался тут. Очень много полезного узнал. Но я не программер, всё-таки. Многовато пробелов. Так что о вызове миру сказать было бы слишком громко.

@Ferrari F1 · 06.08.2016, 13:52

IGPIGP, мне нравится наблюдать ваш каждодневный оптимизм даже несмотря на ваш возраст

Байт · 06.08.2016, 14:49

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

Это был сарказм или философская патетика?

С одной стороны, если ТС позволил себе небольшой стеб в этом топике, то чем я, собственно хуже.
С другой, есть тут такая награда - "Приколист". И иногда хочется на нее попретендовать. Хотя я прекрасно осознаю, насколько мне далеко до корифеев этого жанра.

@Ferrari F1 · 06.08.2016, 14:51

Байт, вы 18 летний приколист)

Байт · 06.08.2016, 14:56

Не по теме:

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

Спелые арбузы так отбирают

Что касается арбузов, то лучше моей тещи от первого брака никто арбузов не выбирал. Она казачка с Дона. А выведать алгоритма я у нее так и не смог. На все вопросы она отвечала - "Ну это же видно!"

Добавлено через 2 минуты

Не по теме:

Сообщение от Ferrari F1

Байт, вы 18 летний приколист)

Не стоит так уж доверчиво относиться к тому, что опубликовано в профиле. Профиль - тоже неплохое место для приколов:)

@Ferrari F1 · 06.08.2016, 14:59

Не по теме:

Байт, все мы понимали, что это был :sarcasm:

IGPIGP · 06.08.2016, 15:58

Не по теме:

Сообщение от Байт

Что касается арбузов, то лучше моей тещи от первого брака никто арбузов не выбирал. Она казачка с Дона. А выведать алгоритма я у нее так и не смог.

Тут тёщи вне конкуренции. Моя, от последнего брака тоже знала в этом толк, земля ей пухом.
У нас с женой, такая ~~алгоритма~~ примета была: если после того как мы оставили арбузы в холодильнике и ушли, а потом придя увидели тёщу зелёной и полосатой, то арбузы были спелыми! :yes:

Сообщение от Ferrari F1

мне нравится наблюдать ваш каждодневный оптимизм даже несмотря на ваш возраст

Это не оптимизм. Я пессимист и ненавистник. Ненавижу портить кому-то настроение. И не люблю тех кто это любит. А возраст при чём? Тут есть мало людей, кого я не уделаю на турнике или на беговой дорожке и что? Да Вы и не женщина вроде, чтобы учитывать это обстоятельство, хоть каким-либо образом.:)

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

В 13-м зарегистрировался тут.

В в 2011 и зарегистрировался.:wall: Жара... :pardon:

@LVV · 06.08.2016, 17:00

Сообщение от Байт

Изготавливаем N шариков (можно кубиков) одинакового объема с весами, пропорциональными значениям элементов массива. Помещаем их в жидкость. Постепенно увеличиваем плотность жидкости, пока шарик (кубик) с минимальным весом не останется на поверхности в одиночестве.
Возможны варианты. Например, вместо жидкости использовать газ, что позволит технически проще менять плотность среды.

Ну, при повышении плотности жидкости шарик с минимальным весом всплывёт первым и "останется на поверхности в одиночестве" если Вы сразу же прекратите повышать плотность жидкости.

А как это реализовать программно?
Например, задан массив положительных целых чисел.
Чтобы найти минимальное, то есть определить какое число "всплывёт" первым, я должен каждое из чисел массива сравнивать сначала с единицей, потом с двойкой и т д, пока не произойдёт "всплытие".
И где здесь выигрыш в скорости поиска минимального числа?
Для поиска минимального из двух чисел 1000000 и 1000001 я должен 999999 раз дискретно повышать плотность жидкости от 1 до 1000000 и сравнивать с двумя числами, а это почти 2000000 операций.

@HenryDukart · 06.08.2016, 17:07

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

я должен каждое из чисел массива сравнивать сначала с единицей

А еще же и отрицательные числа есть.

IGPIGP · 06.08.2016, 17:59

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

А как это реализовать программно?

Для реализации всплытия многих шариков, нужно столько же независимых потоков исполнения. Иначе модель не адекватна. Что касается изменения плотности с целью фильтрации фракции или, в пределе, одного ~~яблока~~ шарика, то легко показать, что технически метод имеет, относительно плохую разрешающую способность, если говорить о технически реализуемом процессе. Но в идеале это возможно. Вообще, разделение происходит под действием потока на поток. Вот песок разных фракций летит в космосе с одинаковой скоростью. Включаем атмосферу (без гравитации) и сопротивление газа действуя на песчинки разного размера начинает разделение.
А где в стоячей воде поток, там же архимедова сила и всё, спросите вы. Там есть поток гравитационного поля создающий силы. Интересно действует сила переменного направления. Можно заставить кастрюлю с шарами вибрировать или вращаться и получим вибро-разделение или центрифугирование. Последнее не нуждается в гравитации. И пыли меньше.

Так вот о переменных воздействиях для разделения:
Можно модифицировать, меняя плотность бинарно. Много - все всплыли (более одного, что для нас важно), мало, - никто не всплыл. Пополамим пока не останется только один (Who wants to live forever...).
Процессоров надо много. Независимый доступ к памяти и очень быстрая общая шина. Звучит очень трудно.

@LVV · 06.08.2016, 18:07

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

А еще же и отрицательные числа есть

Ответ:

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

Например, задан массив положительных целых чисел.

Добавлено через 5 минут

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

Для реализации всплытия многих шариков, нужно столько же независимых потоков исполнения. Иначе модель не адекватна. Что касается изменения плотности с целью фильтрации фракции или, в пределе, одного яблока, то легко показать, что технически метод имеет, относительно плохую разрешающую способность, если говорить о технически реализуемом процессе. Но в идеале это возможно. Вообще, разделение происходит под действием потока на поток. Вот песок разных фракций летит в космосе с одинаковой скоростью. Включаем атмосферу (без гравитации) и сопротивление газа действуя на песчинки разного размера начинает разделение.
А где в стоячей воде поток, там же архимедова сила и всё, спросите вы. Там есть поток гравитационного поля создающий силы. Интересно действует сила переменного направления. Можно заставить кастрюлю с шарами вибрировать или вращаться и получим вибро-разделение или центрифугирование. Последнее не нуждается в гравитации. И пыли меньше.

С точки зрения банальной эрудиции не каждый индивидуум способен различать парадоксальные эмоции.

Вы еще не учли принцип неопределённости Гейзенберга и корни уравнения Шредингера для движущихся песчинок.

IGPIGP · 06.08.2016, 18:28

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

С точки зрения банальной эрудиции не каждый индивидуум способен различать парадоксальные эмоции.

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

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

Вы еще не учли принцип неопределённости Гейзенберга и корни уравнения Шредингера для движущихся песчинок.

Вот это дело. Ждём в разделе Физика

А по существу, так там только самые общие факторы разделения и в самых общих формулировках. Бинарный поиск, я бы сравнил с отделением сливок. Есть разные способы разделения: методом вибрации (взбивание), методом центрифугирования (центробежная сепарация), а можно в крынке на окно поставить (~~всплытие~~ гравитационная сепарация о которой мы говорим - самая медленная). Кто скажет что это отстой, тот просто, не пробовал и все.

@Puporev · 06.08.2016, 20:56

Наиболее оптимальный способ нахождения особого элемента массива это применение алгоритма быстрой сортировки.

IGPIGP · 06.08.2016, 23:01

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

IGPIGP, заметил ошибочку в алгоритме сортировки.

И правда. Когда не выполняется ни одно из условий получается неприятность. Ты решил достаточно остроумно.

C++
1
2
3
comparison_count++;
if (max_val_ind == left_ind)
max_val_ind = min_val_ind;

Как я не старался, а лучше не получается. И если поставить счетчик, то проигрыш иногда более 30%.

@Ромаха · 06.08.2016, 23:56

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

Наиболее оптимальный способ нахождения особого элемента массива это применение алгоритма быстрой сортировки.

Нет. К-ая порядковая статистика

Новые блоги и статьи Все статьи Все блоги /
FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .
Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32

	Найти минимум в массиве используя наиболее оптимальный алгоритм 03.08.2016, 22:30. Показов 15445. Ответов 186 Метки нет (Все метки) Дан массив чисел, надо найти минимум. Препод сказал - дополнительное задание: предложить наиболее оптимальный алгоритм, написать код, реализующий его идею, и обосновать его теоретически. 4

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	06.08.2016, 12:09
	Вот такой приснился любопытный алгоритм. (Если он уже встречался в данном обсуждении - не обессудьте, прочесть всю сотню сообщений мне было не под силу).Алгоритм вообще не использует сравнений, так что по этому критерию он весьма оптимален. Изготавливаем N шариков (можно кубиков) одинакового объема с весами, пропорциональными значениям элементов массива. Помещаем их в жидкость. Постепенно увеличиваем плотность жидкости, пока шарик (кубик) с минимальным весом не останется на поверхности в одиночестве. Возможны варианты. Например, вместо жидкости использовать газ, что позволит технически проще менять плотность среды. Детали типа "А если все шарики сразу потонут", я для ясности изложения опустил 1

@Ferrari F1 807 / 534 / 158 Регистрация: 27.01.2015 Сообщений: 3,017 Записей в блоге: 1
	06.08.2016, 13:52
	IGPIGP, мне нравится наблюдать ваш каждодневный оптимизм даже несмотря на ваш возраст 1

@Ferrari F1 807 / 534 / 158 Регистрация: 27.01.2015 Сообщений: 3,017 Записей в блоге: 1
	06.08.2016, 14:51
	Байт, вы 18 летний приколист) 0

@Ferrari F1
	06.08.2016, 14:59
	Не по теме: Байт, все мы понимали, что это был :sarcasm: 0

@Puporev Почетный модератор 64320 / 47616 / 32743 Регистрация: 18.05.2008 Сообщений: 115,167
	06.08.2016, 20:56
	Наиболее оптимальный способ нахождения особого элемента массива это применение алгоритма быстрой сортировки. 0