- Введение в тему
- Последовательный поиск в массиве
- научиться находить наибольшее значение среди элементов массива
- научиться находить значение массива, соответствующее заданному условию
- Что такое массив?
- Как описываются массивы?
- Как заполнить массив данными?
- Как вывести массив?
- Как вычислить сумму элементов массива?
Введение в тему
На занятиях и в качестве домашнего задания по разным учебным предметам и факультативным курсам довольно часто требуется найти определённую информацию, опираясь на которую, нужно выполнить задание: ответить на вопросы, написать сообщение/доклад/реферат и др.
Тема «Одномерные массивы. Последовательный поиск в массиве» относится к программированию, но её изучение способствует лучшему пониманию специфики построения алгоритмов поиска необходимой информации.
Последовательный поиск в массиве
Задания по поиску информации являются достаточно распространёнными задачами невычислительного направления.
Основные типы задач по поиску информации в массиве:
- Нахождение наибольшего/наименьшего значения элемента массива.
- Нахождение значения элемента массива, соответствующего заданному условию.
Как известно из предыдущих занятий по одномерным массивам целых чисел, во всех программах используются циклы, т. е. заполнение массива происходит в цикле.
В программировании при обосновании коррекции циклических алгоритмов применяется понятие «инвариант цикла».
Инвариант цикла — это логическое условие, которое зависит от переменных и изменяется в теле цикла. Инвариант цикла истинен перед началом выполнения цикла и после каждого прохождения через тело цикла.
Внесём изменения в уже известную задачу. Теперь вместо суммы будем находить наибольшее значение и сделаем задачу более массовой, сделав неизвестным количество элементов в массиве.
Задача 1
Дан массив А, состоящий из целых чисел. Написать программу для нахождения наибольшего значения элемента массива. Значения элементов массива пользователь самостоятельно вводит с клавиатуры.
Решение
1. Так как теперь неизвестно, сколько чисел может ввести пользователь, то можно написать, например, 10 000. Т. е. теперь массив А от 1 до 10 000. Данный способ является пригодным только для статических массивов.
Статический массив — это массив, размеры которого не задаются обычным пользователем, а определяются программистом на этапе разработки программы. Например, в разделе описания переменных.
10 000.
У статического массива имеется верхняя граница значений, которую пользователь не может превысить. Поэтому разработчик, определяя, какое максимальное количество значений может ввести пользователь, устанавливает это значение в программу.
У статических массивов есть три минуса, которых нет у динамических массивов (изучение динамических массивов не предусмотрено на базовом уровне, но если хорошо понимать, как они работают, то можно самостоятельно изучить динамические массивы):
- Верхняя граница, которая должна быть продумана на этапе разработки программы.
- Если пользователь не заполняет все выделенные программистом ячейки памяти, то память простаивает.
- Сами значения в статических массивах размещаются в ячейки памяти. Если представить, что данных не десятки, а сотни тысяч и более, то такой перенос значений по ячейкам увеличивает время выполнения операций с данными.
Добавим в раздел var переменную max для вывода наибольшего значения и переменную kol_vo для ввода пользователем количества элементов, а также увеличим размеренность массива до 10 000. Удалим переменную summa (рис. 1).
![](https://onlineschool-1.hb.bizmrg.com/VjAiuIOJ6wFi_%D1%80%D0%B8%D1%81%201.png)
2. В программном блоке напишем просьбу к пользователю ввести количество чисел и считаем введённое количество в переменную kol_vo (рис. 2)
![](https://onlineschool-1.hb.bizmrg.com/mRVWinYxkCJ6_%D1%80%D0%B8%D1%81%202.png)
3. Далее напишем просьбу к пользователю ввести сами числа и в цикле реализуем считывание значений элементов массива. Наибольшему значению присвоим первое введённое пользователем число. Иногда за наибольшее число принимают самое маленькое число, которое может быть, но в данном случае гораздо удобнее присвоить наибольшему значению первое число, введённое пользователем (рис. 3).
![](https://onlineschool-1.hb.bizmrg.com/7ahSVn2YTsW5_%D1%80%D0%B8%D1%81%203.png)
4. Теперь также в цикле for рассмотрим оставшиеся элементы (со второго по последний) и будем сравнивать их с max, который в начале равен первому введённому значению. Если введённое пользователем значение больше max, то max присваивается это значение. Таким образом перебираются все значения (рис. 4).
![](https://onlineschool-1.hb.bizmrg.com/Hsu383TNmman_%D1%80%D0%B8%D1%81%204.png)
5. Организуем вывод наибольшего значения (рис. 5)
![](https://onlineschool-1.hb.bizmrg.com/aIgixpBTq8lA_5.png)
Готовая программа к данной задаче вместе с результатом работы представлена на рис. 6.
![](https://onlineschool-1.hb.bizmrg.com/vgWeazqh1IaV_%D1%80%D0%B8%D1%81%206.png)
Рассмотрим пример задачи, когда нужно найти значение элемента массива, соответствующего заданному условию.
Задача 2
Дан массив Massiv, состоящий из целых чисел. Вывести количество элементов массива, значения которых меньше 7.
Решение
1. Назовём программу min_7, создадим раздел var и опишем переменные. Для решения задачи потребуется массив под именем Massiv, а также i — для реализации цикла, kol_vo — для ввода пользователем количества чисел в массиве, chisla_min_7 — для подсчёта количества чисел меньше 7 (рис. 7).
![](https://onlineschool-1.hb.bizmrg.com/OoaFZIqKWvos_%D1%80%D0%B8%D1%81%207.png)
2. В разделе описания переменных попросим пользователя ввести количество чисел, а затем сами числа. В цикле реализуем считывание элементов массива и, ещё раз проходя по циклу, производим сравнение имеющихся значений с числом 7. Если введённое пользователем число меньше 7, то к количество чисел увеличиваем на 1. Затем выведем на экран полученное количество чисел меньше 7 (рис. 8).
![](https://onlineschool-1.hb.bizmrg.com/mm0bHixIjOLY_%D1%80%D0%B8%D1%81%208.png)
Готовая программа к данной задаче вместе с результатом работы представлена на рис. 9.
![](https://onlineschool-1.hb.bizmrg.com/xu5iF6Db8UZN_%D1%80%D0%B8%D1%81%209.png)
Следует понимать, что писать программы даже для одной и той же задачи можно по-разному. Чтобы научиться «видеть» разные способы программной реализации, нужно хорошо понимать алгоритмы, сформулированные на естественном языке или с помощью блок-схем,
а также описанные выше программы.
Контрольные вопросы
- Что такое инвариант цикла?
- Что собой представляют статические массивы?
- Как найти количество чисел в массиве?
- Как изменится реализация задачи 1, если нужно будет найти наименьшее значение элемента массива?
- Как изменится реализация задачи 2, если нужно будет найти количество чисел кратных 3 и больше 15?