Типы данных. Структуры данных. Обработка массивов. Итеративные и рекурсивные алгоритмы обработки массивов. Многомерные массивы
Обсуждая билет № 5, мы уже говорили о типах данных, их роли в алгоритме, а также о том, что дает компьютеру “знание” типа конкретной величины. Мы также говорили, что существуют простые и сложные типы данных. Простые типы чаще всего используются для хранения рабочих величин, но могут быть также аргументами или результатами в несложных алгоритмах. Тем не менее для представления данных в реальных задачах возможностей простых данных обычно недостаточно. В самом деле, в типичном случае о человеке необходимо хранить фамилию, имя и отчество (текстовые данные), год рождения (число), пол и семейное положение (одно из значений, выбираемых из фиксированного набора), факты наличия или отсутствия определенных признаков, например, обладания недвижимостью (логические данные) и т.д. В результате для объединения совокупности всех относящихся к одному реальному объекту данных (компонентов) требуется возможность создания из них единой сложной структуры.
Примечание. Стоит отметить, что если к сложному набору данных, состоящему из отдельных компонентов (полей), добавить методы их обработки, то получится автономная конструкция еще более высокого уровня — объект (см. билет № 6).
Необходимость в обработке на компьютере сложных видов данных также непосредственно вытекает из цикличности большинства применяемых на практике алгоритмов. Свойство массовости (см. билет № 4) требует, чтобы алгоритм реализовывался для обработки максимально большого количества данных, а не для какого-то одного конкретного значения1. Следовательно, компьютер в подавляющем большинстве случаев производит многократную обработку множества данных по одному и тому же алгоритму (например, просматривает информацию о каждом человеке, отбирая по определенному признаку только тех, кто нужен согласно запросу).
В результате в языке программирования необходимо предусмотреть средства, которые позволяют компактно представлять программы такого рода обработки: описать действия над одним из типичных данных, а затем циклически многократно повторять эти действия. Нетрудно понять, что над формальной совокупностью простых данных (набором простых переменных с разными обозначениями) такую процедуру построить трудно — для этого лучше подойдет одна величина, определенным образом организованная (например, массив).
Как неявно следует из дальнейшей формулировки вопроса, в данном билете требуется рассказывать именно о сложных типах данных (в некоторых языках, подобных Си, подобные конструкции данных принято называть структурами).
Современные языки программирования позволяют создавать весьма разнообразные сложные структуры данных, причем для этого можно объединять как несколько простых, так и другие сложные данные. Самым распространенным сложным типом является массив, соединяющий в себе набор данных одного типа, например, массив из целых чисел или массив из логических величин. Кстати, конструкция “массив из массивов” также является вполне допустимой, о чем мы будем говорить несколько позже.
Для сложного типа в обязательном порядке требуется предварительно описать его состав. Это логически понятно, поскольку для конкретной структуры данных компоненты выбирает пользователь, и компьютер в принципе не в состоянии предугадать их набор; следовательно, никакое самое дружественное программное обеспечение не в состоянии автоматизировать данную операцию. В то же время сложные структуры данных требуют больших объемов памяти, так что и с этой точки зрения компьютеру требуется заранее знать состав компонентов структуры (для распределения памяти под каждый ее компонент).
Как уже отмечалось ранее, наиболее простой из сложных структур данных в памяти компьютера является массив. Поэтому мы будем рассматривать компьютерную обработку сложных данных именно на его примере.
Массив — это единая структура, компоненты которой имеют один и тот же тип. Обращение к отдельным элементам массива производится путем указания общего имени массива и определенной информации, характеризующей позицию требуемого элемента внутри массива. Последняя имеет смысл некоторой координаты (или, может быть, нескольких координат) и называется индексом (индексами). Отсюда видно, что массивы естественным образом делятся по количеству индексов на одномерные (с одним индексом), двумерные и, что допускается в большинстве языков, многомерные массивы (с боRльшим числом индексов). Для удобства изложения начнем рассмотрение с одномерных массивов.
Описание одномерного массива в различных языках программирования выглядит несколько по-разному, но всегда содержит информацию об устройстве индекса и типе элементов. Например:
m1: array [1..10] of real; — Паскаль
float m2[10]; — Си, Java и ряд других языков программирования
dim m3(9) as variant; — VBA (Visual Basic for Applications)
Во всех приведенных примерах в той или иной форме присутствует информация об индексах массива2 и типе его компонентов3. Видно, что, несмотря на различную форму записи, ее смысл во всех языках программирования примерно один и тот же, что легко объясняется общностью целей описаний массивов.
Подчеркнем, что хотя в одних языках (Basic, Си) индексы, определяющие положение элемента массива, всегда числовые, в других (Паскаль, Ада) допускаются и другие “счетные” типы (более точно их называть порядковыми). Хорошим примером порядковых данных может служить символьный тип CHAR, упорядоченный в соответствии с принятым в компьютере алфавитом (см. билет № 21).
Следует четко различать значения элементов массива и значения их индексов, обеспечивающие доступ к этим элементам. Можно провести весьма глубокую аналогию, сопоставив эту пару понятий с человеком и его почтовым адресом, который позволяет доставить необходимую информацию нужному лицу.
При решении задач на обработку массивов очень важно постоянно контролировать корректность значений индексов. Особенно актуальной эта проблема становится в том случае, если значения индекса задаются не в явном виде, а вычисляются тем или иным способом. Рассмотрим в качестве примера следующий фрагмент программы. Пусть в описании сказано, что массив Q состоит из элементов с номерами от 1 до 5. Пусть далее в некотором месте программы находится оператор присваивания Q[t+2] := 0. Тогда в случае t > 3 нулевое значение будет сохранено вне массива, точнее говоря, в то место памяти, где находился бы элемент под номером t+2, если бы он существовал. Так что в результате выполнения данного некорректного присвоения в лучшем случае будет “испорчено” значение какой-либо другой переменной, а в худшем — сама исполняемая программа. В любом случае найти такую ошибку крайне сложно: для этого потребуется большое внимание и глубокое понимание логики работы программы.
Примечание. Возможно, у некоторых читателей возник вопрос: неужели компьютер не в состоянии проконтролировать “попадание” значения индекса в “разрешенный” диапазон? Разумеется, в состоянии, вот только контроль этот увеличивает длину программы и замедляет ее работу. Именно поэтому во многих компиляторах контроль индексов является отключаемым, причем ради эффективности итоговой программы по умолчанию контроль как раз бывает выключен (именно так работает система программирования Turbo Pascal фирмы Borland).
Введение сложного типа “массив” позволяет компактно описывать решение широкого круга важных для практики задач. К типовым задачам обработки массива относятся:
· заполнение его элементов по определенному закону;
· нахождение некоторого характерного элемента (например, максимального или первого нулевого) и, может быть, его положения;
· поиск элементов, удовлетворяющих определенному условию (или подсчет их количества);
· определение некоторых характеристик массива (сумма, среднее значение, наличие упорядоченности или симметрии);
· сортировка массива;
· перенос данных из одного массива в другой, разделение массива на части, объединение массивов
— и некоторые другие. Подчеркнем, что к этим, казалось бы, весьма абстрактным упражнениям сводится огромное множество практических задач: от обслуживания каталогов дисков до обработки результатов соревнований.
В качестве примера рассмотрим задачу поиска в массиве положения максимального элемента, которое определяется числовым значением его индекса. Программа решения этой стандартной для массивов задачи на языке Паскаль может быть реализована следующим образом.
PROGRAM ind_max(INPUT, OUTPUT);
CONST n = 10;
m: ARRAY [1..n] OF INTEGER =
(8,10,9,4,7,2,5,6,3,1);
VAR k,im: INTEGER;
BEGIN im := 1;
FOR k := 2 TO n DO
IF m[k] > m[im] THEN im := k;
WRITELN('max=',im)
END.
Программа настолько проста и традиционна, что не требует особых комментариев. Отметим только, что для простоты отладки4 элементы массива не вводятся с клавиатуры, а инициализируются входящими в текст программы значениями с помощью механизма так называемых типизированных констант. Разумеется, вместо этого для ввода может быть написан и стандартный цикл FOR k := 1 TO n DO READLN(m[k]).
Существует большое количество способов организации обработки массивов. Помимо рассмотренной выше традиционной реализации, можно дополнительно выделить итерационный и рекурсивный методы. Опишем подробнее названные технологии обработки массивов на примере классической задачи сортировки массива.
Примечание. В том, что такой сложности задание соответствует уровню проведения выпускного экзамена, свидетельствуют задачи под номером 3, предлагаемые в качестве образцов в билетах
№ 12 базового и № 17 профильного уровня (см. [1] или [2]).
Пример итеративной обработки массива
Рассмотрим итерационный способ сортировки элементов одномерного числового массива в порядке возрастания, суть которого заключается в следующем. Просматривая массив, будем менять местами его соседние элементы в тех случаях, когда они нарушают требуемый порядок, иными словами, больший элемент оказывается в положении с меньшим индексом. Очевидно, что каждая такая перестановка “соседей” с позиций сортировки улучшает ситуацию в массиве, но одного “прохода вдоль массива” скорее всего будет недостаточно. Максимальное число просмотров равняется количеству элементов массива без единицы, что достигается при наиболее неудачной начальной расстановке (когда самое маленькое число стоит последним). Тем не менее вполне возможны ситуации, когда требуемый порядок по указанному алгоритму удастся получить за меньшее число проходов; в частности, в предельном случае, когда массив уже упорядочен, в этом можно убедиться единичным просмотром.
Каждый просмотр массива, приближающий к решению поставленной задачи (причем результат обработки всегда служит начальным состоянием для нового просмотра), в компьютерной литературе называют итерацией. В словаре [3], например, дается такое определение данного термина: итерация — это “повторение пошагового процесса, когда результат предыдущего шага (шагов) используется для получения результата следующего шага”.
Вообще говоря, любой цикл обработки массивов есть итерация. Правда, как правило, итерационными алгоритмами чаще всего называют такие, в которых количество повторений заранее неизвестно. Наш алгоритм сортировки является именно таким.
Механизм сортировки описанным методом настолько широко известен, что здесь мы приведем только возможное решение на Паскале и совсем краткие пояснения к нему.
PROGRAM sort_iter(INPUT, OUTPUT);
CONST n = 10;
m:ARRAY [1..n] OF INTEGER =
(10,9,8,7,6,5,4,3,2,1);
VAR i,p: INTEGER; c: BOOLEAN;
BEGIN REPEAT c := FALSE;
FOR i := 1 TO n - 1 DO
IF m[i] > m[i + 1] THEN
BEGIN p := m[i]; m[i] := m[i + 1];
m[i + 1] := p;
c := TRUE
END;
FOR i := 1 TO n DO
WRITE(m[i],' '); WRITELN;
UNTIL NOT c;
END.
В программе в виде типизированной константы задан массив, который с точки зрения сортировки по возрастанию представляет наибольшую трудность. Итерационный процесс сортировки регулируется переменной c, которая имеет смысл наличия произведенных во время итерации перестановок: когда c после выполнения очередной итерации ложно, перестановок не было и сортировку можно прекратить. Первый из циклов FOR обеспечивает проход по массиву и обмен “неправильно стоящих” соседних элементов местами, а второй — служит для контрольного вывода на экран результатов каждой итерации сортировки.
Заметим, что в билете № 5 в связи с рассмотрением физической задачи о расчете распределения температуры в стержне также был подробно описан пример итерационного алгоритма обработки одномерного массива.
Примеры рекурсивной обработки массива
Рекурсия — это способ решения задачи, при котором производится последовательное ее сведение к аналогичной, но более простой. К рекурсии в принципе можно свести любой циклический алгоритм, но не наоборот: известным примером может служить алгоритм закраски на экране произвольной области, который элементарно реализуется рекурсивным путем, зато решение этой задачи в виде циклов весьма затруднительно.
Таким образом, любая задача по обработке массива может быть решена с помощью рекурсии. Мы возьмем в качестве примера ту же самую задачу сортировки массива, которая рассматривалась выше для итерационного метода. Попутно окажется, что нам потребуется написать нахождение максимума, что также можно сделать рекурсивно5. Следовательно, в итоге у нас будет сразу два примера рекурсивных алгоритмов.
Рассмотрим возможную реализацию программы.
PROGRAM sort_rekurs(INPUT, OUTPUT);
CONST n = 10;
m: ARRAY [1..n] OF INTEGER =
(10,9,8,7,6,5,4,3,2,1);
FUNCTION ind_max(k: INTEGER): INTEGER;
VAR w: INTEGER;
BEGIN IF k > 1 THEN BEGIN w := ind_max(k - 1);
IF m[k] < m[w] THEN ind_max := w
ELSE ind_max := k
END
ELSE ind_max := 1
END;
PROCEDURE sort2(p: INTEGER);
VAR im,c: INTEGER;
BEGIN im := ind_max(p);
c := m[im]; m[im] := m[p]; m[p] := c;
FOR c := 1 TO n DO WRITE(m[c],' '); WRITELN;
IF p > 2 THEN sort2(p - 1)
END;
BEGIN sort2(n)
END.
Описание начнем с рассмотрения рекурсивной функции ind_max для нахождения индекса максимального элемента. Ее рекурсивная логика может быть сформулирована следующим образом. Решение задачи для массива из n элементов весьма трудоемко, поэтому его постепенно сводим к более простому: для n – 1, n – 2
и т.д. элементов (см. вызов ind_max(k-1), который и является рекурсивным вызовом функцией самой себя). Так поступаем до тех пор, пока ответ не станет тривиальным: в массиве из одного элемента индекс максимума равен индексу этого единственного элемента (в нашем случае 1). Далее производится “обратный ход” — зная текущее значение ind_max, соответствующее ему значение максимума сравниваем с текущим элементом массива, после чего индекс наибольшего из сравниваемых элементов запоминаем. Таким образом, отрабатывается последовательная цепочка рекурсивных вызовов и без всякого цикла организуется полный перебор всех элементов массива.
Примечание. Понимание механизма вызова процедур6 делает возможность реализации их “самовызова” абсолютно очевидной; даже просто зная о факте разрешения вызова из одной процедуры другой, можно предсказать существование рекурсивности. Главная же проблема рекурсии заключается в том, чтобы организованный рассматриваемым способом процесс каким-то образом завершался.
Теперь, рассматривая функцию ind_max как единое целое и не обращая внимания на ее внутреннюю логику, обсудим второй рекурсивный алгоритм — сортировку массива, описанную в рекурсивной процедуре sort2. Ее логика работы такова. В массиве размерности n находится максимальный элемент, и он меняется местами с последним. В результате самый последний элемент массива займет свое окончательное место и останется рассортировать массив уже меньшего размера, т.е. n – 1. Аналогичным образом задача последовательно решается для все меньшего и меньшего массива, пока не останется массив из одного элемента, в котором, естественно, сортировка уже не требуется: условие p > 2 предотвращает вызов sort2(1) и процесс рекурсии благополучно завершается.
Примечание. Имеющийся в sort2 цикл вывода массива на экран играет вспомогательную роль. Читатели при желании могут без труда самостоятельно оформить его в виде рекурсивной процедуры (печатаем первый элемент, а затем вызываем процедуру вывода оставшегося массива!), реализовав тем самым чисто рекурсивную программу без единого цикла.
Основная программа состоит из единственной строки sort2(n), которая запускает процесс сортировки, начиная с полного массива.
Примечание для учителей. Вполне возможно, что приведенное решение задачи для некоторых школ покажется слишком сложным. В этом случае вполне можно ограничиться рекурсивным решением ее части — нахождением положения максимума в массиве. Вообще сам факт наличия вопроса о рекурсии7 в тексте официальных “министерских” билетов для выпускных экзаменов в пору, когда слово “программирование” для многих методистов стало едва ли не ругательным, весьма наглядно демонстрирует тот идейный разброд, который внесла в содержание курса информатики энергичная борьба за наполнение школьного курса прикладными офисными технологиями!
Все обсуждавшиеся выше примеры рассматривали одномерные массивы данных. Они являются наиболее простыми и, кроме того, естественным образом согласуются с принципами организации памяти компьютера: согласно классическим идеям фоннеймановской архитектуры, память — это линейный массив пронумерованных ячеек. Следовательно, остается лишь получить формулу пересчета значений индексов в адреса ОЗУ и с элементами такого массива можно легко работать.
В математике, физике и некоторых других науках тем не менее широко используются и многомерные массивы. Поэтому такие структуры не могли не появиться в языках программирования. Фактически есть два способа определения многомерных массивов: непосредственный и создание сложной структуры. Мы ограничимся обсуждением двумерных массивов; обобщение для большей размерности делается аналогично. На языке Паскаль, например, эти два способа описания массивов выглядят так:
m1: ARRAY [1..3, 1..5] OF REAL;
m2: ARRAY [1..3] OF ARRAY [1..5] OF REAL;
Примечание. Обращение к элементам массивов m1 и m2 отличаются: они записываются как m1[i,j] и m2[i][j] соответственно.
В некоторых простых языках программирования типа Basic используется только традиционная математическая (“матричная”) форма представления массивов, а в языках с более развитыми средствами создания данных, в частности Паскале, допустимы обе формы.
Подчеркнем, что если в языке программирования для индексов допустимы не только целочисленные типы (в Паскале в том числе), то индексы многомерных массивов не обязательно имеют одинаковый тип: например, один индекс может быть целочисленным, а другой являться символом.
С математической точки зрения для увеличения размерности массива достаточно формально приписать еще один индекс. Однако для реализации такой структуры в памяти компьютера потребуется как-то приспособить многомерную структуру данных к хранению в одномерной памяти. “За исключением языка Fortran, все языки хранят двумерные массивы как последовательности строк… Такое размещение вполне естественно, поскольку сохраняет идентичность двумерного массива и массива массивов”. [4] Приведенный рисунок поясняет идею формирования двумерного массива данных в “линейном” ОЗУ компьютера.
Учитывая, что все элементы массива однородны (имеют один и тот же тип и, следовательно, занимают одинаковое место в памяти), получить формулу пересчета индексов в требуемый адрес ОЗУ является несложной задачей. И хотя школьных знаний для этого вполне достаточно, мы не будем сейчас этим заниматься. Заметим лишь, что в 32-разрядных процессорах Intel специально предусмотрены аппаратные методы адресации, в которые заложены такие формулы для данных стандартной длины (1, 2, 4 и даже 8 байт), что существенно облегчает для программиста (или для компилятора) доступ к элементам массивов. Заинтересовавшиеся читатели могут познакомиться с формулами для масштабированной базово-индексной адресации (одномерные массивы) и для аналогичного метода со смещением (двумерные), например, по книге [5].
Литература
1. Примеры задач к билетам. Информатика, 2006, № 6, с. 3–16.
2. Примеры задач к билетам. Информатика и образование, 2006, № 3, с. 24–30.
3. Фридланд А.Я. Информатика и компьютерные технологии: Основные термины: Толковый словарь / А.Я. Фридланд, Л.С. Ханамирова, И.А. Фридланд. М.: ООО “Издательство Астрель”: ООО “Издательство АСТ”, 2003, 272 с.
4. Бен-Ари М. Языки программирования. Практический сравнительный анализ. М.: Мир, 2000, 366 с.
5. Гук М. Процессоры Intel: от 8086 до Pentium II. СПб.: Питер, 1997, 224 с.
Изображение на бумажном носителе состоит из нескольких частей. Отсканировать части изображения и объединить их в одно растровое изображение. Отретушировать получившееся изображение и сохранить его в файле.
Решение данной задачи (после сканирования частей изображения) может быть выполнено в любом растровом графическом редакторе (в частности, в редакторе Paint). Для получения качественного итогового изображения рекомендуется воспользоваться редактором Adobe Photoshop.
Не будем здесь приводить детального описания решения задачи.