Типы данных. Структуры данных. Обработка массивов. Итеративные и рекурсивные алгоритмы обработки массивов. Многомерные массивы

Билет № 7

Задание на подсчет полного набора символов (мощности алфавита), используемого при кодировании информации

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

Решение. При условии, что не обязательно поднимать флаг на каждом из флагштоков, для каждого флагштока есть 4 возможности: нет флага, желтый флаг, зеленый флаг, красный флаг. Тогда общее количество комбинаций получается следующим:
4 · 4 · 4 · 4 · 4 = 1024.

Варианты заданий

В качестве задач в этом разделе можно предлагать любые простейшие задачи из комбинаторики.

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

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

3. Сколько можно составить пятизначных телефонных номеров из цифр от 0 до 7?

4. На полке стоит 5 напитков. Сколько разных коктейлей из них можно составить?

5. Номер машины состоит из 3 цифр. Сколько неправильных вариантов можно получить, угадывая номер?

Обсуждая билет № 5, мы уже говорили о типах данных, их роли в алгоритме, а также о том, что дает компьютеру “знание” типа конкретной величины. Мы также говорили, что существуют простые и сложные типы данных. Простые типы чаще всего используются для хранения рабочих величин, но могут быть также аргументами или результатами в несложных алгоритмах. Тем не менее для представления данных в реальных задачах возможностей простых данных обычно недостаточно. В самом деле, в типичном случае о человеке необходимо хранить фамилию, имя и отчество (текстовые данные), год рождения (число), пол и семейное положение (одно из значений, выбираемых из фиксированного набора), факты наличия или отсутствия определенных признаков, например, обладания недвижимостью (логические данные) и т.д. В результате для объединения совокупности всех относящихся к одному реальному объекту данных (компонентов) требуется возможность создания из них единой сложной структуры.

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

Необходимость в обработке на компьютере сложных видов данных также непосредственно вытекает из цикличности большинства применяемых на практике алгоритмов. Свойство массовости (см. билет № 4) требует, чтобы алгоритм реализовывался для обработки максимально большого количества данных, а не для какого-то одного конкретного значения¹. Следовательно, компьютер в подавляющем большинстве случаев производит многократную обработку множества данных по одному и тому же алгоритму (например, просматривает информацию о каждом человеке, отбирая по определенному признаку только тех, кто нужен согласно запросу).
В результате в языке программирования необходимо предусмотреть средства, которые позволяют компактно представлять программы такого рода обработки: описать действия над одним из типичных данных, а затем циклически многократно повторять эти действия. Нетрудно понять, что над формальной совокупностью простых данных (набором простых переменных с разными обозначениями) такую процедуру построить трудно — для этого лучше подойдет одна величина, определенным образом организованная (например, массив).

Как неявно следует из дальнейшей формулировки вопроса, в данном билете требуется рассказывать именно о сложных типах данных (в некоторых языках, подобных Си, подобные конструкции данных принято называть структурами).

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

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

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

Массив — это единая структура, компоненты которой имеют один и тот же тип. Обращение к отдельным элементам массива производится путем указания общего имени массива и определенной информации, характеризующей позицию требуемого элемента внутри массива. Последняя имеет смысл некоторой координаты (или, может быть, нескольких координат) и называется индексом (индексами). Отсюда видно, что массивы естественным образом делятся по количеству индексов на одномерные (с одним индексом), двумерные и, что допускается в большинстве языков, многомерные массивы (с бо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]).

Дата добавления: 2015-04-23