Уроки 34 - 36
§ 20. Обработка массивов
Содержание урока
Перестановка элементов массива
Линейный поиск в массиве
Практическая работа № 15 «Перестановка элементов массива»
Практическая работа № 16 «Линейный поиск в массиве»
Практическая работа № 17 «Сортировка»
Линейный поиск в массиве
Очень часто требуется найти в массиве заданное значение или определить, что его там нет. Для этого нужно просмотреть все элементы массива с первого до последнего. Как только будет найден элемент, равный заданному значению X, надо завершить цикл и вывести результат. Такой поиск называется линейным.
Сколько операций сравнения придётся выполнить, если в массиве N элементов? В каком случае количество сравнений будет наименьшим? Наибольшим?
Катя торопилась и написала такой алгоритм линейного поиска:
i:=1
нц пока A[i]<>Х i:=i+l
кц
вывод 'А [', i,'] = ',X
Проверьте: правильно ли сработает алгоритм, если искать в массиве {1, 2, 3} число 2? Число 4?
Этот алгоритм хорошо работает, если нужный элемент в массиве есть, однако приведёт к ошибке, если такого элемента нет, — получится зацикливание и выход за границы массива. Чтобы этого не произошло, в условие нужно добавить ещё одно ограничение: i <= N. Если после окончания цикла это условие нарушено, это означает, что поиск был неудачным — элемента нет:
В сложном условии i <= N и А [i] <> X первым должно проверяться именно отношение i <= N. Если первая часть условия, соединённого с помощью операции И, ложна, то вторая часть не вычисляется — уже понятно, что всё условие ложно. Дело в том, что, если i > N, проверка условия А [i] <> X приводит к выходу за границы массива, и программа может завершиться аварийно.
Возможен ещё один поход к решению этой задачи: используя цикл с переменной, перебрать все элементы массива и досрочно завершить цикл, если найдено требуемое значение:
Для выхода из цикла используется оператор выход (в Паскале — break), номер найденного элемента сохраняется в переменной nХ. Если её значение осталось равным нулю (не изменилось в ходе выполнения цикла), то в массиве нет элемента, равного X.
Следующая страница 
Сортировка массивов
Cкачать материалы урока
