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

UptoLike

ВУЗ: 

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

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

Рубрика: 

37
Var C,A,B: integer;
Begin A:=1; B:=n k:=0;
While A<B do
Begin C:=(A+B)div 2;
If X[C]<P then A:=C+1
Else B:=C end;
If X[A]=P then k:=A
End;
В заключении приведем сравнительную таблицу.
Таблица 2. Сравнение линейного и бинарного методов поиска
Число
элементов
массива
Линейный поиск среднее
число сравнений,
необходимое для
выявления
Бинарный поиск
максимальное число
сравнений, необходимое
для выявления
n
Присутствия
элемента
Отсутствия
элемента
Присутствия
элемента
Отсутствия
элемента
7 4 7 3 3
100 50 100 7 7
1 000 500 1 000 10 10
1 000 000 50 000 1 000 000 20 20
Алгоритмы сортировки
Суть задачи сортировки заключается в перестановке элементов
числового массива в порядке возрастания или убывания значений с
увеличением номера элемента (Таблица 3, 4.). Индексы у цифр
показывают относительный порядок элементов с равными значениями.
Таблица 3. Пример сортировки по возрастанию
Номер элемента
1 2 3 4 5 6 7 8 9
Последовательность
2
1
49
2
2
1
1
4 5
2
3
9
1
2
Отсортированный
по возрастанию
1
1
1
2
2
1
2
2
2
3
4 5 9 49
38
Алгоритмы сортировки
ЛОС №3
ВСТАВК И
≤
>
>
ВЫБОР
?
1
2
ОБМЕН
3
!
≤
>
>
>
Рисунок 22. Лист опросного сигнала №3 
Var C,A,B: integer;
    Begin A:=1; B:=n k:=0;
                                                                                        ЛОС №3
                                                                                                  Алгоритмы сортировки
           While A            >
           В заключении приведем сравнительную таблицу.
Таблица 2. Сравнение линейного и бинарного методов поиска                                                              3
                  Линейный поиск среднее                   Бинарный поиск               ВЫБОР
  Число
                      число сравнений,                    максимальное число
элементов
                      необходимое для                   сравнений, необходимое
 массива
                         выявления                          для выявления
                 Присутствия Отсутствия                Присутствия Отсутствия
       n
                   элемента      элемента               элемента      элемента
         7                   4             7                      3            3
       100                  50           100                      7            7
     1 000                 500         1 000                     10           10         ОБМЕН
 1 000 000              50 000     1 000 000                     20           20

                          Алгоритмы сортировки

      Суть задачи сортировки заключается в перестановке элементов
числового массива в порядке возрастания или убывания значений с
увеличением номера элемента (Таблица 3, 4.). Индексы у цифр
показывают относительный порядок элементов с равными значениями.                                         ≤
Таблица 3. Пример сортировки по возрастанию
                                                                                                         >
Номер элемента              1      2    3    4    5     6   7    8   9
                                                                                                         >
Последовательность
Отсортированный
                            21     49   22   11   4     5   23   9   12
                                                                                                         >
                            11     12   21   22   23    4   5    9   49
по возрастанию



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

                                                                             37    38

Страницы