Выбор метода решения и проектирование

Переменные с индексами. Массивы

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

Задание 8.1.

Постановка задачи

В военкомат на медкомиссию вызвали N призывников. Известен рост каждого призывника r_i. Написать программу, вычисляющую средний рост призывников. Распечатать номера тех призывников, чей рост оказался ниже среднего (для отправки в танковые войска).

Выбор метода решения и проектирование

На первый взгляд задача во многом повторяет задание 6.5. Однако при ближайшем рассмотрении оказывается, что использовать для ее решения алгоритм, предложенный выше, не представляется возможным. Решение, которое мы нашли в п.6, при всех его достоинствах обладает одним серьезным недостатком: по окончании работы алгоритма существенная часть исходных данных, а именно значения роста всех призывников (кроме последнего) оказываются утерянными и сравнивать со средним ростом нечего.

Очевидны два решения создавшейся проблемы:

1) После того как программа рассчитала средний рост – применить унтер-офицерский подход, заставить пользователя «не тянуть резину в долгий ящик» и вторично ввести исходные данные:

program Feldfebel;

var

N,I:Integer;

S,H,R:Integer;

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 элементов. Для обращения же к отдельным элементам этой структуры необходимо кроме идентификатора указать индексы элемента, характеризующие его положение внутри этой структуры (a_1,2, a_1,1, a_i,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 новобранцев, каждый из которых имеет фамилию f_i и рост r_i, i=1÷n. Расположить фамилии новобранцев в порядке убывания роста.

Выбор метода решения и проектирование

В главе 5 мы уже столкнулись с проблемой сортировки в простейшем виде. В нашем случае задача несколько сложнее – располагать по убыванию придется не два, не три, а произвольное число элементов. Алгоритмов сортировки существует великое множество[7], мы воспользуемся тем, который, обычно и использует ротный старшина.

Выглядит это примерно следующим образом: солдаты строятся по команде в одну шеренгу, в общем-то, как бог на душу положит в соответствии с субъективными представлениями о собственном росте и общественной значимости. Старшина, оглядев весь строй, находит самого высокого солдата, который почему-то пока стоит на месте с порядковым номером k: r_k|(r_k≥r_j, j=1÷n), и устраняет вопиющую несправедливость, дав ему команду поменяться с нахалом, самоуверенно занявшим место на правом фланге: r_k↔r₁; f_k↔f₁[8] (см. рис. 8.2). Затем, оценив оставшихся гвардейцев, находит уже среди них самого высокого: r_k|(r_k>=r_j, j=2÷n) и меняет его со вторым: r_k↔r₂; f_k↔f₂ и т.д. Оставшегося последним солдатика f_n ростом r_n старшина не оделяет своим вниманием – он и так уже оказался на своем родном левом фланге.

Таким образом, старшина, не читая трудов Кнута[9], легко решает проблему, называемую в программировании сортировкой по убыванию. Метод, который он при этом использует, в литературе принято называть обменной сортировкой с выбором максимального/ минимального элемента. Параметр, по которому выполняется сортировка, называется ключом. В рассматриваемом примере ключом является рост.

В приведенной на рисунке 8.2 блочной схеме используются следующие переменные n – количество солдат в подразделении, f – строковый массив в который записаны фамилии личного состава, r – действительный массив в который записаны значения роста соответствующих солдат. Например, f₅=’Иванов’, r₅=210 означает, что рядовой Иванов имеет рост 2 м 10 см и в настоящий момент он стоит в строю пятым. В принципе декомпозицию алгоритма можно продолжить дальше, подробным образом расписав блоки поиска максимального элемента и обмена – но вряд ли стоит увлекаться художественными изысками. Задача поиска максимального элемента подробно рассматривалась нами в главе 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 участников эстафеты, фиксировалось в протоколе. Написать программу, позволяющую вводить с клавиатуры данные из протокола и вычислить итоговое время, с которым подошла к финишу каждая из команд.