Что такое индекс в одномерном массиве

0

Урок 14. Одномерные массивы. Работа с элементами

Сегодня мы с вами наконец-то начинаем новую тему — одномерные массивы .

Одномерные массивы. Определение.

Одномерный массив — это фиксированное количество элементов одного и того же типа, объединенных одним именем, где каждый элемент имеет свой номер. Обращение к элементам массива осуществляется с помощью указания имени массива и номеров элементов.

Между именем типа и именем переменной ставится знак «двоеточие». Array — служебное слово (в переводе с английского означает «массив», «набор»); [1..N] — в квадратных скобках указывается номер первого элемента, затем, после двух точек, номер последнего элемента массива; of — служебное слово (в переводе с английского «из»); integer — тип элементов массива.

Индексом могут быть не только натуральные числа: мы можем написать так: [0..10], [-29..45], [‘a’..’z’], [false..true] — то есть нам подходят любые символы и числа — главное соблюсти следующее условие: левая часть меньше правой. Для того чтобы определить, что меньше — восклицательный знак(‘!’) или точка(‘.’) используем таблицу ASCII и функции Ord() и Chr().

Как же производится ввод одномерного массива?

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

Как видите, ничего страшного в массивах нет. Массивы применяют в тех случаях, когда нельзя обойтись одной-двумя переменными (примеры таких задач мы рассматривали в решении задач из блока Series). В случаях, когда после ввода последовательности целиком пользователю необходимо обратиться к переменным в середине последовательности, в начале, поменять их значения местами, отсортировать.

Раз уж мы затронули тему задач из блока Series, давайте решим пару задачек оттуда с помощью массивов, а не тем увечным способом, которым нам приходилось пользоваться.

Одномерные массивы. Решение задач.

Series8. Дано целое число N и набор из N целых чисел. Вывести в том же порядке все четные числа из данного набора и количество K таких чисел.

Series28. Дано целое число N и набор из N вещественных чисел: A₁, A₂, …, A_N. Вывести следующие числа:

Исходное решение: Series28.

Более подробно про возведение числа в степень мы говорили в решении задачи for36.

Ну и напоследок давайте разберём веселенькую задачу на длинную арифметику.

Задача. Найти факториал числа.

Мы уже решали эту задачу здесь(for19).

Научимся вычислять факториал натурального числа N. Факториал числа — это произведение чисел 1*2*3*…*(N-1 )*N (обозначается как N!). Сложность задачи в том, что уже 8!=40320, а 13!=6227020800. Типы данных Integer, Longlnt применимы весьма в ограниченном диапазоне натуральных чисел. Для представления факториала договоримся использовать массив. Пример:

В массиве записано значение 11!=39916800. Каким образом? В А[0] фиксируется число занятых элементов массива, в А[1] — цифра единиц результата, в А[2] — цифра десятков результата, в А[3] — цифра сотен результата и т. д. Почему так, а не наоборот? Такая запись позволяет исключить сдвиг элементов массива при переносе значений в старший разряд. А сейчас наберите, как обычно, текст программы, выполните компиляцию и, выполните ее в пошаговом режиме, отслеживая изменение значений переменных при не очень большом значении N. Добейтесь полного понимания логики работы программы.

Для того чтобы выполнить программу в пошаговом режиме, нажмите «шаг без входа в подпрограмму» и перейдите в «локальные переменные».

Одномерный массив — это конечное упорядоченное множество элементов. За первым элементом идет второй, за вторым — третий и т. д. Индекс может быть чем угодно — и целым числом, и символом. Но чаще мы всё-таки будем пользоваться следующим диапазоном: [1.. N].

На сегодня все! Если у вас еще остались вопросы о том, как работает программа выше, оставляйте их в комментариях. И очень скоро мы начнем решать задачи на массивы из задачника М. Э. Абрамяна.

Что такое индекс в одномерном массиве

Массив – это составной объект, образованный из элементов (компонент) одного и того же типа. Такой тип данных применяется в программировании для обозначения объектов, аналогичных числовым последовательностям в математике, где сразу целая группа чисел обозначается одним именем (чаще всего буквой), а для обращения к каждому отдельному числу данной последовательности используются различные индексы (номера элементов).
В математике это может выглядеть, например, так:

Таким образом, в программировании массив – это последовательность однотипных элементов, имеющих общее имя, причем каждый элемент этой последовательности определяется порядковым номером (индексом) элемента.

Примеры массивов:

Х₁, Х₂, …, Х_n – одномерный массив, состоящий из n элементов;
А₀, А₁, А₂, …, А₁₀ – одномерный массив, состоящий из 11 элементов.

Особенности массива:

1. Структура массива всегда однородна. Массив может состоять из элементов типа integer , real или char , либо других однотипных элементов.
2. К любой его компоненте можно обращаться произвольным образом. Программа может сразу получить нужный ей элемент по его порядковому номеру (индексу).
3. Номер элемента массива называется индексом. Индекс – это значение порядкового типа, определенного, как тип индекса данного массива. Тип индекса определяет границы изменения значений индекса.

Рассмотрим массив Х 1 , Х 2 , …, Х n . Здесь:
Х – имя массива;
1, 2,…, n – индексы (порядковые номера) элементов;
Х 7 – седьмой элемент массива Х.

Описание одномерных массивов

Переменную типа массив можно описать сразу в разделе описания переменных Var:

Var Имя переменной: array [тип индекса (ов)] Of тип элементов;

Здесь:
Array – служебное слово (в переводе с английского означает «массив»);
Of – служебное слово (в переводе с английского означает «из»).

Пример
Var X: array [1..20] of real;
Массив Х – одномерный, состоящий из двадцати элементов вещественного типа. Элементы массива хранятся в памяти компьютера последовательно друг за другом.

Индексы элементов массива могут начинаться с любого целого числа, в том числе и отрицательного.

Пример
Var X: Array [-5..3] Of Boolean;
Массивы данного типа будут содержать 9 логических переменных, пронумерованных от -5 до 3.

Ввод и вывод одномерных массивов в Паскале

Ввод и вывод массивов осуществляется поэлементно.
Введем одномерный массив Х, состоящий из 30 элементов, то есть необходимо ввести некую последовательность элементов Х 1 , Х 2 , …, Х 30 .
Пусть i – индекс (порядковый номер) элемента в массиве Х. Тогда Хi – i-й элемент массива Х, где i = 1, 2, …, 30.

Для ввода массива можно использовать любой цикл.

Ввод массива с использованием цикла с параметром

Можно ввести с клавиатуры элементы следующим образом:
-7 _ 4 _ -2 _ 0 _ 12 _ -1 _ -5 _ 9 _ 11 _ -3 _ -5 _ … _15, то есть через пробел ввести в строчку и нажать клавишу Enter.
Можно было ввести элементы в столбец, отделяя элементы клавишей Enter, то есть каждый элемент с новой экранной строки:
-7 Enter
4 Enter
-2 Enter
…
…
…

Вывод одномерного массива осуществляется аналогично. В программе вместо операторов Read или Readln используются операторы Write или Writeln. Но просто заменить одни операторы на другие здесь недостаточно. Для того чтобы выводимые значения не сливались между собой, надо явным образом вставлять между ними разделитель – пробел или перевод строки.

Приведем два возможных способа вывода массива:

For i := 1 To n Do Write (X[i],’ ‘);

For i := 1 To n Do Writeln (x[i]).

Пример
Выведем одномерный массив Х 1 , Х 2 , …, Х n , состоящий из 30 элементов целого типа (30 единиц), используя цикл с параметром.

Вывод: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Массивы в программировании: описание и наполнение данными

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

Массивы, которые хранят в своем составе неупорядоченные сведения – это множества. С ними знаком каждый математик. Массивы одномерного типа – это реализация абстрактного типа данных. Носит название вектора. В отдельных языках программирования соответствующий элемент кода может носить название:

• ряд;
• таблица;
• матрица;
• вектор.

Далее предстоит разобраться с тем, что собой представляют массивы в программировании. Рассмотрим в качестве примеров несколько языков программирования. Упомянутые ранее элементы в них работают со своими особенностями, хоть и примерно одинаково. Предстоит разобраться с видами, а также ключевыми нюансами каждого типа «упорядоченного множества». Также нужно будет изучить принципы заполнения массива в том или ином случае.

Разновидности

Перед началом работы с соответствующим элементом разработки нужно выяснить, каким он может быть. Различают самые разные размерности массивов. Это – количество индексов, необходимое для однозначной (конкретизированной) адресации элемента в пределах заданного «упорядоченного множества». Здесь можно выделить следующие виды:

1. Одномерные. Индекс будет всего один.
2. Двумерные. «Адресов обращения» два.
3. Три и более. Встречаются на практике крайне редко.

Огромную роль играет форма (или структура). Она представлена сведениями о количестве размерностей и размере (протяженности) массива по каждой размерностей. Может выступать в виде самостоятельного одномерного массива.

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

Также есть гетерогенные массивы – хранящие в разных элементах информацию совершенно разных типов. В языках разработки принято выделять специфические массивные виды:

• ассоциативные;
• деревья отрезков;
• разреженные;
• параллельные;
• V-списки.

Одномерные массивы обладают нестрогим соответствием векторам, а двумерные – матрицам. Это – самые распространенные варианты. Именно с ними предстоит работать далее.

Индексы – общие понятия

Индекс меняется в зависимости от выбранного программистом языка разработки. Можно выделить три типа «упорядоченных множеств»:

• с отчетом с нуля;
• отсчет начинается с единички;
• отсчет от специфического значения, которое заранее задается разработчиком.

Первый вариант предусматривается преимущественно в низкоуровневых языках разработки, но и в ЯП высокого уровня тоже встречается. Пример – СИ-семейство. В некоторых языках разработки допускается определение диапазона индексов в виде произвольного диапазона значений любого типа данных, приводимого к целому. Это – набор перечислений, целых, а также символов. Логический тип данных тут тоже применяется. Такой вариант актуален для Модула-2, Ада и Паскаль.

Несколько слов о динамическом типе

Динамический массив – это «упорядоченное множество», размер которого умеет меняться по мере работы приложения. Обычные массивы носят название статистических или фиксированных

Динамические массивы реализовываются на уровне программирования, а также на уровне системных библиотек. Во втором случае он представляет собой объект стандартной библиотеки. Все манипуляции с соответствующим элементом будут проходить в пределах заданного «хранилища».

Если язык программирования поддерживает динамические массивы, в процессе создания исходного кода, в нем предусматриваются такие особенности и возможности:

1. Описание динамического массива. На уровне языка оно может быть представлено синтаксической конструкцией. В случае с библиотеками – библиотечным типом данных, значение которого устанавливается стандартным образом. При создании (описании) динамического «упорядоченного множества» нужно указать его начальный размер. Это требование не является обязательным.
2. Операции определения текущего размера динамического массива.
3. Изменение размеров заданного «упорядоченного множества».

Теперь можно рассмотреть процессы задания и заполнения массивов более подробно. Но сначала выясним, что является массивом одномерного характера.

Одномерный массив

Данный элемент программного кода встречается на практике достаточно часто. И заполнить его можно без особых затруднений. Обратите внимание на то, что у одномерных «упорядоченных множеств» обращение происходит по одному единственному индексу. Такой вариант носит название «линейного».

Одномерный массив – это конечное (или итоговое) количество однотипных элементов. Они объединяются друг с другом при помощи общего заданного имени. Каждый элемент имеет собственный порядковый номер. Обращение к ним осуществляется по имени, а также индексу (установленному порядковому номеру).

Линейным такой программный компонент называется из-за того, что в нем каждый элемент будет следовать друг за другом, напоминая линию или цепочку. «Упорядоченное множество» представляется при помощи простейшей таблицы. Она включает в себя несколько строчек:

• имеющиеся значения (их нужно предварительно задать);
• индексы элементов.

Начальный индекс зависит от выбранного языка программирования. В Pascal можно задавать его произвольно. Согласно действующим правилам разработки лучше начинать с единицы. Это упростит дальнейшую работу с рассматриваемым компонентом. Итоговый (конечный) индекс будет определяться в соответствии с имеющейся задачей. Численно он соответствует размеру заданного множества, которое отражает количество содержащихся в нем элементов.

В основном работать предстоит с числовыми массивами. Они включают в себя вещественные и целые значения. Пример – цепочка 1 2 3 4 5 6 7 8 9. Это – не только множество, но и массив.

Выше – наглядный пример соответствующего одномерного компонента.

Особенности в C++

Рассмотрение двумерного массива – более сложная задача. Если представить себе его в математической форме, получится своеобразная матрица. На практике встречается не так часто, как одномерные варианты, поэтому более подробно их изучать пока не будем.

«Упорядоченные множества» имеют немало типовых задач. В основном они все сводятся к:

• заполнению массива информацией;
• проведению тех или иных операций с заданным «множеством»;
• выводу непосредственного результата.

Обычно после постановки задачи становится очевидной часть решения. Далее будут рассмотрены типовые ситуации, которые помогут при создании приложений в C++ и других языках.

Организация

Здесь стоит запомнить следующие принципы:

1. Память под массив может выделяться несколькими способами – динамически и автоматически.
2. Автоматический подход применяется тогда, когда размер массива известен на этапе компиляции. Это значит, что соответствующий параметр задается в момент написания исходного кода.
3. Динамическое выделение памяти актуально для ситуаций, при которых используется «упорядоченное множество данных» с неизвестным «объемом».
4. Массивы могут быть глобальными (определенными за пределами функции), а также локальными (объявленные внутри блоков кода или функций).
5. Память для локального автоматического массива будет выделяться в стеке. Из-за этого его размер должен быть небольшим. В противном случае существует риск столкновения с перегрузкой и завершением работы приложения.
6. Глобальные автоматические массивы в плане вопросов переполнения стеков являются безопасными. Но такие элементы видны всему программному коду, расположенному после объявления массивов. Это иногда провоцирует прямо применение «упорядоченных множеств», игнорируя передачу в функции при помощи параметров.

А еще для массивов с динамическим выделением памяти актуально ее распределение через так называемые кучи. Это – память, которая выделяется операционной системой для использования конкретным программным обеспечением.

Инициализация массива происходит обычно в момент его создания. Вот общая форма описания одномерного соответствующего компонента:

тип имя_массива [размер];

Эту запись надо использовать в программном коде, чтобы задать массив в C++. Соответствующая форма записи актуальна почти для всех языков программирования.

Заполнение значениями

Провести заполнение массива можно несколькими способами. Соответствующий момент напрямую зависит от условий поставленной изначально задачи. Предусматриваются такие варианты:

• путем ввода с клавиатуры;
• через генерацию случайных чисел;
• по выставленным принципам, формулам или условиям.

В некоторых задачах поддерживается чтение данных из файла. Это достаточно сложная и редкая ситуация, которую изучать более подробно не будем.

Рассматривая наглядные примеры на разных языках программирования, будем использовать разнообразные массивы информации. В Pascal для наглядности возьмем множество, которое включает в себя 5 элементов:

Данный код будет применяться при попытках заполнить «упорядоченное множество» теми или иными элементами в описываемых ситуациях. Это – элементарный случай, помогающий более быстро и эффективно разобраться в изучаемой тематике.

Случайные числа

Первый вариант – это использование генератора случайных чисел. Такой подход позволяет заполнять «упорядоченные множества» элементами, которые не вводятся пользователем непосредственно с клавиатуры. Достаточно распространенная ситуация.

Так выглядит процесс на примере C++:

1. Функция rand() будет при каждом запуске приложения генерировать одну и ту же последовательность случайных чисел.
2. Чтобы избавиться от описанного выше нюанса, нужно «разогнать» функцию при помощи начального случайного значения. На помощь приходят time() и srand().
3. Заполнение «множества» элементами случайного характера нужно организовывать непосредственно внутри цикла.

Вот – пример, в котором используется глобальный автоматический массив. Он включает в себя 10 элементов типа of integer. Интервал, в котором определяются случайные значения – от -100 до 100 включительно. Особое внимание здесь необходимо уделить включению заголовочных файлов.

В случае с Pascal ситуация будет выглядеть в виде программного кода так:

Здесь происходит заполнение изначального «упорядоченного множества» из пяти элементов случайными значениями в диапазоне от 0 (включительно) до 10. Такой подход помогает удостовериться в правильности функционирования и работоспособности имеющегося программного кода.

Ввод с клавиатуры

Всего несколько строк в приложении – и «упорядоченное множество информации» будет заполнено случайными элементами. Это – наиболее распространенная ситуация. Но иногда требуется заполнить имеющееся «множество» иначе. А именно – путем ввода значений в massiv с клавиатуры.

Для C++ такая ситуация – более сложный случай. За основу возьмем предыдущим пример. В него нужно внедрить возможность указания значений элементов массива с клавиатуры. Для этого в начало кода требуется внести заголовочный файл #include <iosteram>. Вместо инициализации случайными значениями нужно записать что-то вроде такого кода:

Метод работает неплохо, но результат будет зависеть от выбранного компилятора. Иногда он оказывается непредсказуемым. Из-за этого в C++ рекомендуется пользоваться такой формой:

В случае с Pascal все намного проще. Тут нужно использовать «стандартные» переменные (int i) и операторы цикла for.

В программном коде ввод элементов массива с клавиатуры будет иметь такой вид. Здесь n – это количество элементов в определенном «упорядоченном множестве».

Правила

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

Тут предстоит заполнить массив квадратами натуральных чисел. Соответствующий пример актуален для большинства типовых задач. Если необходимо использование многомерного массива, лучше пользоваться оператором присваивания («=», пишется без кавычек). Особенно тогда, когда «множество» не слишком большое.

В JavaScript

JavaScript – это еще один популярный язык разработки. Он применяется преимущественно для веб-программирования и создания программного обеспечения для работы с Сетью. Тут тоже предстоит работать с «упорядоченными множествами».

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

• .push() – позволяет заполнить массив с конца, добавляется один элемент;
• .unshift() – добавление в самое начало;
• .splice() – используется для добавления одного или нескольких элементов, начиная с указанного.

Выше – фрагмент кода, который поможет лучше объяснить принцип работы соответствующих методов.

Вывод

Теперь понятно, чему равен результат описанных операций. Заполнить «упорядоченное множество» теми или иными данными обычно недостаточно для решения задачи. Результат необходимо вывести.

В C++ это делается так:

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

А это – код, который актуален для JavaScript:

Он помогает вывести содержимое в элемент массива с >

Типовой шаблон для Pascal

Тут и здесь можно увидеть несколько шаблонов для решения типовых задач на C++ и JavaScript соответственно, связанные с массивами данных. В случае с Pascal можно задействовать всего один программный код. Выглядит он следующим образом:

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

Как быстро научиться программировать

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

Быстрее освоить соответствующее направление помогут разнообразные видеоуроки и туториалы. Вот – наглядный пример того, как заполнить элементы «упорядоченного множества» значениями, введенными непосредственно с клавиатуры. Но такой подход отнимает много времени и сил. А еще не всегда удается найти материал, соответствующий обозначенной задаче.

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

1. Сжатые сроки обучения. Оно отнимает от нескольких месяцев до года.
2. Возможность быстро освоить инновационные IT-профессии и совершенно любые языки программирования. Есть предложения для опытных разработчиков и новичков. Можно выбрать всего одно направление или несколько одновременно.
3. Постоянное кураторство и богатую практику. В процессе специалисты помогут ученику сформировать первое портфолио.
4. Интересные домашние задания.
5. Обучающий процесс, полностью построенный в режиме «онлайн». Лекции и вебинары можно смотреть в любое время и с совершенно разных устройств. Это помогает совмещать обучение с работой, домом, детьми и семьей.
6. Грамотно составленные программы обучения. Они учитывают все последние изменения тех или иных языков разработки.
7. Наиболее полную подачу материала. В процессе учебы пользователю пояснят не только, что значит new int, но и более сложные моменты простыми словами.

В конце клиент получит электронный сертификат, подтверждающий полученные навыки и умения.

Хотите освоить современную IT-специальность? Огромный выбор курсов по востребованным IT-направлениям есть в Otus!

Урок 5. Массивы

Перечень вопросов, рассматриваемых в теме: массивы, описание массивов, заполнение массивов, типовые задачи обработки массивов.

Глоссарий по теме: массив, элемент массива, размерность массива, индекс элемента массива, сортировка.

Основная литература по теме урока:

Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 11 класса. — М.: БИНОМ. Лаборатория знаний, 2017

Дополнительная литература по теме урока:

— И. Г. Семакин, Т. Ю. Шеина, Л. В. Шестакова. Информатика и ИКТ. Профильный уровень: учебник для 11 класса. — М.: БИНОМ. Лаборатория знаний, 2012

— К. Ю. Поляков, Е. А. Еремин. Информатика. Углубленный уровень: учебник для 10 класса. В 2 ч. Ч. 2 — М.: БИНОМ. Лаборатория знаний, 2013

— Андреева Е. В. Программирование — это так просто, программирование — это так сложно. Современный учебник программирования. — М.: МЦНМО, 2015

— Молчанова С. И. Основы программирования. Турбо-Паскаль 7.0 для школьников и абитуриентов. — М.: «Аквариум»; ООО «Фирма «Издательство АСТ», 1999

Теоретический материал для самостоятельного изучения

Рассмотрим следующую задачу: ввести с клавиатуры 20 действительных чисел и вычислить их сумму, при этом каждое из чисел сохранить в памяти для последующей обработки.

Для решения этой достаточно простой задачи мы будем вынуждены ввести 20 имен переменных, что, естественно, очень неудобно. Но ведь чисел может быть гораздо больше, чем 20!

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

Массив — это поименованная совокупность однотипных элементов, упорядоченных по индексам, определяющим положение элемента в массиве.

Элемент массива — отдельная переменная, входящая в массив.

Индекс элемента массива — номер элемента в этом массиве.

Размерность массива — количество элементов, которое содержит массив.

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

Описание массивов

В языке Паскаль массивы описываются в блоке описания переменных следующим образом:

var <идентификатор>: array [<тип индекса>] of <тип компонентов>

— array и of — служебные слова, которые буквально можно перевести как «массив» и «из»;

— <тип индекса> — описание индексации (нумерации) элементов массива. В качестве типа индекса можно использовать любые порядковые типы;

— <тип компонентов> — тип величин, непосредственно составляющих массив.

Приведем несколько примеров описаний:

1. varday: array [1..365] of integer; — массив, состоящий из 365 целых чисел, которые пронумерованы от 1 до 365;
2. vartem: array [0..11] of real; — массив, состоящий из 12 вещественных, пронумерованных от 0 до 11;
3. var ocenka: array [–2..2] of char; — массив, состоящий из 5 символьных переменных с номерами от -2 до 2:
4. const n=10; var slovo: array [1..n] of string; — n строковых величин, пронумерованных от 1 до n;

Для того, чтобы обратиться к элементу массива, нужно записать имя массива и в квадратных скобках индекс нужного элемента, например, day[100].

Рассмотрим основные приемы работы с массивами.

Заполнение одномерного массива значениями

Задать элементам массива значения мы можем:

— вводя значения с клавиатуры;

— случайным образом из некоторого диапазона;

Но какой бы способ мы ни выбрали, нам обязательно нужно организовать цикл.

Для начала договоримся, что мы имеем дело с массивом из 10 натуральных чисел (хотя тип элементов в данном случае значения не имеет).

Вывод элементов массива на экран

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

Воспользуемся вторым и третьим способами, рассмотренными выше:

Теперь перейдем к задачам обработки массивов.

Вычисление суммы элементов массива

Алгоритм решения практически полностью совпадает с алгоритмом нахождения суммы некоторого количества чисел, который мы уже рассматривали на третьем уроке в этой теме.

Следующая группа задач очень часто встречается нам в реальной жизни. Это задача поиска в массиве. Например, поиск нужного слова в словаре, поиск времени отправления нужного поезда в расписании и т. д.

В программировании поиск — одна из наиболее часто встречающихся задач вычислительного характера.

В алгоритмах поиска существуют два возможных варианта окончания их работы: поиск может оказаться удачным — заданный элемент найден в массиве и определено его месторасположение, либо поиск может оказаться неудачным – необходимого элемента в данном объеме информации нет. Кроме того, искомый элемент может встретиться в массиве неоднократно.

Рассмотрим несколько типовых задач, которые уже знакомы вам из курса основной школы.

Поиск в массиве элемента, удовлетворяющего некоторому условию

Например, требуется найти в массиве элемент, значение которого равно значению переменной p, или сообщить, что такого элемента в массиве нет.

Мы построим алгоритм, идея которого следующая:

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

Можно заметить, что наш алгоритм решает еще одну часто встречающуюся задачу обработки массивов — подсчет количества элементов, удовлетворяющих некоторому условию.

Поиск максимального (минимального) элемента массива

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

Введем дополнительную переменную max, которой присвоим значение, равное значению элемента массива a[1]. Теперь будем сравнивать все элементы, начиная со 2-го, с max, и если найдем больший элемент, то присвоим его значение переменной max. Конечное значение этой переменной и будет значением наибольшего элемента массива.

Поиск максимального (минимального) среди всех элементов массива, удовлетворяющих некоторому условию

Фактически, эта задача является объединением двух предыдущих, но с одним «подвохом».

Допустим, нужно найти наибольшее среди всех четных чисел, входящих в массив произвольных натуральных чисел.

Мы знаем, что условие «четности» на языке Паскаль можно записать так: x mod 2=0. Значит, найти все четные элементы массива мы сможем. Но как среди них найти наибольший?

Прием, которым мы воспользовались в задаче 5, здесь может привести к ошибке. Например, на первом месте в массиве будет стоять НЕЧЕТНОЕ число, которое окажется больше всех четных. Здесь переменной max лучше присвоить начальное значение, заведомо меньшее всех элементов массива. Например, если наш массив составлен из натуральных чисел, то присвоить max значение -2. Если после окончания программы значение max останется таким же, это будет означать, что в массиве нет четных чисел. Если же они будут, max изменит значение.

Сдвиг элементов массива

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

Таким образом при удалении элемента из массива мы можем получить, например, такую ситуацию. Допустим, имеется массив:

Удалим из него элемент с индексом i=4, т. е. a[1]=a[1], a[2]=a[2], a[3]=a[3], a[4]=a[5], a[5]=a[6], a[6]=a[7]. А вот для последнего элемента a[7] новое значение взять неоткуда. Он сохранит свое значение. Получим:

Чтобы избежать такого дублирования последнего элемента обычно на его место ставят число 0.

Программа удаления элемента из массива на языке Паскаль может выглядеть следующим образом:

Сложнее обстоит дело со вставкой элемента внутрь массива. Как мы сказали, при вставке все элементы, расположенные справа от места вставки, сдвигаются вправо. Последнему же элементу сдвигаться некуда, и он пропадет. Чтобы этого не произошло, нужно увеличить размерность массива на 1. Но учесть это надо при описании массива. Второй важный момент заключается в том, что сдвиг значений мы будем производить справа налево до заявленной позиции вставки:

Реверс массива

Реверс массива — это перестановка его элементов в обратном порядке: первый элемент становится последним, а последний — первым.

Из примера видно, что местами меняются 1-й элемент с N-м, второй — с (N–1)-м и т. д. Замечаем, что сумма индексов элементов, участвующих в обмене, равна N+1, поэтому элемент с номером i должен меняться местами с (N+1–i)-м элементом.

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

Все вернулось в исходное состояние, потому что реверс выполнился дважды. Чтобы этого не произошло, нужно остановить процесс обмена на середине массива, т.е. на элементе с индексом (N div 2).

Сортировка массива

Сортировка — один из наиболее распространенных процессов обработки данных.

Под сортировкой массива понимают расстановку элементов массива в заданном порядке.

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

Цель сортировки — ускорить последующий поиск элементов, т. к. нужный элемент легче искать в упорядоченном массиве.

Существует много различных алгоритмов сортировки. Мы рассмотрим некоторые из них на примере сортировки массива целых чисел в порядке неубывания (a[i]<=a[i+1]).

Обменная сортировка методом «пузырька»

Свое название этот алгоритм получил из-за схожести с физическим явлением всплытия пузырька воздуха в воде. Точно также в массиве как бы «всплывают» наверх (к началу массива) меньшие элементы.

Сначала мы сравниваем последний и предпоследний элементы массива. Если они стоят неправильно (нижний элемент меньше верхнего), то меняем их местами. Далее сравниваем следующую пару элементов и т. д.

В итоге самый «легкий» элемент поднимается на самый верх.

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

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

Сортировка выбором

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

Рассмотренные алгоритмы сортировки являются достаточно простыми для понимания и запоминания, но на практике применяются редко. Дело в том, что они обладают квадратичной сложностью, т. е. в общем случае число сравнений и обменов сопоставимо с n 2 , где n — число элементов в массиве.

С примером более эффективного алгоритма сортировки — «быстрой сортировкой» — вы сможете познакомиться в дополнительном материале.