Алгоритмы обработки массивов - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Алгоритмы обработки массивов. Доклад-сообщение содержит 16 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

АЛГОРИТМЫ ОБРАБОТКИ МАССИВОВ: ПОИСК И СОРТИРОВКА.

Слайд 2

Описание слайда:

Эффективность алгоритма Алгоритмы можно разделить на два класса: Алгоритмы с повторением. число операций в цикле число циклов Рекурсивные алгоритмы. число операций разбиения на подзадачи выполнение алгоритма каждой подзадачи объединение результатов.

Слайд 3

Описание слайда:

При оценке эффективности алгоритма нужно выбрать наиболее значимую операцию или группу операций. Операции сравнения. Арифметические операции.

Слайд 4

Описание слайда:

Классы входных данных При оценке эффективности алгоритма нужно попытаться разбить входные данные на классы и оценить поведение алгоритма на каждом из них. Пример: Определить максимальное число из набора 10 чисел. Число возможных наборов входных данных – N!. 10!= 3628800

Слайд 5

Описание слайда:

Наборы данных можно разбить на 10 классов по месторасположению максимального числа: Наборы данных можно разбить на 10 классов по месторасположению максимального числа: Максимальное число на первом месте Максимальное число на втором месте Максимальное число на третьем месте …………………………………………………………………………………….. 10. Максимальное число на десятом месте Следовательно нужно оценить эффективность только 10 вариантов, а не 10!

Слайд 6

Описание слайда:

Варианты отличаются друг от друга числом перестановок в зависимости от местоположения наибольшего элемента. Наилучший случай, когда наибольший элемент находится на первом месте, наихудший – на последнем. Варианты отличаются друг от друга числом перестановок в зависимости от местоположения наибольшего элемента. Наилучший случай, когда наибольший элемент находится на первом месте, наихудший – на последнем. Эффективность любого алгоритма проверяется исходя из анализа трёх вариантов набора начальных данных: Наилучший случай; Наихудший случай; Средний случай. Для определения максимального и минимального чисел из набора 10 чисел нужно сформировать 90 классов входных данных

Слайд 7

Описание слайда:

Алгоритмы поиска. Списки данных могут быть двух типов – отсортированными или неотсортированными по какому-либо признаку (ключу). Элемент списка являющийся предметом поиска называется целевым элементом. Поиск обычно проводится не для того, чтобы убедиться в наличии того или иного элемента, а с целью получит какие-либо данные соответствующие данному ключу.

Слайд 8

Описание слайда:

Последовательный поиск. Поиск проводится в неотсортированном списке. Последовательно просматривается список элементов, начиная с первого. Элементов списка, соответствующих ключу, может быть несколько. Самый простой анализ – запись порядкового номера элементов в исходном списке, соответствующих ключу.

Слайд 9

Описание слайда:

Spisok – список элементов Kluch - целевой элемент i – индекс элемента исходного массива j – индекс элемента массива M(j) , соответствующего ключу. j:=1; for i:=1 to N do if Spisok(i)=Kluch then begin M(j):=i; j:=j+1; end

Слайд 10

Описание слайда:

Слайд 11

Описание слайда:

Двоичный поиск. Поиск проводится в отсортированном списке. Алгоритм поиска : Выбираем средний элемент списка и сравниваем его с ключом. Возможны три случая: Средний элемент списка меньше ключа; Средний элемент списка равен ключу; Средний элемент списка больше ключа. В соответствии с результатом сравнения ведутся последующие действия: Исключается из рассмотрения левая (меньше ключа) половина списка.; Поиск завершен; Исключается из рассмотрения правая (больше ключа) половина списка.

Слайд 12

Описание слайда:

SpSort – список элементов SpSort – список элементов Kluch - целевой элемент i – индекс элемента исходного массива nl:=1; - левая граница списка nr:=n; - правая граница списка k:=0; - признак завершения поиска repeat nsr := (nl+nr) div 2; - середина списка if SpSort(nsr) < Kluch then nl:=nsr; else begin if SpSort(nsr) = Kluch then begin k:=1; j:=i; end; else nr:=nsr; end; until k1;

Слайд 13

Описание слайда:

Слайд 14

Описание слайда:

Выборка. Задача - выбрать из списка элемент, не имеющий какого-либо конкретного значения. Например, выбрать запись с большим, меньшим, средним по величине элементом или, в общем случае, с К-ым по величине элементом.

Слайд 15

Описание слайда:

Алгоритм –1. Выбираем из списка наибольший элемент и помещаем его в конец списка. В оставшейся части выбираем наибольший элемент и помещаем его на второе место от конца списка. Продолжаем процедуру до тех пор, пока не дойдем до К-го по величине элемента.

Слайд 16

Описание слайда:

Алгоритм –2. Произведем перестановку списка (без сортировки) таким образом, что элементы меньшие по величине располагаются на местах с номерами меньшими номера ключевого элемента, а элементы большие - на местах с номерами большими номера ключевого элемента. После ряда итераций в ячейке с номером «К» будет располагаться интересующий нас элемент.