Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Поиск минимального числа из массива

Автор: Melancholic 22.5.2008, 08:31

Задача в том, чтобы найти минимум из последовательности чисел. Самое популярное решение:

Код


min:=1; // пусть первый элемент минимальный 
for i:=2 to SIZE do
  if a[i]<a[min]then min:=i;

Имеется также рекурсивный алгоритм:

Код


Program Example _1;
Const n=10;
Type MyArray=Array[1..n] of Integer;
Const a : MyArray = (4,2, -1,5,2,9,4,8,5,3);
Function Min (a, b : Integer) : Integer;
Begin
  if a>b then Min := b else Min:=a;
End;
Function Pmin(n, b : Integer) : Integer;
Begin
  if n = 2 then Pmin := Min(n,a[1]) else Pmin := Min(a[n], Pmin(n-1,a[n]));
End;
BEGIN
  Writeln(‘Минимальный элемент массива  - ‘, Pmin(n,a[n]));
END.

Какие ещё варианты?

Автор: maxdiver 22.5.2008, 09:11

ггг
1) Отсортировать и взять 1-ый элемент
2) Построить дерево отрезков
3) Построить дерево Фенвика
4) Запихать числа в строку (дополняя числа нулями до одинаковой длины) и найти её наименьший циклический сдвиг
...
)))

Автор: Akina 22.5.2008, 09:12

Цитата(Melancholic @ 22.5.2008, 09:31

)

Имеется также рекурсивный алгоритм:

В программе минимум 2 ошибки - и если в строке 14 тупой синтаксис, то в строке 11 кривая логика. Попробуйте его на

Код

Const a : MyArray = (4,5,6,5,7,9,4,8,5,3);

Автор: ksili 22.5.2008, 09:17

Алгоритмы разные - первый ищет индекс минимального элемента, а второй - значение минимального элемента

Автор: Melancholic 22.5.2008, 20:21

Всем большое спасибо за содействие.

Цитата

1) Отсортировать и взять 1-ый элемент
2) Построить дерево отрезков
3) Построить дерево Фенвика
4) Запихать числа в строку (дополняя числа нулями до одинаковой длины) и найти её наименьший циклический сдвиг

Требуется наиболее шустрый.

Цитата

В программе минимум 2 ошибки - и если в строке 14 тупой синтаксис, то в строке 11 кривая логика. Попробуйте его на

Программа переписана:

Код


unsigned char r_min(unsigned char* a, int n)
{
  if(n > 2) return std::min(a[n-1], r_min(a, n-2)); else return std::min(a[0], a[1]);
}

Цитата

Алгоритмы разные - первый ищет индекс минимального элемента, а второй - значение минимального элемента

Второй переписан для поиска значения:

Код


  unsigned char min = c_numbers[0];
  for(int i = 0; i < NUMBERS_COUNT; i++)
    if(c_numbers[i] < min)
      min = c_numbers[i];

Вопрос в том, существует ли что-нибудь быстрее варианта последовательных сравнений? Нужен самый быстрый алгоритм.

Автор: maxdiver 22.5.2008, 22:31

Могу заверить, что асимптотически - быстрее некуда )
А с точки зрения оптимизации - ну наверно на асме можно как-то быстрее написать, но на Паскале - куда уж быстрее простого обхода массива for'ом.

Автор: Mayk 23.5.2008, 05:06

Цитата(Melancholic @ 23.5.2008, 00:21

)

для n неотсортиванных элементов очевидно требуется Θ(n) сравнений.

Автор: sergejzr 22.7.2008, 19:02

Ну если только распараллелить на n процессоров smile