- Введение в тему
- Последовательный поиск в массиве
- научиться находить наибольшее значение среди элементов массива
- научиться находить значение массива, соответствующее заданному условию
- Что такое массив?
- Как описываются массивы?
- Как заполнить массив данными?
- Как вывести массив?
- Как вычислить сумму элементов массива?
Введение в тему
На занятиях и в качестве домашнего задания по разным учебным предметам и факультативным курсам довольно часто требуется найти определённую информацию, опираясь на которую, нужно выполнить задание: ответить на вопросы, написать сообщение/доклад/реферат и др.
Тема «Одномерные массивы. Последовательный поиск в массиве» относится к программированию, но её изучение способствует лучшему пониманию специфики построения алгоритмов поиска необходимой информации.
Последовательный поиск в массиве
Задания по поиску информации являются достаточно распространёнными задачами невычислительного направления.
Основные типы задач по поиску информации в массиве:
- Нахождение наибольшего/наименьшего значения элемента массива.
- Нахождение значения элемента массива, соответствующего заданному условию.
Как известно из предыдущих занятий по одномерным массивам целых чисел, во всех программах используются циклы, т. е. заполнение массива происходит в цикле.
В программировании при обосновании коррекции циклических алгоритмов применяется понятие «инвариант цикла».
Инвариант цикла — это логическое условие, которое зависит от переменных и изменяется в теле цикла. Инвариант цикла истинен перед началом выполнения цикла и после каждого прохождения через тело цикла.
Внесём изменения в уже известную задачу. Теперь вместо суммы будем находить наибольшее значение и сделаем задачу более массовой, сделав неизвестным количество элементов в массиве.
Задача 1
Дан массив А, состоящий из целых чисел. Написать программу для нахождения наибольшего значения элемента массива. Значения элементов массива пользователь самостоятельно вводит с клавиатуры.
Решение
1. Так как теперь неизвестно, сколько чисел может ввести пользователь, то можно написать, например, 10 000. Т. е. теперь массив А от 1 до 10 000. Данный способ является пригодным только для статических массивов.
Статический массив — это массив, размеры которого не задаются обычным пользователем, а определяются программистом на этапе разработки программы. Например, в разделе описания переменных.
10 000.
У статического массива имеется верхняя граница значений, которую пользователь не может превысить. Поэтому разработчик, определяя, какое максимальное количество значений может ввести пользователь, устанавливает это значение в программу.
У статических массивов есть три минуса, которых нет у динамических массивов (изучение динамических массивов не предусмотрено на базовом уровне, но если хорошо понимать, как они работают, то можно самостоятельно изучить динамические массивы):
- Верхняя граница, которая должна быть продумана на этапе разработки программы.
- Если пользователь не заполняет все выделенные программистом ячейки памяти, то память простаивает.
- Сами значения в статических массивах размещаются в ячейки памяти. Если представить, что данных не десятки, а сотни тысяч и более, то такой перенос значений по ячейкам увеличивает время выполнения операций с данными.
Добавим в раздел var переменную max для вывода наибольшего значения и переменную kol_vo для ввода пользователем количества элементов, а также увеличим размеренность массива до 10 000. Удалим переменную summa (рис. 1).
Рис. 1. Раздел описания переменных
2. В программном блоке напишем просьбу к пользователю ввести количество чисел и считаем введённое количество в переменную kol_vo (рис. 2)
Рис. 2. Начало программного блока
3. Далее напишем просьбу к пользователю ввести сами числа и в цикле реализуем считывание значений элементов массива. Наибольшему значению присвоим первое введённое пользователем число. Иногда за наибольшее число принимают самое маленькое число, которое может быть, но в данном случае гораздо удобнее присвоить наибольшему значению первое число, введённое пользователем (рис. 3).
Рис. 3. Программный блок (продолжение)
4. Теперь также в цикле for рассмотрим оставшиеся элементы (со второго по последний) и будем сравнивать их с max, который в начале равен первому введённому значению. Если введённое пользователем значение больше max, то max присваивается это значение. Таким образом перебираются все значения (рис. 4).
Рис. 4. Программный блок (продолжение)
5. Организуем вывод наибольшего значения (рис. 5)
Рис. 5. Вывод max
Готовая программа к данной задаче вместе с результатом работы представлена на рис. 6.
Рис. 6. Готовая программа к задаче 1 с примером её работы
Рассмотрим пример задачи, когда нужно найти значение элемента массива, соответствующего заданному условию.
Задача 2
Дан массив Massiv, состоящий из целых чисел. Вывести количество элементов массива, значения которых меньше 7.
Решение
1. Назовём программу min_7, создадим раздел var и опишем переменные. Для решения задачи потребуется массив под именем Massiv, а также i — для реализации цикла, kol_vo — для ввода пользователем количества чисел в массиве, chisla_min_7 — для подсчёта количества чисел меньше 7 (рис. 7).
Рис. 7. Раздел описания переменных
2. В разделе описания переменных попросим пользователя ввести количество чисел, а затем сами числа. В цикле реализуем считывание элементов массива и, ещё раз проходя по циклу, производим сравнение имеющихся значений с числом 7. Если введённое пользователем число меньше 7, то к количество чисел увеличиваем на 1. Затем выведем на экран полученное количество чисел меньше 7 (рис. 8).
Рис. 8. Программный блок
Готовая программа к данной задаче вместе с результатом работы представлена на рис. 9.
Рис. 9. Готовая программа к задаче 2 с примером её работы
Следует понимать, что писать программы даже для одной и той же задачи можно по-разному. Чтобы научиться «видеть» разные способы программной реализации, нужно хорошо понимать алгоритмы, сформулированные на естественном языке или с помощью блок-схем,
а также описанные выше программы.
Контрольные вопросы
- Что такое инвариант цикла?
- Что собой представляют статические массивы?
- Как найти количество чисел в массиве?
- Как изменится реализация задачи 1, если нужно будет найти наименьшее значение элемента массива?
- Как изменится реализация задачи 2, если нужно будет найти количество чисел кратных 3 и больше 15?
