Основы алгоритмизации и программирования. Часть вторая. Типовые алгоритмы обработки массивов. Асламова В.С - 15 стр.

UptoLike

ВУЗ: 

АГТА | Ангарск

Составители: 

Рубрика: 

29
Алгоритмы поиска и сортировки
Алгоритмы поиска
Задача поиска заключается в отыскании последовательности
элемента с заданными свойствами его значения. Для детального анализа
алгоритмов поиска сформируем конкретные задачи.
1. Найти минимальное (максимальное) значение элемента
последовательности (все элементы разные).
2. Найти номер минимального (максимального) элемента
последовательности (все элементы разные).
3. Найти минимальный (максимальный) элемент и его номер в
последовательности с с
овпадающими номерами.
4. Найти номер элемента с заданным значением (все элементы
разные).
Поиск минимального элемента в массиве
Обратимся к листу опорного сигнала №2 (Рисунок 17.). Задача
поиска минимального элемента в массиве рассматривается как задача
определения самой маленькой клубники из всей, лежащей в ящике.
Сделаем из мягкой проволоки рамку размером с любую п
роизвольную
клубнику. Итак, мы задались исходным размером, назовем его эталоном.
Берем следующую клубнику и пытаемся ее пронести через рамку. Если
она не проходит, значит, она больше эталонной клубники и нас не
интересует. Если очередная клубника меньше эталона, то значит это уже
претендент на наименьшее значение. В этом случае, изменим эталон, до
разме
ра претендента на наименьшее, подкрутив проволоку, и продолжим
сравнение. Когда мы, таким образом, пропустим всю клубнику через
рамку, размер рамки и будет равен величине наименьшей клубники в
ящике.
Аналогично можно найти наибольшую клубнику в ящике, но в этом
случае рамку нужно увеличивать каждый раз до размеров большей
клубники.
Распространим эту идею на по
иск минимального элемента в
последовательности. Поиск будем проводить путем сравнения всех
элементов последовательности с эталонной переменной, которой
необходимо присвоить значение любого элемента последовательности,
например, первого.
30
Алгоритмы поиска
ЛОС №2
ЗНАЧЕНИЕ (РАЗМЕР)
МИНИМАЛЬНОЕ (МАКСИМАЛЬНОЕ) ЗНАЧЕНИЕ ЭЛЕМЕНТА
ЭТАЛОН ПРЕТЕНДЕН
Т
НОМЕР (МЕСТО)
НОМЕР МИНИМАЛЬНОГО (МАКСИМАЛЬНОГО) ЭЛЕМЕНТА
1
2 3 4
N – 1 N
ОТКУДА
1 K
РАЗМЕР И МЕСТО
НОМЕР И ЗНАЧЕНИЕ МИНИМАЛЬНОГО ЭЛЕМЕНТА
1
2 3 4
N – 1 N
1
K
N
≤
<
<
последний
текущий
первый
НЕУПОРЯДОЧЕН
НОМЕР ПО ЗНАЧЕНИЮ ЭЛЕМЕНТА
ДИХОТОМИЯ
А. ГРИН
Л. ТОЛСТОЙ
Х. ЧЕЙЗ
А. ПУШКИН
М. БУЛГАКОВ
Н. НОСОВ
Н. ВИРТ
ОСТРОВСКИЙ
Ж. ВЕРН
ТРЕБОВАНИЕ
Н. ВИРТ
АЛГОРИТМЫ И
СТРУКТУРЫ
ДАННЫХ
ТРЕБОВАНИЕ
Ф.М.ДОСТОЕВСКИЙ
СОБРАНИЕ
СОЧИНЕНИЙ
ТОМ 15
Ф.М.ДОСТОЕВСКИЙ
Ф.М.ДОСТОЕВСКИЙ
Ф.М.ДОСТОЕВСКИЙ
Ф.М.ДОСТОЕВСКИЙ
Ф.М.ДОСТОЕВСКИЙ
Ф.М.ДОСТОЕВСКИЙ
Ф.М.ДОСТОЕВСКИЙ
Ф.М.ДОСТОЕВСКИЙ
Ф.М.ДОСТОЕВСКИЙ
Ф.М.ДОСТОЕВСКИЙ
1
2
...
...
14
15
16
...
39
40
Рисунок 17. Лист опорного сигнала №2. 
               Алгоритмы поиска и сортировки
                                                                               ЛОС №2
                                                                                                  Алгоритмы поиска
                                                                               МИНИМАЛЬНОЕ (МАКСИМАЛЬНОЕ) ЗНАЧЕНИЕ ЭЛЕМЕНТА
                          Алгоритмы поиска
      Задача поиска заключается в отыскании последовательности
элемента с заданными свойствами его значения. Для детального анализа
алгоритмов поиска сформируем конкретные задачи.
   1.    Найти    минимальное     (максимальное)    значение   элемента
                                                                               ЗНАЧЕНИЕ (РАЗМЕР)                ЭТАЛОН ПРЕТЕНДЕНТ
        последовательности (все элементы разные).
                                                                                НОМЕР МИНИМАЛЬНОГО (МАКСИМАЛЬНОГО) ЭЛЕМЕНТА
   2.    Найти    номер    минимального     (максимального)    элемента
        последовательности (все элементы разные).
   3.    Найти минимальный (максимальный) элемент и его номер в
        последовательности с совпадающими номерами.                             1       2     3       4       N–1                                              N                                                                                               1                                                                 K
   4.    Найти номер элемента с заданным значением (все элементы
                                                                               НОМЕР (МЕСТО)                       ОТКУДА
        разные).
                                                                               НОМЕР И ЗНАЧЕНИЕ МИНИМАЛЬНОГО ЭЛЕМЕНТА




                                                                                                                                                                                                                                                                                                                                           текущий первый
Поиск минимального элемента в массиве
      Обратимся к листу опорного сигнала №2 (Рисунок 17.). Задача
                                                                                                                                                                                                                                                                       <                                          1
поиска минимального элемента в массиве рассматривается как задача
определения самой маленькой клубники из всей, лежащей в ящике.
                                                                                1       2     3       4       N–1                                              N
                                                                                                                                                                                                                                                                      <
Сделаем из мягкой проволоки рамку размером с любую произвольную                 РАЗМЕР И МЕСТО                                                                                                                                                                                                                       K




                                                                                                                                                                                                                               ≤
клубнику. Итак, мы задались исходным размером, назовем его эталоном.




                                                                                                                                                                                                                                                                                                                  последний
Берем следующую клубнику и пытаемся ее пронести через рамку. Если
она не проходит, значит, она больше эталонной клубники и нас не                НОМЕР ПО ЗНАЧЕНИЮ ЭЛЕМЕНТА                                                                                                                                                                 N
интересует. Если очередная клубника меньше эталона, то значит это уже          НЕУПОРЯДОЧЕН
претендент на наименьшее значение. В этом случае, изменим эталон, до           ТРЕБОВАНИЕ




                                                                                                                                                                                                                                                    ОСТРОВСКИЙ
                                                                                                                                                               А. ПУШКИН
                                                                                                                                                                                    М. БУЛГАКОВ
                                                                                                                    Л. ТОЛСТОЙ
размера претендента на наименьшее, подкрутив проволоку, и продолжим                   Н. ВИРТ




                                                                                                                                                                                                          Н. НОСОВ




                                                                                                                                                                                                                                                                          Ж. ВЕРН
                                                                                                          А. ГРИН


                                                                                                                                          Х. ЧЕЙЗ
сравнение. Когда мы, таким образом, пропустим всю клубнику через




                                                                                                                                                                                                                               Н. ВИРТ
                                                                                   АЛГОРИТМЫ И
рамку, размер рамки и будет равен величине наименьшей клубники в                   СТРУКТУРЫ
ящике.                                                                             ДАННЫХ
      Аналогично можно найти наибольшую клубнику в ящике, но в этом
случае рамку нужно увеличивать каждый раз до размеров большей                  ДИХОТОМИЯ




                                                                                                                       Ф.М.ДОСТОЕВСК ИЙ

                                                                                                                                            Ф.М.ДОСТОЕВСК ИЙ

                                                                                                                                                                 Ф.М.ДОСТОЕВСК ИЙ

                                                                                                                                                                                       Ф.М.ДОСТОЕВСК ИЙ

                                                                                                                                                                                                            Ф.М.ДОСТОЕВСК ИЙ

                                                                                                                                                                                                                                 Ф.М.ДОСТОЕВСК ИЙ

                                                                                                                                                                                                                                                       Ф.М.ДОСТОЕВСК ИЙ

                                                                                                                                                                                                                                                                            Ф.М.ДОСТОЕВСК ИЙ

                                                                                                                                                                                                                                                                                               Ф.М.ДОСТОЕВСК ИЙ

                                                                                                                                                                                                                                                                                                                        Ф.М.ДОСТОЕВСК ИЙ
клубники.                                                                      ТРЕБОВАНИЕ
                                                                                    Ф.М.ДОСТОЕВСКИЙ
      Распространим эту идею на поиск минимального элемента в
                                                                                    СОБРАНИЕ
последовательности. Поиск будем проводить путем сравнения всех                      СОЧИНЕНИЙ
элементов последовательности с эталонной переменной, которой                        ТОМ 15
необходимо присвоить значение любого элемента последовательности,
например, первого.                                                                                                          1                      2                 ...                  ...               14                   15                   16                      ...              39                       40



                                                                                            Рисунок 17. Лист опорного сигнала №2.

                                                                    29    30

Страницы