(курс 68 ч.) Перестановка элементов массива | Линейный поиск в массиве (informatika_09_68_pol) (68 часов в уч. год)

Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, углубленный уровень)


Уроки 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качать материалы урока







Наверх