VPF::Поиск минимального числа из массива

Melancholic

Дата 22.5.2008, 08:31 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 31
Регистрация: 8.5.2007

Репутация: нет
Всего: нет

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

Код


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 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18

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

Akina

Дата 22.5.2008, 09:12 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Цитата(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 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2069
Регистрация: 3.11.2005
Где: Красноярск

Репутация: 2
Всего: 17

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

--------------------

Ничто так не развивает аналитическое мышление, как отладка сложной программы без возможности пошагового выполнения (с)

Melancholic

Дата 22.5.2008, 20:21 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 31
Регистрация: 8.5.2007

Репутация: нет
Всего: нет

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

Цитата

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 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18

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

Mayk

Дата 23.5.2008, 05:06 (ссылка)

(нет голосов)

Загрузка ...

^аВаТаР^ сообщение>>

Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: 2
Всего: 134

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

)

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

--------------------

Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.

sergejzr

Дата 22.7.2008, 19:02 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 4
Всего: 360

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

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »