![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Поиск минимального (максимального) элемента. ⇐ ПредыдущаяСтр 3 из 3
Алгоритм поиска минимального (максимального) элемента массива следующий: сначала делается предположение, что первый элемент массива является минимальным (максимальным), затем остальные элементы массива последовательно сравниваются с этим элементом. Если во время очередной проверки обнаруживается, что проверяемый элемент меньше (больше) принятого за минимальный (максимальный), то этот элемент становится минимальным (максимальным) и продолжается проверка оставшихся элементов. PROCEDURE POISK_1 (x: massiv; VAR min: element); 1.2. Найти номер минимального элемента последовательности (все элементы различные). PROCEDURE MIN_NOM (x: massiv; VAR nomer: integer); 1.3. Найти минимальный элемент и его номер в последовательности с совпадающими элементами. PROCEDURE POISK_2 (x: massiv; VAR min: element; nomer: integer); Если поставлена задача отыскания первого по порядку следования минимального элемента и его номера, то используется условие: 'эталон' > 'текущее'. Поиск элемента с заданным значением. Требуется найти номер элемента с заданным значением (все элементы различные). Пусть задана последовательность {Xi}, i=1,..., N и переменная Р, которая называется поисковой (эталон). Известно, что в {Xi} все элементы имеют различные значения. Требуется определить номер элемента, значение которого равно значению Р. Самый поверхностный анализ выявляет особенность: в последовательности может не быть элемента со значением Р. Такую ситуацию надо рассмотреть при конструировании алгоритма. 2.1. Поиск в неупорядоченной последовательности. PROCEDURE NEUPPOS (var x: massiv; P: element); 2.2. Поиск в упорядоченной последовательности. · Если образец равен среднему элементу, то задача решена. · Если образец больше среднего элемента, то это значит, что искомый элемент расположен правее среднего элемента (между элементами с номерами i+1 и Nk), и за новое значение No принимается i+1, а значение Nk не меняется. · Если образец меньше среднего элемента, то это значит, что искомый элемент расположен левее среднего элемента (между элементами с номерами No и i-1), и за новое значение Nk принимается i-1, а значение No не меняется. 2. После того как определена часть массива, в которой может находиться искомый элемент, по формуле (Nk + N0) div 2 вычисляется новое значение i и поиск продолжается. Основой алгоритма является цикл, выполняемый неопределенное количество раз. В этом цикле интервал номеров делится пополам, получается номер под названием INDEX. Элемент с этим номером сравнивается с поисковой переменной Р. В зависимости от результата сравнения: перевычисляется No или Nk. Это повторяется до тех пор, не обнаружится элемент или No и Nk не совпадут, затем делается проверка X[No]=Р и по ее исходу формируется результат. PROCEDURE DICHOTOM (VAR x: massiv; P: element; Последовательный поиск. " Начать с начала и продолжать, пока не будет найден искомый ключ; затем остановиться". Эта последовательная процедура представляет собой очевидный путь поиска и может служить отличной отправной точкой для рассмотрения множества алгоритмов поиска, поскольку они основаны на последовательной процедуре. Двоичный поиск. Последовательный поиск выполняется очень быстро для небольших объёмов информации. Большие – намного быстрее обрабатывает алгоритм двоичного поиска. Алгоритм двоичного поиска сравнивает элемент в середине списка с искомым. Если искомый элемент меньше, алгоритм продолжает перебирать первую половину списка, если же он больше, чем найденный элемент, поиск продолжается во второй половине списка. На рисунке процесс поиска элемента со значением 44 изображен графически. Интерполяционный поиск. Двоичный поиск оптимизирует поиск полным перебором, так как исключает большие части списка, не проверяя значения пропускаемых элементов. Если известно, что значения распределены достаточно равномерно, то можно на каждом шаге исключить еще большее количество элементов, используя интерполяционный поиск. Program Sort;
PROCEDURE MIN_NOM (x: Array of integer; n: integer); VAR i, nomer, min: integer; BEGIN min: = x[1]; nomer: = 1; FOR i: = 2 to n do if x[i]< min then begin min: = x[i]; nomer: = i; end; Writeln (min); Write (nomer); END; Const Nmax = 100; Var X: Array [1..Nmax] Of integer; n, i: Integer; Begin Writeln('‚ўҐ¤ЁвҐ Є®«ЁзҐбвў® зЁбҐ«'); Readln(n); Writeln('‚ўҐ¤ЁвҐ ббЁў зЁбҐ«'); For i: = 1 To n Do Read (X[i]); MIN_NOM(X, n); readln(n); End.
|