Последовательный поиск в массиве

Часто возникает ситуация, когда в массиве необходимо найти определённый элемент.

Типовые задачи на поиск элемента в массиве:

·       поиск максимального или минимального элемента;

·       поиск элемента, имеющего конкретное значение.

Задача: Мальчики класса решили устроить соревнование на точность. Для этого на уроке физкультуры им всем были присвоены номера. После чего мальчики, начиная с участника с номером один, стали бросать баскетбольный мяч в кольцо, до первого промаха каждый.
(абзац) Написать программу, которая считывает количество попаданий у каждого и определяет номер победителя, а если их несколько, то выводит победителя с наименьшим номером.

Очевидно, что при решении данной задачи без использования компьютера, когда мальчики будут бросать мяч в кольцо, мы будем действовать следующим образом:

·       запишем результат и номер первого участника, полагая, что он победит;

·       далее, пока не закончатся участники, мы будем делать следующее:

·       смотреть сколько раз участник попал в кольцо;

·       если участник попал меньше или столько же раз, как и тот, результат которого мы записали до этого – его номер мы не записываем;

·       если участник попал в кольцо большее количество раз, чем тот, номер которого записан, – мы зачеркнём записанный номер и запишем новый и предположим, что этот участник победит.

Таким образом, в конце у нас будет записан номер участника, который попал в кольцо наибольшее количество раз.

Запишем данный алгоритм в форме программы. Назовём программу sorevnovanie. Нам понадобится переменная n, которая будет хранить количество участников, переменная i, которая будет хранить номер текущего участника и переменная r, которая будет хранить номер предполагаемого победителя. А также массив результатов a. Все данные задачи будут принадлежать к целочисленному типу integer.

Между служебными словами begin и end запишем тело программы. Вначале выведем на экран поясняющее сообщение о том, что это программа определения победителя в соревнованиях по броскам мяча в корзину, а также запрос на ввод количества участников. Считаем переменную n с переходом на следующую строку. Запишем цикл for i:=1 to n do, в котором будут команды вывода на экран запроса на ввод результата i-того участника, а так же считывания i-того элемента массива a.

После цикла будет следовать команда r:=1, т. е. мы полагаем, что победит первый участник.

Далее, так как результат первого участника уже сохранен, начнём просматривать результаты со второго. При помощи цикла for i:=2 to n do, мы будем сравнивать результат предполагаемого победителя с последующими, и если i-тый участник попал в кольцо большее количество раз – он становится предполагаемым победителем, то есть присвоим переменной r значение i. В конце выведем поясняющее сообщение с текстом «Победил участник под номером», и значение переменной r.

Исходный код программы

Запустим программу на выполнение. Пусть было пятеро участников. Первый попал в кольцо десять раз, второй - семь, третий – одиннадцать, четвёртый – пятнадцать и пятый – восемь. Таким образом, результатом должна быть победа четвёртого участника.

Результат работы программы

Результат работы программы соответствует ожидаемому – следовательно, задача решена верно.

Еще одним типом задач являются задачи на поиск элемента в массиве по указанному значению.

Задача: Определить, есть ли в последовательности n случайных чисел от 1 до 100 число равное k. Если есть – вывести номер, под которым оно встречается впервые, а если нет – вывести слово «Нет».

Для решения данной задачи нам понадобится последовательность чисел, хранящаяся в массиве a, длина данной последовательности n, номер текущего элемента последовательности i, искомое число k.

Составим блок-схему алгоритма решения данной задачи.

Для начала необходимо ввести длину последовательности чисел, а также искомое число. Затем будут следовать циклы для генерации последовательности случайных чисел длины n и для вывода её элементов на экран.

Теперь перейдём к поиску. Для этого переменной i присвоим значение 1 и будем перебирать элементы пока они не закончатся или пока не найдём искомый. Цикл поиска будет содержать всего одну команду – увеличения i на 1. Таким образом, в конце нам достаточно будет проверить, равен ли i-тый элемент массива a заданному k. Если равен, выведем поясняющее сообщение «Номер искомого элемента последовательности» и значение i. Если же не равен, выведем слово «Нет». В конце блок-схемы следует блок «Конец».

Блок-схема алгоритма

Запишем программу по данной блок-схеме. Назовём её poisk. В разделе описания переменных будет массив из ста элементов типа integer, а также переменные n, i и k типа integer.

Запишем тело программы. Выведем с переходом на следующую строку поясняющее сообщение о том, что это программа поиска элемента k в последовательности из n случайных чисел. Теперь выведем запрос на ввод n и считаем её, то же сделаем и для k. Запишем цикл for i:=1 to n do, который будет содержать команду присваивания i-тому элементу массива a, суммы случайного числа от 0 до 99 и 1. Теперь запишем такой же цикл for i:=1 to n do, который будет содержать одну команду вывода i-того элемента массива a через пробел.

Теперь выполним поиск в последовательности случайных чисел элемента равного k. Для этого, согласно блок-схеме, мы будем перебирать элементы, пока они не закончатся, или пока не найдём равный k. Для этого присвоим i:=1 и запишем цикл while с условием i<n и a[i]<>k, содержащий команду увеличения i на 1.

Теперь для вывода ответа мы должны перейти на следующую строку – для этого достаточно записать оператор writeln без параметров. Для проверки того, нашли ли мы нужный элемент, запишем условный оператор с условием, что a[i]=k, в случае выполнения условия выведем на экран значение i, в противном случае выведем слово «Нет».

Исходный код программы

Запустим программу на выполнение и введём длину последовательности, равную 15 и k, равное 3. В последовательности, сгенерированной программой, есть элемент равный 3 на первой позиции, программа вывела число 1. Ещё раз запустим программу на выполнение и введём длину последовательности, равную 10, и искомый элемент, равный 70. В последовательности, сгенерированной программой, элемента с таким значением нет, и программа вывела слово «Нет». Программа работает правильно. Задача решена.

Результаты работы программы

Также при поиске удобно использовать цикл с пост условием repeat, который записывается в следующей форме. Записывается служебное слово repeat, после которого идёт тело цикла, то есть последовательность команд, которая будет повторяться. После чего записывается служебное слово until, после которого идёт условие, при выполнении которого цикл прекратит работу. Обратим внимание, что при записи тела цикла repeat служебных слов begin и end не требуется, а условие, в отличии от цикла while, проверяется после выполнения тела цикла.

Изменим текст нашей программы. До поиска элемента программа будет такой же. Перед циклом поиска нужно присвоить переменной i значение 0, так как условие будет проверяться уже после увеличения i на 1. Вместо строки while с условием запишем служебное слово repeat, а после тела цикла – служебное слово until. Цикл будет выполняться, пока i-тый элемент массива a не будет равен k или пока i не станет равным n.

Исходный код изменённой программы

Ещё раз запустим программу на выполнение. Введём длину последовательности, равную 20, и k, равное 7. В сгенерированной программой последовательности такого элемента нет, и программа вывела на экран слово «нет». Ещё раз запустим программу на выполнение и введём длину последовательности, равную 10 и k, равное 40. В последовательности случайных чисел число сорок находится на второй позиции, и программа вывела на экран число 2. Программа работает верно.

Результаты работы изменённой программы

Важно запомнить:

Типовые задачи на поиск элемента в массиве:

·       найти элемент, сравнивая его с другими элементами массива;

·       найти элемент, равный определённому значению.

В первом случае: нужно выбрать один элемент массива, предположить его искомым и сравнить с оставшимися, меняя в процессе предполагаемый искомый элемент.

Во втором случае: достаточно перебирать элементы массива, пока они не закончатся или пока не найден искомый.