Алгоритмические языки и программирование. Игошина Л.В. - 84 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Пусть задан массив Х, содержащий n целых чисел, расположенных в
порядке возрастания значений. Требуется найти заданное число isk.
18.1 Линейный поиск
Линейный поиск заключается в последовательном сравнении элементов
упорядоченного массива Х с искомым значением isk. Поиск заканчивается в
двух случаях:
1. Очередной элемент массива Х равен искомому значению isk, в этом
случае элемент найден.
2. Очередной элемент массива Х больше искомого значения, а так как
все последующие элементы также больше isk, то
искомого элемента
не может быть в Х.
Схема алгоритма линейного поиска
нет да
нет
да
В худшем случае для поиска заданного элемента алгоритмом линейного
поиска приходится проводить n сравнений, т.е. временная сложность
алгоритма ∼ n.
Текст программы линейного поиска
Uses crt;
Var
Начало
Ввод
данных
n,X,isk
Цикл
i=1,n
X[i] =
isk
X[i] >
isk
Элемента
нет
Элемента
найден
Конец 
     Пусть задан массив Х, содержащий n целых чисел, расположенных в
порядке возрастания значений. Требуется найти заданное число isk.

                             18.1 Линейный поиск

      Линейный поиск заключается в последовательном сравнении элементов
упорядоченного массива Х с искомым значением isk. Поиск заканчивается в
двух случаях:
      1. Очередной элемент массива Х равен искомому значению isk, в этом
         случае элемент найден.
      2. Очередной элемент массива Х больше искомого значения, а так как
         все последующие элементы также больше isk, то искомого элемента
         не может быть в Х.
                       Схема алгоритма линейного поиска


                                              Цикл
                                              i=1,n
               Начало


              Ввод                      нет                да
              данных                          X[i] =
              n,X,isk                          isk


                            нет     X[i] >             Элемента
                                     isk               найден

                                        да
                                  Элемента
                                  нет
                                                           Конец


     В худшем случае для поиска заданного элемента алгоритмом линейного
поиска приходится проводить n сравнений, т.е. временная сложность
алгоритма ∼ n.

                        Текст программы линейного поиска

        Uses crt;
        Var

Страницы