Переменные с индексами. Массивы
Как и было обещано, вернемся к задаче 6.5 о призывниках. Она опять нам потребуется, правда, в немного усложненном варианте.
Задание 8.1.
Постановка задачи
В военкомат на медкомиссию вызвали N призывников. Известен рост каждого призывника ri. Написать программу, вычисляющую средний рост призывников. Распечатать номера тех призывников, чей рост оказался ниже среднего (для отправки в танковые войска).
Выбор метода решения и проектирование
На первый взгляд задача во многом повторяет задание 6.5. Однако при ближайшем рассмотрении оказывается, что использовать для ее решения алгоритм, предложенный выше, не представляется возможным. Решение, которое мы нашли в п.6, при всех его достоинствах обладает одним серьезным недостатком: по окончании работы алгоритма существенная часть исходных данных, а именно значения роста всех призывников (кроме последнего) оказываются утерянными и сравнивать со средним ростом нечего.
Очевидны два решения создавшейся проблемы:
1) После того как программа рассчитала средний рост – применить унтер-офицерский подход, заставить пользователя «не тянуть резину в долгий ящик» и вторично ввести исходные данные:
program Feldfebel;
var
N,I:Integer;
S,H,R:Real;
begin
Write(‘Количество призывников? ’);
ReadLn(N);
S:=0;
for I:=1 to N do
begin
Write(‘Введите рост ‘,I,’-го призывника: ’);
ReadLn(R);
S:=S+R;
end;
H:=S/N;
WriteLn(‘Средний рост ’,H);
for I:=1 to N do
begin
Write(’Введите рост ‘,I,’-го призывника: ’);
ReadLn(R);
if R<H then
WriteLn(’номер ’,I,’– в танковые войска’);
end;
end.
Программа получилась вполне работоспособной и выдержанной в духе известных рекомендаций одного старшины: «… грузить будем люминий, а особо грамотные будут грузить чугуний». Но, к сожалению, «шила в мешке не утаишь: оно все равно всплывет наружу» и рекомендации бравого старшины не соответствуют стандартам структурного программирования (см. п. 13 «Структурная методология разработки больших программных комплексов»). Данный вариант решения задачи после «интеллектуальной работы бицепсами правого полушария» следует признать, по меньшей мере, неструктурным и попытаться найти другой подход.
2) Отвести для каждого призывника (точнее, для его роста) отдельную переменную. Здесь, пожалуй, содержится рациональное зерно. Правда, для этого «вы еще много мало знаете». При этом мысль об использовании для роста каждого призывника отдельного идентификатора по типу R1, R2, R3, …, Rn, договоримся сразу относить к разряду фельдфебельских. Речь идет об использовании новой структуры данных, позволяющей с помощью единого идентификатора обращаться к нескольким различным ячейкам (областям памяти), как это показано, например, на рисунке 8.1.
Одномерные массивы
До сих пор при рассмотрении различных переменных мы по умолчанию подразумевали, что одному идентификатору (переменной) соответствует одна единственная ячейка памяти (см. рисунки 4.1, 6.3, 6.8). Однако, это далеко не всегда так. Математики издавна используют переменные с индексами: векторы и матрицы, включающие в себя несколько отдельных элементов, объединенных общим идентификатором. При этом если мы говорим о квадратной матрице A порядка 3, то под идентификатором A понимается вся структура, состоящая из 9 элементов. Для обращения же к отдельным элементам этой структуры необходимо кроме идентификатора указать индексы элемента, характеризующие его положение внутри этой структуры (a1,2, a1,1, ai,j, и т.д.). В программировании для этой цели вводится специальный тип данных – массив, позволяющий при обращении к различным областям памяти использовать один и тот же идентификатор (см. рисунок 8.1). Внутри этой структуры отдельные ее элементы различаются по индексу, который в свою очередь может рассматриваться, как значение переменной и ему может быть поставлен в соответствие свой идентификатор. Индексом массива может быть константа, переменная или выражение любого перечисляемого типа. Индексов у массива может быть один, два или более. Математическим аналогом одномерного массива, имеющего один индекс, является вектор, двумерного – матрица. Для описания массивов в стандарт Pascal’я введен специальный тип ARRAY. Описание массива с одним индексом:
Очень часто значение индекса массива может быть интерпретировано как порядковый номер, однако, это далеко не всегда так. Примеры описания и использования одномерных массивов приведены ниже:
| № п.п. | Фрагмент программы | Комментарии |
| 1. | var A,B: array[1..100] of Real; I: Integer; begin … A[50]:= 34.3; I:=16; B[I]:=2.45; … end. | Во фрагменте приведено описание двух массивов A и B, каждый из которых состоит из 100 действительных чисел. Обращение к элементам массива может осуществляться по индексу, принимающему целочисленные значения из интервала от 1 до 100. В приведенном фрагменте пятидесятый элемент массива A принимает значение 34.3, а шестнадцатый элемент массива B = 2.45; |
| var C:array[-10..10] of Integer; I:Integer; begin … C[-9]:=0; C[0]:=1000; I:=3; C[I]:=45; … end. | Фрагмент описывает один массив, состоящий из 21 целого числа. Индекс массива C может принимать отрицательные значения. В приведенном фрагменте второй по порядку элемент массива C (индекс -9) принимает значение 0, одиннадцатый (индекс 0) – 1000, а четырнадцатый (индекс 3) становится равным 45; | |
| var Ch:array[’a’..’z’] of Real; I:Integer; begin … Ch[’b’]:=0.14; I:=’c’; Ch[I]:=22.4; … end. | Массив Ch состоит из 25 действительных элементов. Индекс представляет собой прописную латинскую букву: тип Char, как это было отмечено в п. 4.4, также является перечисляемым. В приведенном фрагменте второй по прядку элемент массива Ch (индекс ’b’) принимает значение 0.14, третий (индекс ’c’) – 22.4; | |
| 4. | var B:array[False..True] of string; I: Boolean; begin … B[True]:=’Карл’; I:=False; B[I]:=’Клара’; … end. | Массив B состоит всего из двух элементов. Индекс его имеет тип Boolean и может принимать одно из двух значений: True или False. В приведенном фрагменте второй по прядку элемент массива B (индекс True) принимает значение ‘Карл’, первый (индекс False) – ‘Клара’; |
| 5. | var B: array[Boolean] of string; | Синтаксически верная конструкция, идентичная примеру 4[1]. |
Таким образом, в массив может быть объединено конечное, заранее определенное количество данных, относящихся к одному базовому типу. Максимальный интервал изменения индексов должен быть определен на этапе составления описаний переменных и не может быть изменен в процессе выполнения программы. Обращение к отдельным элементам массива осуществляется по индексу. Для одномерного массива:
где
Значение индекса при обращении к элементу массива не должно выходить за пределы описанного диапазона. В противном случае возникает фатальная ошибка, в результате которой ваша программа прекращает работу. Рассмотрим учебный пример с использованием одномерных массивов.
 |
program BeliBerda;
var
A:array[0..5] of Real;
I:Integer;
begin
A[0]:=1.5;
A[1]:=10;
for I:=2 to 5 do
A[I]:= A[I-1]+A[I-2];
for I:=1 to 5 do
WriteLn(’A[’,I,’]= ’,A[I]);
ReadLn;
end.
Как правило, обращение к элементам массива осуществляется в цикле, параметрами которого являются индексы, как это показано в рассмотренном примере.
Использование одномерного массива позволяет легко решить проблему с призывом в танковые войска:
Текст программы:
program Major;
var
R:array[1..500] of Real;
N,I,S,H:Integer;
begin
Write(’Количество призывников (не более 500)? ’);
ReadLn(N);
S:=0;
for I:=1 to N do
begin
Write(‘Введите рост ‘,I,’-го призывника: ’);
ReadLn(R[I]);
S:= S+R[I];
end;
H:= S/N;
WriteLn(‘Средний рост ’,H);
for I:= 1 to N do
if R[I]<H
then WriteLn(’номер ’,I,’– в танковые войска’);
end.
Задание 8.2. Посмотрим, как развивались события в танковых войсках далее. Новобранцам выдали обмундирование и ротного старшину, который начал с того, что решил их построить. Построить в прямом и переносном смысле. В прямом – это по росту, в переносном – ну это умеет делать только старшина срочной службы и этот технологический процесс никакой автоматизации не подлежит. А вот написать программу, которая распечатывала бы нам список бойцов роты по росту – это нам, пожалуй, уже под силу.
Определимся с исходными данными. В отличие от военкомата (см. задачу 8.1) непосредственно в войсковой части приходится иметь дело не с обезличенным призывником, а с конкретным рядовым Теркиным[2], Чонкиным[3], Швейком[4] и т.д. При построении по росту старшина в соответствии с Уставом[5] обязан к подчиненным обращаться по званию и фамилии. Так что кроме роста каждого из подчиненных ему придется познакомиться еще и с фамилиями[6]. Соответственно и в нашей программе должен появиться массив фамилий личного состава.
Постановка задачи
Имеется n новобранцев, каждый из которых имеет фамилию fi и рост ri, i=1÷n. Расположить фамилии новобранцев в порядке убывания роста.
Выбор метода решения и проектирование
В главе 5 мы уже столкнулись с проблемой сортировки в простейшем виде. В нашем случае задача несколько сложнее – располагать по убыванию придется не два, не три, а произвольное число элементов. Алгоритмов сортировки существует великое множество[7], мы воспользуемся тем, который, обычно и использует ротный старшина.
Выглядит это примерно следующим образом: солдаты строятся по команде в одну шеренгу, в общем-то, как бог на душу положит в соответствии с субъективными представлениями о собственном росте и общественной значимости. Старшина, оглядев весь строй, находит самого высокого солдата, который почему-то пока стоит на месте с порядковым номером k: rk|(rk≥rj, j=1÷n), и устраняет вопиющую несправедливость, дав ему команду поменяться с нахалом, самоуверенно занявшим место на правом фланге: rk↔r1; fk↔f1[8] (см. рис. 8.2). Затем, оценив оставшихся гвардейцев, находит уже среди них самого высокого: rk|(rk>=rj, j=2÷n) и меняет его со вторым: rk ↔ r 2; fk ↔ f 2 и т.д. Оставшегося последним солдатика fn ростом rn старшина не оделяет своим вниманием – он и так уже оказался на своем родном левом фланге.
Таким образом, старшина, не изучая трудов Дональда Эрвина Кнута[9], легко решает проблему, называемую в программировании сортировкой по убыванию. Метод, который он при этом использует, в литературе принято называть обменной сортировкой с выбором максимального / минимального элемента. Параметр, по которому выполняется сортировка, называется ключом. В рассматриваемом примере ключом является рост.
В приведенной на рисунке 8.2 блочной схеме используются следующие переменные n – количество солдат в подразделении, f – строковый массив в который записаны фамилии личного состава, r – действительный массив в который записаны значения роста соответствующих солдат. Например, f 5=’Валуев’, r 5=213 означает, что рядовой Валуев имеет рост 2 м 13 см и в настоящий момент он стоит в строю пятым. В принципе декомпозицию алгоритма можно продолжить дальше, подробным образом расписав блоки поиска максимального элемента и обмена – но вряд ли стоит увлекаться художественными изысками. Задача поиска максимального элемента подробно рассматривалась нами в главе 6.
Текст программы.
program Starshina;
var
I,J,N,Max:Integer;
R:array[1..50] of Real;
F:array[1..50] of string;
R0:Real;
F0:string;
begin
Write('N=? '); ReadLn(N);
for I:=1 to N do
begin
Write('Фамилия и рост=? ');
ReadLn(F[I],R[I]);
end;
for I:=1 to N-1 do
begin
Max:=I;
for J:=I+1 to N do
if R[J]>R[Max] 
then
Max:=J;
 |
R0:=R[I];
R[I]:=R[Max];
R[Max]:=R0;
 |
F0:=F[I];
F[I]:=F[Max];
F[Max]:=F0;
end;
for I:=1 to N do
WriteLn(F[I],' ',R[I]:4:2);
ReadLn;
end.
Многомерные массивы
Как уже отмечалось, массивы могут иметь один, два и более индексов. Описание массива с несколькими индексами:
Для обращения к отдельным элементам многомерного массива необходимо указать значение каждого индекса:
Двумерный массив может рассматриваться как матрица. При этом по умолчанию принимается, что первый индекс определяет строку этой матрицы, а второй – столбец. Примеры описания и использования многомерных массивов приведены ниже:
| № п.п. | Фрагмент программы | Комментарии |
| 1. | var A:array[1..10,1..5] of Real; I,J:Integer; begin … A[1,1]:= 6.3; I:=1; J:=5; A[I,J]:=3.14; … end. | Во фрагменте приведено описание массива A, который может быть интерпретирован как прямоугольная матрица, состоящая из 10 строк по 5 действительных элементов в каждой. Обращение к элементам массива может осуществляться указанием двух индексов, принимающих целочисленные значения из интервала от 1 до 10 и от 1 до 5, соответственно. В приведенном фрагменте элемент матрицы A, стоящий в верхнем левом углу на пересечении 1-й строки и первого столбца, принимает значение 6.3, а элемент, стоящий в правом верхнем углу на пересечении 5-го столбца и 1-й строки принимает значение 3.14; |
| var C:array[1..3,1..4,1..10] of Integer; I:Integer; begin … C[2,4,5]:=0; C[1,2,3]:=1000; I:=3; C[I,I,I]:=45; … end. | Фрагмент описывает один трехмерный массив, состоящий из 36 целых чисел. Элементы массива имеют три индекса, меняющиеся в диапазоне от 1 до 3, от 1 до 4 и от 1 до 10, соответственно. В приведенном фрагменте элемент с индексами [3,3,3] принимает значение 45. |
Задание 8.4.
Постановка задачи.
В соревнованиях участвовало 3 команды школьников по 10 человек в каждой. Время, за которое пробежал дистанцию каждый из 30 участников эстафеты, фиксировалось в протоколе. Написать программу, позволяющую вводить с клавиатуры данные из протокола и вычислить среднее время, с которым подошла к финишу каждая из команд.
Выбор метода решения и проектирование
Введем обозначения: i – номер команды (i принимает целочисленные значения из интервала от 1 до 3), j – номер участника (j принимает целочисленные значения из интервала от 1 до 10), tij – время, за которое пробежал дистанцию j-й участник i-й команды. Для вычисления si – среднего времени, с которым подошла к финишу i-я команда необходимо просуммировать результаты всех десятерых ее участников:
. (8.1.)
Наиболее подходящей (из изученных нами) структурой для хранения результатов каждого участника представляется двумерный массив, у которого первый индекс – номер команды, второй – номер участника. Результаты команд удобнее всего хранить в одномерном массиве, индексированном по номеру команды.
Первая проблема, с которой придется столкнуться – это ввод двумерного массива. Возможны два подхода, зависящие от того, какую форму имеет протокол соревнований.
1) Протоколы составляются для каждой команды отдельно и обрабатываются последовательно. Сначала вводятся все 10 результатов участников первой команды в соответствии с первым протоколом. Завершив эту операцию, переходим к вводу результатов участников второй команды в соответствии со вторым протоколом, затем третей. Фрагмент блочной схемы, организующий ввод данных по предложенной схеме показан на рисунке 8.3 а и реализует построчный ввод матрицы.
2) Отдельные протоколы не составляются, ведется единый сводный протокол, отражающий результаты в таблице, сгруппированной по номерам участников и командам. В этом случае сначала вводятся результаты участников, идущих под первым номером для каждой из команд. В соответствии с условием задачи таких участников трое. Затем точно также вводятся результаты вторых номеров, затем – третьих, четвертых, пятых и т.д., до тех пор, пока не будут введены результаты последних троих соперников, идущих под номером 10. Фрагмент блочной схемы, организующий ввод данных по предложенной схеме показан на рисунке 8.3 б и реализует ввод матрицы по столбцам.
Право на существование имеет как первый, так и второй подход: результаты ввода будут идентичными. Реализации будут отличаться на уровне организации удобного пользовательского интерфейса.
После того, как массив исходных данных введен, можно приступить к расчетам по формуле (8.1). Здесь уже выбор варианта перебора элементов матрицы не зависит от требований интерфейса. На первый план выходят требования эффективности и читабельности, понятности алгоритма. С этой точки зрения удобнее в качестве внешнего цикла использовать тот, параметром которого является номер команды. Блочная схема алгоритма решения задачи 8.4. представлена на рисунке 8.4.
Текст программы [10]:
program Сompetitions;
var
I,J:Integer;
S:array[1..3] of Real;
T:array[1..3,1..10] of Real;
begin
for I:=1 to 3 do
begin
WriteLn(‘Команда N ’,I);
for J:=1 to 10 do
begin
Write(‘Время ’,J,‘-го участника? ’);
ReadLn(T[I,J]);
end;
end;
for I:=1 to 3 do
begin
S[I]:=0;
for J:=1 to 10 do
S[I]:=S[I]+T[I,J];
S[I]:=S[I]/10;
end;
for I:= 1 to 3 do
Write(‘Среднее время ’,I,‘-й команды ’,S[I]);
ReadLn;
end.
Задание 8.5.
Постановка задачи
Заполнить квадратную матрицу A порядка n таким образом, чтобы выше главной диагонали располагались нули, ниже – единицы, а по главной диагонали – двойки (рисунок 8.5).