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

Использование блока Scratch содержит — простой способ проверить, есть ли в списке определенный элемент. Но если мы хотим узнать позицию искомого элемента в списке, придется искать вручную.

В этом разделе вы познакомитесь с методом линейного поиска (после- довательного перебора), который позволяет вести поиск в списке. Этот прием нетруден для восприятия и легок в исполнении, и работает он с любым списком — отсортированным и беспорядочным. Но, поскольку при линейном поиске с заданной величиной надо сравнить все элементы в списке, операция может занять много времени.

Представим, что вы ищете некий элемент в списке фрукты. Если он в списке есть, вы хотите узнать его позицию. Процедура ПоисквСписке, показанная ниже проводит линейный поиск в списке фрукты.

Процедура ПоисквСписке с первого элемента начинает сравнивать названия фруктов в списке, одно за другим, с тем, что мы ищем. Объект поиска задан параметром цель. Процедура останавливается либо если величина найдена, либо если достигнут конец списка. Если скрипт находит нужную величину, переменная поз будет содержать позицию элемента. Иначе процедура меняет значение поз на неверную величину (–1 в данном случае), чтобы указать на отсутствие элемента в списке.

Величина поз указывает на два момента: содержится нужный нам элемент в списке или нет; если он в списке есть, какова его позиция. В ходе работы этой процедуры скрипт присвоит поз значение 4, указывая, что «Персик» найден на четвертой позиции списка фрукты.

Частота появления события

Предположим, в вашей школе проводится опрос о качестве питания в кафетерии. Учащиеся ставят еде оценки от 1 до 5 (1 — «плохо», 5 — «отлично»). Все ответы заносятся в список, и вас просят написать программу для обработки данных. Для начала школа хочет знать, сколько учащихся считают, что еда отвратительная (сколько из них поставили оценку 1). Как бы вы стали писать такую программу?

Вам явно нужна процедура, которая посчитает, сколько раз в списке появляется единица. Возьмем список, который содержит 100 случайных чисел. Процедура его наполнения данными показана ниже. Она добавит 100 случайных чисел от 1 до 5 в список под названием Опрос.

Теперь, когда у нас есть список оценок, мы можем посчитать, сколько раз в нем встречается заданная величина — 1. Для этого нужна проце- дура ПосчитатьЭлемент

Параметр цель — искомый элемент, а переменная элемКолич отслеживает, сколько раз он был найден. Процедура начинается с того, что переменной элемКолич присваивается значение 0, а затем стартует цикл повторить, ищущий в списке нужную величину. При каждом прохождении цикла происходит проверка элемента списка под соответствующим номером. Если элемент равен цели, скрипт увеличивает значение переменной элемКолич на 1.

Чтобы узнать, насколько учащиеся недовольны едой в кафетерии, надо вызвать процедуру ПосчитатьЭлемент с аргументом 1