Функция поиска максимального элемента в массиве

Функция поиска максимального элемента в массиве

Дан массив X, состоящий из n элементов. Необходимо найти максимальный элемент массива и номер, под которым он хранится в массиве.

Алгоритм решения задачи следующий. Пусть в переменной с именем max хранится значение максимального элемента массива, а в переменной с именем Nmax – его номер. Предположим, что первый элемент массива является максимальным и запишем его в переменную max, а в Nmax – его номер (т.е. 1). Затем все элементы, начиная со второго, сравниваем в цикле с максимальным. Если текущий элемент массива оказывается больше максимального, то записываем его в переменную max, а в переменную Nmax – текущее значение индекса i.

Соответствующий фрагмент программы имеет вид:

Writeln(‘max= ’,max,’ Nmax= ‘,Nmax);

Сортировка массивов

Сортировка – распределение элементов массива по группам в соответствии с определенными правилами.

Линейная сортировка (сортировка отбором)

Идея линейной сортировки (например, по возрастанию) заключается в том, чтобы последовательно просматривая весь массив, отыскать наименьшее число и поместить его на первую позицию, обменяв его с элементом, который ранее занимал первую позицию. Затем просматриваются все остальные элементы массива и выполняется аналогичная операция по отбору из рассматриваемой части массива минимального элемента и обмену местами этого элемента и первого из рассматриваемой части и т.д.

var A: array[1..10] of integer;

for i:=1 to 10 do

for i:=1 to 10-1 do

for j:=i+1 to 10 do

for i:=1 to 10 do

где I – используется для указания позиции первого элемента в рассматриваемой части массива;

J – для указания позиции очередного сравниваемого с ним элемента;

Если условие A[i]>=A[j] выполняется, т.е. в неотсортированной части массива найден элемент, меньший, чем первый, то необходимо обменять местами эти элементы.

Генерация случайных чисел

Генерация случайных вещественных чисел (REAL) в диапазоне от 0 до 1 осуществляется с помощью функции RANDOM

Читайте также:  Адаптер не видит роутер

Если необходимо генерировать случайные числа в другом диапазоне, то необходимо преобразовать это выражение с помощью операций смещения и масштабирования. Например, для того, чтобы получить случайное число в диапазоне от 10 до 12, необходимо написать:

Для генерации целых случайных чисел (INTEGER) в диапазоне от 0 до N используется функция RANDOM с аргументом:

Для смены базы генерации случайных чисел, чтобы при каждом новом прогоне программы числа были другие, используется процедура RANDOMIZE. Обращение к этой процедуре идёт до обращения к функциям RANDOM.

Задача

Найти максимальный элемент численного массива.

Решение

Алгоритм решения задачи:

Значения, составляющие массив, могут быть получены из разных источников: путем вызова функции random, ввода значений пользователем, считывания из файла. В программе ниже используется первый вариант.
В задачах подобного рода (поиск максиму или минимума) может быть поставлена цель, найти только 1) индекс элемента, 2) только значение или 3) и то и другое. В программе ниже используется третий вариант.
Неплохо бы, чтобы при запуске программы весь массив выводился на экран. В этом случае пользователь может оценить правильность работы программы.

  1. В переменной max_num хранится текущее максимальное значение массива, а в max_index – его позиция (индекс).
  2. В программе можно выделить две части: заполнение массива числами с выводом их на экран (первый цикл for) и непосредственно поиск максимума (второй цикл for).
  3. Перед первым циклом запускается процедура randomize для того, чтобы при каждом запуске программы значения массива были разными.
  4. Изначально делается предположение, что первый элемент массива и есть максимум. Поэтому переменной max_indexприсваивается значение 1 (т.е. указатель на первый элемент массива), а max_num – непосредственно значение, хранящееся в первой ячейке массива.
  5. Начиная со второго элемента, каждое очередное значение массива сравнивается с текущим значением max_num. В случае, если текущее значение массива больше, чем хранящиеся в max_num, происходит новое присваивание обоим переменным текущего значения и индекса.
Читайте также:  Оптимальная видеокарта для игр 2018

Какой алгоритм для поиска максимума в случайном массиве использовать? В статье собрано 5 эффективных must-have алгоритмов.

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

В действительности, единственный способ точно найти самое большое число в случайном массиве будет перебор каждого числа в поисках максимума. Поэтому сложность такого алгоритма – O(N). Они называются линейными.

Простейшая реализация алгоритма на С:

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

Рассмотрим ситуацию на примере. Есть 200 карточек, на каждой из которых случайное число. Ваша задача найти карточку с самым большим числом. Допустим, друг согласился помочь, забрав половину карточек. Теперь каждый из вас ищет максимум из 100 карточек, вместо 200. Как только вы оба закончите, останется сравнить максимумы обеих половин. Время сократилось вдвое, но просмотреть пришлось все 200 карточек.

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

Есть ещё один вариант нахождения максимума в случайном массиве.
Идем по первой половине всех значений в массиве. Запоминаем самое большое. Назовём его Х. Далее проходим по второй половине. Когда (и если) находим значение, которое больше Х, останавливаемся. Обозначим его Y. Какова вероятность того, что Y – максимум в массиве?

Чтобы это утверждение было истинным, Y должно находиться во второй половине массива. А так как значения в массиве случайны, шанс такого = 50%. Тогда если второй максимум присутствует в первой половине, это гарантирует, что найден правильный максимум.

Читайте также:  Моноблок asus zen aio zn242gdk ca024t отзывы

Вероятность, что второй максимум в первой половине также = 50%. Посему вероятность, что и второй максимум в первой половине, и первый максимум во второй половине, равна 25%.

В итоге, такой алгоритм гарантирует точность 25% в нахождении максимума в массиве случайных чисел. Можно улучшить алгоритм, если искать второй максимум не в первой половине (1/2), а в 1/e (основание натурального логарифма) части массива. Этот способ впервые был предложен для решения задачи о разборчивой невесте или задачи секретаря (The Secretary Problem).

Спагетти-сортировка — прекрасный аналоговый алгоритм для решения задачи нахождения максимума в массиве.

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

Асимптотическая сложность такого алгоритма – O(1). Но в цифровом мире он не применим.

Алгоритм Гровера (или схема Гровера) используется в квантовых вычислениях для решения задач перебора. С его помощью сложность поиска максимума уменьшается до O(sqrt(N)) (большая О от корня N).

Данный способ решения может быть применен только на квантовом компьютере, что сильно умаляет его полезность в современном мире, но его нельзя не упомянуть.

Ссылка на основную публикацию
Adblock detector