Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 05.02.2011, 00:00
Новичок

Отправить личное сообщение для habrageek Посмотреть профиль Найти все сообщения от habrageek
 
Регистрация: 04.02.2011
Сообщений: 4

Простой поиск Двух максимальных (минимальных) чисел в массиве.
Здравствуйте, уважаемые форумчане!
Это мое первое сообщение.
Искал в поиске по словам "поиск двух масимальных" не нашел.

Решаю тут по информатике задачки первокурсникам на Паскале. Такой вопрос: как сделать красивый алгоритм для поиска двух максимальных(минимальных) элементов в массиве.

Точнее: можно ли найти оба максимальных элемента в одном проходе цикла?

(Или только найти сперва максимальный, а потом второй максимальный?)
  #2  
Старый 05.02.2011, 00:05
гocть

 
Сообщений: n/a

Цитата:
Точнее: можно ли найти оба максимальных элемента в одном проходе цикла?
конечно можно. идешь по массиву и хранишь два наибольших из найденных.

если надо k максимальных, для больших k лучше хранить их в куче. (двоичной куче)
  #3  
Старый 05.02.2011, 00:05
Новичок

Отправить личное сообщение для habrageek Посмотреть профиль Найти все сообщения от habrageek
 
Регистрация: 04.02.2011
Сообщений: 4

Если кому интересно, то вот мои мысли (на Паскале):

Код:
{*
for i:=2 to n do
if (odd(i)) then
begin
  if (a[i]<=a[min2]) then
	  begin
	   if (a[i]<=a[min1]) then
	    begin

	     min1:=i;
	     if (i<>1) then min2:=pred(min1) ;
	    end
	   else
	    min2:=i;
	 end;

end;
*}
там надо было нечетные к тому же искать..
не работает(
  #4  
Старый 05.02.2011, 08:57
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>там надо было нечетные к тому же искать..
Постановочка задачи-то хромает....
  #5  
Старый 06.02.2011, 22:38
Новичок

Отправить личное сообщение для habrageek Посмотреть профиль Найти все сообщения от habrageek
 
Регистрация: 04.02.2011
Сообщений: 4

min
получается если минимальное число стоит первым, то второе по минимальности он уже не найдет. Как это учесть? Не могу придумать...
MBo,
есть такое(
  #6  
Старый 06.02.2011, 23:13
Новичок

Отправить личное сообщение для habrageek Посмотреть профиль Найти все сообщения от habrageek
 
Регистрация: 04.02.2011
Сообщений: 4

Сообщение от гocть Посмотреть сообщение
конечно можно. идешь по массиву и хранишь два наибольших из найденных.

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

у меня получается только самый минимальный найти, а если второй по минимальности на второй позиции? Тогда в if-е нужно учитывать еще if (a[i]>secondmin) чтоле?
  #7  
Старый 07.02.2011, 12:50
гocть

 
Сообщений: n/a

Сообщение от habrageek Посмотреть сообщение
как это сделать с минимальными?
ну хранишь в max-heap'е вместо min-heap'а и все, чтобы на каждом шаге удалять из хипа максимум. для 2-х элементов хип не нужен, массив, или две переменных хватит

Цитата:
получается если минимальное число стоит первым, то второе по минимальности он уже не найдет. Как это учесть? Не могу придумать
знач баг у тебя в коде пиши с нуля.

че там думать? сортировку вставками проходил? на каждом шаге тебе нужно вставить ей элемент в массив из 2-х элементов.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
наибольшее простое число, делитель двух чисел гость Математические алгоритмы (другое) 5 01.10.2009 18:54
Поиск различий в двух деревьях RAPTORGrrr Математические алгоритмы 1 14.09.2008 01:18
Поиск различий в двух деревьях RAPTORGrrr Графы 0 15.08.2008 23:15
Поиск в массиве чисел всех интервалов с разнастью между элементами в еденицу. phprus Сортировка и поиск 2 15.01.2008 11:23
поиск всех максимальных паросочетаний force_sk Графы 1 29.09.2006 09:14