Pascal. Поиск в массиве.

Записывать данные в массива можно и без помощи readln, достаточно простой команды read. Приведём простой пример где считываем данные из массива и выводим:

Это было простое повторение. А теперь давайте попробуем написать программу, которая ищет в массиве число k, и если оно есть, то выводит yes или no:

Эту программу все всегда пишут с первого раза именно в таком виде.


Какие тут могут быть ошибки?

Ошибки довольно таки простые:

Например переменная q и так может быть равна 1, так как в разных средах Ваша программа будет воспринимать всё по разному. Тогда онулируем переменную в самом начале:

И видно что программа будет работать очень долго, если у нас будет массив из миллиарда элементов, так как наш цикл сначала проверит весь массив и только потом выдаст результат, что нам не нужно. Тогда ускорить программу нам поможет замена цикла на цикл с условием — while:

Теперь программа стала работать быстрее, так как после нахождения нужного нам числа, цикл остановится, но эта программа ещё далека от совершенства. Теперь давайте попробуем вида-изменить цикл while, и убрать переменную q:

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

То есть если у нас в программе строгие проверки с количеством элементов в массиве, то ошибка будет видна нам сразу, а так мы её и не заметим, то есть цикл может быть переполненным — значение i станет равно n+1, что нам не нужно, тогда достаточно просто поменять условия местами, и как известно в pascal — если одно условие не сработает, то и другое проверятся не будет:

Мы можем ещё упростить верхнюю часть:

Мы каждый раз проверяем в условии цикла — конец ли массива, что нам вообще и не нужно, если представить что у нас цикл с миллионом элементов, то каждый раз проверять конец ли массива нет смысла, для облегчения этой задачи используется Барьерный элемент. Что он из себя представляет:

Это самый последний элемент массива, добавленный вручную, который имеет искомое значение, то есть мы добавим искомое значение в конец массива, и при проверки условия будет проверять именно это — имеет ли переменная i значение n+1:

Мы добавили одну ячейку памяти и при этом ускорили программу вдвое.

Теперь перейдём к следующему:

Второй максимум.

То есть мы будем искать в массиве второй максимум, второй максимум — это число, которое меньше максимума, но больше других чисел.

Сначала напишем программу, которая просто находит максимальное число в массиве:

Как видим — максимум у нас равен первому элементу, который мы будем сравнивать со всеми другими элементами.

До этого мы представляли себе — если у нас много чисел, то всех их нужно загонять в массив, но это не так — представьте себе что в Вашей программе нельзя использовать массивы, то как сделаете Вы?

Самое простое решение — это использование одной переменной для хранения всех значений:

Теперь перейдём к решению задачи со вторым максимумом.

Представим что изначально переменные max и max2 равны минус бесконечности.

Теперь изменим код предыдущей программы именно так, что бы он искал max2 и не было ни каких ошибок:

В этой программе мы всё учли, даже то, что max может изначально иметь максимальное значение.

Представьте себе задачу подсчитать сколько максимумов в массиве, то как бы Вы реализовали её?

Мы предлагаем ввести в программу счётчик, который увеличивался на 1 при новом максимуме или числу равному максимуму. Увеличивать мы будем не по старинке — i:=i+1, а при помощи функции increment, сокращённо inc, и в скобках уже пишем имя переменной, эта функция увеличивает переменную на единицу. Также есть и функция, которая уменьшает значение на единицу — decrement, сокращённо dec.

Теперь давайте напишем нашу программу:


Похожие записи:

Оставить комментарий

Ваш e-mail не будет опубликован. Обязательные поля отмечены *