Лекция Паскаль 10 – Массивы, Объявления одномерного массива, Индексация элементов


Тема: Массивы.

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

1. Понятие массива. Объявления одномерного массива. Индексация элементов.

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

Элементами массива могут быть данные различных типов, в том числе и структурированных. Каждый элемент одномерного массива однозначно определяется именем и индексом (для многомерных — индексами).

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

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

Общий вид описания линейного (одномерного) массива: Array [<тип индексов>] of <тип элементов>;

Чаще всего описание происходит следующим образом:

Array [<нижняя граница> .. <верхняя граница>] of <тип элементов>; Например:

Var

A: array [byte] of real; B: array [1..5] of integer;

C: array [0..9] of boolean;

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

На практике, как правило, элементы нумеруются, начиная с 1 или 0. Программисту — начинающему также лучше вести нумерацию, начиная с 1, так как при счете мы используем именно такую ​​последовательность значений. Однако, с точки зрения сохранения данных и некоторых алгоритмов, более целесообразно начинать нумерацию с 0.

Нумеровать элементы массива можно не только целыми числами. Произвольный порядковый тип данных (перечисляемые, интервальный, символьный, логический, а также произвольный, созданный на их основе) может выступать в роли индекса. При этом совокупный размер массива не может превышать 2 ГБ.

Таким образом, допустимые следующие описания массива: Var

D: array [char] of real;

E: array [ ‘a’ .. ‘z’] of integer; F: array [Boolean] of char;

Читать  КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ – Основы алгоритмизации и программирования

Примеры неправильных описаний массива: G: array [integer] of integer;

H: array [real] of byte;

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

a [1] = 5.4;

b [2] = — 2;

d [ ‘1’] = 1.568;

a [ ‘b’] = 7;

f [true] = ‘Y’;

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

Размещение массива A целых чисел в памяти:

A [1] A [2] A [3] A [4] A [5]
базовый адрес базовый адрес

+ 4 байта

базовый адрес

+ 8 байт

базовый адрес

+ 12 байт

базовый адрес

+ 16 байт

Такого типа массив, представляющий собой набор однотипных данных, называется простым или одномерным.

Всего в массив, приведен в таблице, в памяти будет отведено 20 байт — объявлен массив А целых чисел типа integer, каждому элементу (ячейке) массива будет выделено по 4 байта памяти. Все эти элементы соответствуют обычным переменным этого типа.

2. Ввод данных в массив. отражение его содержимого.

При изучении языка программирования Паскаль Вы практиковали ввод данных в массив, используя несложный цикл For:

var a: array [1..10] of integer; i: integer;

begin

for i: = 1 to 10 do begin

write ( ‘a [‘, i, ‘] =’); readln (a [i]);

end; end;

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

Задание 1. Разработать программу, которая реализует заполнения на форме массива целых чисел, содержащий 10 элементов (Massiv01).

Разработаем интерфейс программы. Введение элементов массива целесообразно выполнить с помощью компонентов Label, Edit, Button:

Программный код для реализации задачи — следующий:

Некоторые комментарии по строк программного кода:

// запись значения с поля

// отображение соответствующего индекса очередного элемента массива

// увеличение текущего индекса

// очистить поле ввода и перевести фокус

// если индекс станет равным 11, то завершить ввод

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

var a: array [1..10] of integer; i: integer;

begin

for i: = 1 to 10 do

write ( ‘a [‘, i, ‘] =’, a [i]);

end;

Задача 2. Дополнить предыдущий проект таким образом, чтобы по завершении ввода элементы массива выводились на форму (Massiv02).

Для организации вывода элементов массива на форме разместим компоненты Label, Button, Memo.

 

Элементы выводятся в поле Memo по нажатии на кнопку Вывести.

Фрагмент кода:

Практическое задание 1. Дан массив из N (N <= 50) целых чисел.Его нужно заполнить случайными числами в диапазоне от -10 до +10. Вывести сначала все элементы, размещенные на четных позициях, а потом — все элементы, размещенные на

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

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

1 элемент больше от последнего 1 элемент не больше последнего

 

Для реализации задачи форма содержит элементы Label (количество элементов N =), Edit (для числа), Button (Выполнить!), Memo (для вывода элементов массива).

В разделе Var опишем массив и две переменные типа целые числа:

В программе целесообразно использовать две процедуры — открытие формы и действие по нажатии на кнопку Выполнить.

В процедуре по открытию формы целесообразно прописать выполнения процедуры randomize — генератора случайных чисел:

В процедуре обработчика события «Нажать на кнопку Выполнить» собственно и реализовано решение задачи:

3. Определение итоговых показателей для числового массива.

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

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

Задача 3. Найти сумму всех элементов массива А, состоящий из 10 целых случайных чисел в диапазоне от 0 до 20 (Massiv04).

Форма содержит поле Memo, в котором при запуске программы на выполнение отражаются десять элементов массива, кнопку «Выполнить»  и текстовое поле

«Сумма элементов массива».

В разделе Var опишем массив и две переменные типа целые числа:

В программе целесообразно использовать две процедуры — открытие формы и действие по нажатии на кнопку Выполнить.

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

В процедуре обработчика события «Нажать на кнопку Выполнить» собственно и реализовано решение задачи:

Поиск произведения элементов массива выполняется аналогичным образом. Отличие заключается лишь в том, что начальное значение произведения должно быть равным 1.

Задача 4. Найти произведение всех элементов массива А, состоящий из 10 целых случайных чисел в диапазоне от 1 до 10 (Massiv05).

Программный код для решения этой задачи следующий:

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

Задача 5. Найти среднее арифметическое элементов массива А, состоящий из 10 целых случайных чисел в диапазоне от -10 до 10 (Massiv06).

Программный код для решения этой задачи следующий:

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

Задача 6. Найти количество четных элементов массива А, состоящий из 10 целых случайных чисел в диапазоне от -20 до 20 (Massiv07).

Программный код для решения этой задачи следующий:

4. Поиск данных в массиве.

Поиск — одна из действий, которая чаще всего встречается в задачах по программированию. Входными данными для реализованного алгоритма является последовательность элементов a [1], a [2], a [3], …, a [N] (в нашем случае это массив) и некоторый элемент х. Задача состоит в том, чтобы получить на выходе номер элемента массива, равного х, или выяснить, что такого элемента в последовательности нет.

Задача 7. Составить программу для реализации последовательного поиска элемента в массиве (Massiv08).

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

Вид формы проекта, который реализует последовательный поиск

если элемент изысканы Если элемент не изысканы

 

Программный код проекта:

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

Задача 8. Составить программу для реализации бинарного способа поиска элемента в массиве (Massiv09).

Решение. Количество операций можно существенно уменьшить с помощью бинарного (двоичного) поиска. Это классический алгоритм поиска элемента в отсортированном массиве. Суть алгоритма заключается в уменьшении (в 2 раза) на каждом шагу области для поиска.

Рассмотрим последовательность действий для данного вида поиска. Берем средний элемент — если он равен искомому, то поиск успешно завершается. Если средний элемент больше искомого, то искомый элемент находится в первой половине массива (если он есть в массиве). Если же средний элемент меньше искомого, то искомый элемент находится во второй половине массива. Таким образом, мы разбили массив на две части. Используем тот же алгоритм в выбранной части массива. Продолжаем действия до тех пор, пока не будет найдено искомый элемент или доказано, что он в массиве отсутствует.

если элемент изысканы Если элемент не изысканы

Программный код проекта:

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

В процедуре, описывает событие OnClick кнопки «Выполнить поиск» собственно и реализовано бинарный алгоритм поиска элемента:

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

5. Теоретические вопросы для самоконтроля.

1. Приведите примеры задач, которые могут быть решены с помощью одномерных массивов.

2. Дайте описание одномерного массива в общем виде и на конкретных примерах.

3. Какие типы данных могут быть использованы в качестве индексов массива? Приведите несколько примеров.

4. Какая конструкция используется для ввода массива?

5. Чем отличается последовательность действий при поиске суммы от произведения элементов массива?

6. Типы алгоритмов, реализующих поиск элемента в массиве, Вы знаете? Один из них, по Вашему мнению, более эффективен?

[Всего голосов: 3    Средний: 5/5]