Программирование обработки массивов, строк и записей

Как говорилось выше (гл. 1, п. 4.1), массив — это структура данных одного типа. Одномерный массив представляет собой последовательность элементов, двумерный — матрицу.

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

Ввод массива с клавиатуры осуществляется поэлементно, т. е. один элемент за другим. Для этого организуется цикл. Чаще всего в этих целях используется тип цикла For-do.

Программа ввода одномерного числового массива X с числом элементов п = 20 приведена ниже.

Program Mass; {Ввод одномерного массива}

Var

i,n: integer; {Индекс элемента и их количество в массиве}

x:Array [1..20] of real; {Объявление массива}

Begin

For i=l to 20 do

Begin

Writeln ('Введите элемент' x(',i',)');

Readln (x(i));

Write (x(i):4:l); {Вывод элемента массива}

End;

End.

В этой программе для облегчения ввода в операторе Writeln будет выводиться подсказка «Введите элемент х(1), х(2)» и т. д. Вывод элементов осуществляется в строку и для каждого элемента отводится четыре позиции, одна из которых предназначена для изображения дробной части числа. Таким образом, вся строка вывода в 80 позиций будет полностью заполнена. Если бы мы вводили, например, 30 чисел, то вывод в таком формате был бы продолжен в следующей строке. Для вывода в столбец понадобилось бы использовать оператор Writeln (x(i):4:l).

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

Program MG; {Генерация массива натуральных чисел}

Var

i,n: integer; {Индекс элемента массива и его размер} x:Array [1..100] of integer {Объявление массива}

Begin

Write ('Введите п < 100');

Readln (п);

For i=l to n do

Begin

x(i):=i;

Writeln;

Write (x(i));

End;

End.

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

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

Program MS; {Генерация массива символов}

Var

i: integer; {Индекс элемента массива}

S:Array [65..127] of String {Объявление массива}

Begin

For i=65 to 127 do

Begin

S(i):=Chr(i);

Write (S(i));

End;

End.

В этой программе функция Chr(i) преобразует код в символ, который заносится в массив S и попутно выводится на экран.

С помощью функции Random, возвращающей псевдослучайное число из интервала [0, 1), можно сгенерировать массив случайных чисел из любого интервала [а, Ь. Это выполняет следующая программа.

Program MS; {Генерация массива случайных чисел}

Var

i,n: integer; {Индекс элемента массива и его размер}

a,b: real; {Границы интервала}

R:Array [1..100] of real {Объявление массива}

Begin

Write ('Введите n');

Readln (n);

Writeln ('Введите a,b; 1 < а < b < 100'); Readln (a,b);

Randomize;

For i=l to n do Begin

R(i):=Int (a+Random*(b-a));

Write (R(i):3);

End;

End.

В этой программе процедура Randomize запускает генератор псевдослучайных чисел, которые вырабатывает функция Random на интервале [0, 1). Функция Int отбрасывает дробную часть полученного случайного числа a+Random*(b-a).

Необходимо обратить внимание на то, что при объявлении массивов всегда указывались числовые границы его пределов. Это так называемый статический способ их объявления, и без такого указания компилятор Turbo Pascal не выделит память, необходимую для хранения элементов массива. Вместе с тем на практике встречается много задач, которые требуют динамического распределения памяти, т. е. такого распределения, которое осуществляется в процессе выполнения программы. Например, требуется работа с одномерным массивом, в котором его границы а, b] периодически принимают разные числовые значения, либо обрабатывать матрицу (двумерный массив), в которой с каждым новым запуском программы изменяется число строк и столбцов.

В языке Turbo Pascal 7.0 нет простых средств выделения памяти под массивы на основании задания их пределов операторами ввода или присваивания, как это сделано, например, в языке Turbo Basic. В этом, безусловно, недостаток Turbo Pascal. Однако в Turbo Pascal есть мощное средство динамического распределения памяти за пределами сегмента данных, где хранятся данные каждой программы. Чтобы это уяснить без особых затруднений, на рис. 4.8 приведена упрощенная схема использования памяти персонального компьютера.

Системный раздел памяти

Сегмент данных 64 Кб

Стек 16 Кб

Программа

Куча

Рис. 4.8. Распределение оперативной памяти ПК

Системный раздел памяти ПК предназначен для размещения системных компонент: вектора прерываний, буферов ввода-вывода данных, транзитов ОС, драйверов и др. В сегменте данных компилятор размещает данные к оттранслированной программе: константы, переменные, поля памяти под массивы. Назначение стека — обеспечение работы подпрограмм. Каждая программа занимает свое число ячеек памяти, определенное количеством ее предложений. Сразу же за программой следует раздел памяти, который называется «кучей».

Начальные и конечные адреса кучи всегда определены и хранятся соответственно в переменных Heaporg и Heapend.

В первых персональных компьютерах PC XT куча практически составляла примерно 200—300 Кб. Однако работа программ ограничивалась величиной памяти, которая обеспечивалась сегментом данных в 64 Кб. В частности, в этом разделе допускалась «игра» границ массивов в Turbo Basic.

В Turbo Pascal 7.0 такая «игра» не предусмотрена. Если необходимо изменять пределы массивов в процессе работы программы, следует предварительно задать предельные их числовые значения, допустимые сегментом данных 64 Кб. Если же массивы не размещаются в этом сегменте, языком предоставлена возможность определять эти массивы в куче, однако, опять-таки в наперед установленных числовых пределах.

Для задания динамических переменных в языке Turbo Pascal 7.0 используются специальные переменные, называемые указателями (на английском — Pointer). Эти переменные могут хранить только адреса ячеек памяти, в которых хранятся те или иные данные.

Один указатель может адресовать 64 Кб памяти. Ячейка-указатель занимает 2 байта памяти.

Различают типизированные и нетипизированные указатели. Типизированные указатели адресуют определенный тип данных. Например,

Var i: integer; х: Лгеа1; j: integer.

Не связанный ни с каким типом переменных, указатель имеет тип Pointer, например, Var a,b,k: pointer. Такой указатель чаще всего адресует переменные, тип которых изменяется в процессе выполнения программы. Знак А — крыша в объявлении типизированных указателей i, х определяет то, что именно эти переменные являются указателями.

Для указателей в пределах одного типа допустимы операции присваивания. Например, справедливо: i:=j или j:=i. Однако ошибочно i:=x и x:=j, так как х и j имеют разные типы. Справедливо также i:=a и a:=i, так как а нетипизировано.

Над указателями также могут выполняться операции сложения и сравнения. В этом случае указатель обозначается так:

i := 1л+ jA.

Объявление указателя массива осуществляется с применением типа пользователя. Например, чтобы описать указатель массива Rd 1000 действительных чисел R, необходимо записать:

Туре

R:Array [1..100] of real; {Объявление массива}

Var

Rd=AR; {Описание указателя Rd на массив}

Выделение памяти в куче по указателю под динамическую переменную определяется типом переменной. Например, если i:Ainteger — указатель на переменную целого типа, a xCreal — на переменную вещественного типа, то в первом случае в куче будет выделено 2 байта памяти, а во второй — 6 байт памяти.

Под массив память выделяется непрерывным участком на основании типа переменных и их количества. Например, для хранения чисел массива R в куче будет выделено 6* 1000 = 6000 байт памяти. Непосредственно выделение памяти осуществляет процедура New (указатель). Если записать New (Rd), то будет выделено 6000 байт.

В языке Turbo Pascal 7.0 предусмотрена не только процедура выделения памяти New (указатель), к слову сказать, она не единственна, но и парная ей процедура освобождения выделенного участка — Dispose (указатель).

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

  • 1) описываются указатели переменных;
  • 2) с помощью указателей выделяется память в куче;
  • 3) программируются операции над данными в выделенном разделе кучи;
  • 4) освобождается память.

В качестве примера использования указателей рассмотрим составление программы ввода одномерного массива.

Program D-Mass; {Ввод массива}

Туре

Mass:Array fl..200]; {Объявление массива}

Var

x^Mass; {Объявление указателя на массив}

i,n: integer; {Индекс элемента массива и его размер}

Begin

New (х);{Выделение памяти под массив по указателю на массив х} Write ('Введите размер массива п');

Readln (п);

For i=l to n do

Begin

Write Ox(i’)’);

Readln (xA(i)); {Ввод очередного элемента массива x(i)}

End;

Begin

{Инструкции по обработке массива х}

End;

Dispose (х); {Освобождение памяти, выделенной под массив х}

End.

В заключение отметим, что операционная система MS-DOS, приложением которой является среда программирования Turbo Pascal 7.0, допускает использование кучи в объеме не более 64 Кб. Для того чтобы распространить технику использования указателей на весь объем памяти современных ПК, например, 256 Мб или 512 Мб, необходимо применять специальные программные средства, изложенные в [35], или программировать в среде Delfi.

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

Блок-схема алгоритма поиска наибольшего и наименьшего элементов массива приведена на рис. 1.20. Действуя согласно этой схеме, получим следующую программу.

Program Min Max; {Поиск наименьшего и наибольшего}

{Элементов массива}

Var

a:Array fl..500} of real; {Объявление массива а, содержащего}

{500 элементов}

i,j: integer; {Индексы наибольшего и наименьшего элементов} {Массива}

k,n: integer; {Индекс текущего элемента массива и}

{Количество его элементов}

max,min: real; {Значения максимального и минимального}

{элементов Массива}

Begin

{Ввод элементов массива п < 500}

Write ('Введите п');

Readln (п);

For k=l to n do Begin

Write (’а('Д’)’);

Readln (a(i));

End;

{Поиск максимального и минимального элемента} max:=a(l); i:=l; min:=a(l); j:=l;

For k=2 to n do

Begin

If a(k)>max Then Begin

max:=a(k); i:=k;

End;

If a(k)

min:=a(k); j:=k;

End;

End;

{Вывод результатов поиска} Writeln ('max =', max:6:2, 'i=', i:3); Writeln ('min =', min:6:2, 'j=', j:3);

End.

Программу поиска заданного числа в неупорядоченном массиве X составим, следуя блок-схеме алгоритма, представленной на рис. 1.22. Массив получим путем генерации чисел, применяя функцию Random.

Program Poisk; {Поиск заданного числа в массиве}

Var

i,n: integer; {Индекс элемента массива и его размер} c,d: real; {Интервал, которому принадлежат числа} b: real; {Заданное число} a:Array [1..300] of real; {Объявление массива}

Begin

Write ('Введите n); Readln (п);

Writeln ('Введите c,d, i < с < d < 300"); Readln (c,d);

Randomize;

For i=l to n+1 do Begin

a(i):=Int(a+Random*(d-c)); {Генерация массива чисел} Write (a(i):3); {Вывод чисел}

End;

Write ('Введите число b=');

Readln (b);

a(n+l):=b; {Запись а в ячейку n+1}

For i=l to n+1 do

If a(i)=b Then Break;

If i=

End.

В этой программе выход из цикла For — do осуществляется по оператору Break в двух случаях: когда a(i) = b, т. е. число найдено, и когда ?j = ап+1, так как ап+1 = Ь. Вместо оператора цикла For — do можно было бы использовать и операторы While — do, Repeat — do, однако при этом перед входом в циклы пришлось бы записывать i:=l, а в теле циклов i:=i+l, что удлиняет программу.

Программа сортировки массива, составленная согласно алгоритма (см. рис. 1.23), приведена ниже. В этой программе опущен фрагмент генерации массива чисел, который рассмотрен выше в задаче поиска заданного числа в массиве.

Program Sort; {Сортировка массива по возрастанию вставками}

Var

i,n: integer; {Индекс элемента массива и его размер} j: integer; {Вспомогательный индекс} k: real; {Сортируемый элемент массива} a:Array [ 1 ..300] of real; {Объявление массива}

Begin

{Инструкции генерации массива}

For i=2 to n do {Начало внешнего цикла сортировки}

Begin

k:=a(i); j:=j-l;

While k

Begin

If j=<0 Then Break;

Else

Begin

a(j+l):=a(j); j:=j-l;

End;

End; {Конец внутреннего цикла} a(j+l):=k;

End; {Конец внешнего цикла}

For i=l to n do

Write (a(i):3); {Вывод отсортированного массива}

End.

В этой программе используется структура вложенных циклов. Внешний цикл типа For — do, внутренний While — do.

Ниже приведена программа поиска заданного числа в упорядоченном по возрастанию массиве, составленная по алгоритму, изображенному на рис. 1.24. Как и в рассмотренной ранее программе Sort, в этой программе также опущен фрагмент генерации массива. Предполагается также, что полученный массив отсортирован программой Sort.

Program B Poisk; {Бинарный поиск в массиве}

Lable

Finish;

Var

i, n: integer; {Индекс элемента массива и его размер}

j, l,u: integer; {Вспомогательные индексы} b: real; {Заданное число}

a:Array [1..300] of real; {Объявление массива}

Begin

{Инструкции генерации массива а и его упорядочения}

{по возрастанию}

For i=l to n do Begin

If u

Begin Write ('Элемент не найден'); Go to Finish;

End;

j:=(l+u) div 2;

If a(j)=b Then Break;

Else

Begin

If a(j)

Else l:=j+l;

End;

End;

Write ('Элемент найден');

Finish:

End.

В этой программе используется цикл For — do, который повторяет тело цикла до выхода либо по условию и < 1, либо по условию a(j) = b, т. е. когда число найдено. В этом случае выход из цикла осуществляется по оператору Break.

Бинарный поиск, как говорилось выше (гл. 1, п. 4.1), может применяться и для уточнения корней трансцендентных или алгебраических уравнений. Блок-схема алгоритма такого поиска, называемого методом дихотомии (деления пополам), приведена на рис. 1.26. Согласно этой блок-схеме составлена программа поиска корня уравнения ех -х - 2 = 0.

Program Dih; {Уточнение корня методом дихотомии}

Labi?

Finish;

Var

a,b: real; {Границы интервала расположения корня} х: real; {Значение корня}

u,v,w: real; {Значение функции у = ех-х-2 в разных точках}

Eps: real; {Точность вычисления корня}

Begin

u:=Exp(a)-a-2; v:=Exp(b)-b-2;

Repeat

x:=(a+b)/2; w:=Exp(x)-x-2;

If w=0 Then

Begin Write ('Корень найден точно');

Goto Finish;

End;

If u*w>0 Then

Begin a:=x; u:=w; End;

Else

Begin

b:=x; v:=w; End;

Until Abs(a-b)<=Eps;

x:=Abs(a-b); Write ('Корень x=', x:6:3);

Finish:

End.

В программе используется оператор Repeat, организующий цикл. Этот цикл повторяется до тех пор, пока не выполняется условие | а - b < s.

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

Для решения задачи представим последовательности элементов массива с четным и нечетным числом их элементов в виде схем, изображенных на рис. 4.9.

«1

«2

«3

й4

«5

«6

«7

«8

а

«1

«2

«3

«4

«5

«6

«7

б

Рис. 4.9. Массивы с четным и нечетным числом элементов

Из этих схем наглядно следует, что в массиве с четным числом элементов необходимо поменять местами пары х, ан), (а2, а7), (я3, а6), (а4, а5), в массиве с нечетным числом элементов — пары х, а7), (а2, аь),3, а5). И в том и в другом случае число обменов равно п, деленное на 2 нацело.

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

Схема обмена элементов массива

Рис. 4.10. Схема обмена элементов массива

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

Блок-схема алгоритма, решающего эту задачу, изображена на рис. 4.11.

Программа решения задачи составлена в соответствии с алгоритмом. В качестве массива используется массив строчных букв латинского алфавита, пример получения которого продемонстрирован программой MS.

Program ОВМ; {Обмен элементов массива}

Var

i,n: integer; {Индекс элемента массива и его размер} m: integer; {Количество элементов массива п/2} а:Аггау [97.. 127] of Char; {Объявление массива} х: Char; {Вспомогательные ячейки}

Begin

Write ('Введите n); Readln (n);

For i=97 to n do

Begin

a(i):=Chr(i); {Генерация массива символов}

Write (a(i):2); {Вывод элементов массива}

End;

m:=n div 2;

For i=l to m do Begin

x:=a(i); a(i):=a(n+l-i); a(n+l-i):=x;

End;

{Вывод переставленных элементов массива}

Writeln;

For i=l to n do Write (a(i):2);

End.

В этой программе элементы массива а(п + 1 - /') определяют: для /= 1 - я„, для i=2- я„_, и т. д.

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

Алгоритм обмена элементов массива

Рис. 4.11. Алгоритм обмена элементов массива

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

Ниже приведена программа ввода матрицы с числом строк т и числом столбцов п по строкам.

Program Matrix; {Ввод матрицы}

Const

m=100; n=l 00; {Определение количества строк и столбцов}

Var

i,j: integer; {Индекс строки и столбца}

A:Array [l..m, l..n] of real; {Объявление массива}

Begin

For i=l to m do Begin

For j=l to n do Begin

Write ('A(',i, ', j, ’)=’);

Readln (A[iJ]);

End;

End;

End.

В этой программе количество строк т и столбцов п указано в разделе объявления констант. Возможен и другой вариант, когда массив объявляется, как A:Array [1..100, 1..100], а конкретные значения т, п в операторах цикла задаются оператором ввода Readln (m,n). В этом случае можно ввести массив А с меньшим количеством строк и столбцов. Программа будет выглядеть так

Program Matrix 1; {Ввод матрицы}

Var

i,j: integer; {Индексы строк и столбца} m,n: integer; {Количество строк и столбцов}

A:Array [1..100, 1.. 100] of real;

Begin

Write ('Введите m, n'); Readln (m,n);

For i=l to m do Begin

Forj=l to n do Begin

Write ('АС,і, ’j, )'=');

Readln (A[i,j]);

End;

End;

End.

Вывод матрицы на экран дисплея может быть осуществлен так же, как и ввод, как по строкам, так и по столбцам. Размещение матрицы на экране осуществляется процедурой GoTo XY (позиция в строке, строка).

Предположим, что по программе Matrix 1 введена числовая матрица А, содержащая 20 строк и 20 столбцов. Каждый элемент A[i,j] этой матрицы представляет собой двузначное число. Требуется вывести матрицу по центру экрана монитора по строкам.

Рассуждаем следующим образом. Каждая строка двузначных чисел занимает 20 • 2 = 40 позиций. Для нормального чтения чисел разделим их одним пробелом. То есть на каждое число отведем три позиции. Тогда каждая строка будет представляться 20 • 3 = 60 позициями. Поскольку в каждую строку экрана можно вывести 80 символов от 1 до 80, то 40-я позиция делит строку пополам. Таким образом, чтобы разместить выводимую строку по центру, необходимо от 40-й позиции отсчитать 30 позиций влево и начать вывод строки с 9-й ее позиции. Это будет центрированное горизонтальное размещение вывода.

Центрированное вертикальное размещение получаем аналогичным путем. Так как на экране можно разместить 25 строк, то 12-я строка делит его по горизонтали примерно пополам. Поэтому вывод матрицы можно начать с 3-й строки. Перед этим в первой строке желательно поместить надпись «Матрица А», а 2-ю строку пропустить. Программа ввода-вывода матрицы А будет такой.

Program W_Matrix; {Ввод-вывод матрицы А по центру экрана}

Var

i,j: integer; {Индексы строк и столбцов А} m,n: integer; {Количество строк и столбцов} k: integer; {Вспомогательная переменная-счетчик}

A:Array f 1.. 100, 1..100] of real; {Объявление массива}

Begin

{Инструкции ввода матрицы А}

GoTo XY(34,1); Write ('Матрица A’); k:=2;

For i=l to 20 do Begin

k:=k+l; GoTo XY(9,k);

For j=l to 20 do

Begin

Write (A[i,j]:3);

Writeln;

End;

End;

End.

Числовая матрица может быть введена не только с клавиатуры или файла, но и получена программным путем применением функции Random, как это делалось для одномерных массивов. Символьную матрицу также программным путем можно получить на основании кодовой таблицы ASCII. Рассмотрим эти способы. Ниже приведена программа генерации числовой матрицы.

Program G_Matrix; {Генерация матрицы}

Var

A:Array [1..100, 1..100] of real; {Матрица А} iJ: integer; {Индексы строк и столбцов А} m,n: integer; {Количество строк и столбцов А} a,b: real; {Левая и правая границы интервала чисел}

Begin

Writeln ('Введите m,n'); Readln(m,n);

Writeln ('Введите a

Randomize;

For i=l to m do Begin

For j=l to n do A[i,j]:=Int(a+Random*(b-a));

End;

End.

Символьную матрицу получим следующим образом. Просмотрим коды от 32 до 127 таблицы ASCII. Это составит 127 -- 32 + 1 = 96 кодов. Далее эти коды представим в виде матрицы с 8 строками и 16 столбцами, что дает число 96. Программа приведена ниже.

Program S Matrix; {Получение символьной матрицы}

Var

S:Array [1..8, 1..16] of Char; {Объявление матрицы} i,j: integer; {Индексы строк и столбцов матрицы S} k: integer; {Счетчик кодов}

Begin

k:=31;

For i=l to 8 do {Цикл по строкам}

Begin

For j=l to 16 do

Begin

k:=k+l; {Счет кодов}

S(i,j):=Chr(k); {Преобразование кода}

Write (S(ij)); {Вывод символа в строку}

End;

Writeln; {Начало новой строки}

End;

End.

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

Программа суммирования элементов верхней треугольной матрицы составлена согласно блок-схеме алгоритма, изображенного на рис. 1.31.

Program Sum; {Суммирование элементов верхней}

{треугольной матрицы}

Var

A:Array [1..100, 1..100} of real; {Объявление массива} i,j: integer; {Индексы строк и столбцов матрицы А} n: integer; {Количество строк и столбцов А}

ST: real; {Сумма верхней треугольной матрицы А}

Begin

{Генерация матрицы А с числом строк и столбцов п}

ST:=0;

For i=l to n do {Внешний цикл по строкам}

Begin

For j=i+l to n do {Внутренний цикл по столбцам} ST:=ST+A(i,j); {Суммирование элементов}

End;

Writeln (’Сумма ST= ST:6:2);

End.

Программа транспонирования матрицы А составлена согласно алгоритма, блок-схема которого изображена на рис. 1.32.

Program Trans; {Транспонирование матрицы А}

Var

A:Array [1..20, 1..20] of Char; {Символьная матрица А} іJ: integer; {Индексы строк и столбцов А} n: integer; {Число строк и столбцов, п < 20} u: char; {Вспомогательная переменная}

Begin

{Генерация матрицы с числом строк и столбцов п}

For i=l to n do {Внешний цикл}

Begin

For j=l to n do {Внутренний цикл}

Begin

u:=A(i,j); A(ij):=A(j,i); А(і,і):=и;{Обмен элементов}

End;

End;

{Вывод транспонированной матрицы}

End.

Программа умножения матрицы с количеством строк m и столбцов п на вектор В с числом элементов п составлена согласно блок-схеме решающего алгоритма (см. рис. 1.33).

Program A B; {Умножение матрицы А на вектор В}

Var

A:Array [1..30, 1..40] of real; {Матрица А}

В:Array [1..40] of real; {Вектор В размера 40}

Am:Array [ 1 ..30] of real; {Вектор-результат умножения А на}

{В размера 30}

i,j: integer; {Количество строк и столбцов А}

Sk: real; {Скалярное произведение}

Begin

{Генерация матрицы А и вектора В}

For i=l to m do {Внешний цикл}

Begin

Sk:=0; {Начальное значение Sk}

Forj=l to n do {Внутренний цикл}

Sk:=Sk+A(i,j)*B(j); {Очередное значение Sk} Am(i):=Sk; {Формирование вектора Am}

End;

{Вывод Am}

End.

Программа умножения матрицы А на матрицу В составлена в соответствии с блок-схемой алгоритма, изображенного на рис. 1.34.

Program А*В; {Умножение матрицы А на матрицу В}

Var

A:Array [1..20, 1..30] of real; {Матрица А}

B:Array f 1 ..30, 1..10] of real; {Матрица В}

AM:Array f 1 ..20, 1..10] of real; {Матрица А*В}

i: integer; {Индексы строк А}

j: integer; {Индексы столбцов А и строк В}

q: integer; {Индексы столбцов матрицы AM}

m,n: integer; {Количество строк и столбцов А, п < 20, п < 30}

k: integer; {Количество столбцов В, к < 10}

Sk: real; {Скалярное произведение}

Begin

{Генерация матриц А и В}

For q=l to k do {Цикл по столбцам В}

Begin

For i=l to m do {Цикл по строкам A}

Begin

Sk:=0;

Forj=l to n do {Цикл по столбцам A}

Begin

Sk:=Sk+A(ij)*B(j,q); {Скалярное произведение}

AM(i,q):=Sk; {Заполнение столбца AM}

End;

End;

End;

{Вывод матриц AM}

End.

Теперь составим программу решения системы п линейных уравнений с п неизвестными методом исключения Гаусса (задача 1.28, гл. 1, п. 1.4). Укрупненная блок-схема алгоритма решения этой задачи изображена на рис. 1.35.

Исходными данными для ее решения являются матрица А коэффициентов при неизвестных в линейных уравнениях А и вектор В правых частей уравнений размера п. Результат решения — вектор неизвестных X размера п.

Согласно укрупненной блок-схеме алгоритма, кроме ввода исходных данных и вывода результатов решения задачи, необходимо программировать поиск минимального элемента в столбце матрицы и обмена строк, процедуру вычитания строк, а также поиск вектора X. Блок-схемы алгоритмов, реализующих эти процедуры, изображены соответственно на рис. 1.36, 1.47, 1.38. Действуя согласно укрупненной блок-схеме алгоритма и этим блок-схемам, получим следующую программу.

Program Gauss; {Решение системы линейных уравнений}

{методом Гаусса}

Labi?

Finish;

Var

A:Array f 1 ..30, 1 ..30] of real; {Матрица А}

B:Array f 1 ..30] of real; {Вектор В}

ХАлтау [1..30] of real; {Вектор X}

n: integer; {Количество строк и столбцов А, размеры В,Х} i,j: integer; {Индексы строк и столбцов А} k: integer; {Индекс исключаемого переменного}

1: integer; {Индекс максимального элемента в столбце А} m,z,s: real; {Вспомогательные переменные}

Begin

Writeln ('Введите n'); Readln (п);

For i=l to n do {Внешний цикл ввода А,В}

Begin

Writeln ('B(',i,', {Ввод элементов В}

Readln (B[jl);

Forj=l to n do {Внутренний цикл ввода A}

Begin

Writeln ('A(',i,', ' j'='); {Ввод элементов A}

Readln (A[iJ]);

End;

End;

{Построение треугольной матрицы}

For k=l to n-1 do Begin

{Поиск индекса максимального элемента в столбце А}

1:=к;

For i=k+l to n do

If Abs(A[i,k])>Abs(A[l,k]) Then l:=i;

{Проверка системы на совместимость}

If A[l,k]=0 Then

Begin

Write ('Система не совместна'); GoTo Finish;

End;

{Обмен строк матрицы А}

If lok Then Begin

z:=B[k]; B[k]:=B[l]; B[l]:=z;

For j=k to n do

Begin

z:=A[k,j]; A[kj]:=A[lj]; A[lJ]:=z;

End;

End;

{Вычитание строк матрицы A}

Fori=k+l to n do

Begin

m:=A[i,k]/A[k,k]; A[i,k]:=0;

Forj=k+l to n do A[i,j]=A[ij]-m*A[kj]; B[i]=B[i]-m*B[k];

End;

End;

{Вычисление компонент X}

X[n] :=B[n]/A[n,n];

For i=i-n downto 1 do Begin S:=0

For j=i+l to n do S:=S+A[i,j]*X[j];

X[i]:=(B[i]-S)/A[ij];

End;

{Вывод X}

Writeln ('Решение системы такое:');

For i=l to n do

Write (X[i]:6:2);

Finish;

End.

Программа записи чисел в матрицу А по спирали (задача 1.29, гл. 1, п. 4.1) составлена в соответствии с алгоритмом (см. рис. 1.43). Он предполагает, что сначала ручным способом определены индексы матрицы А, которые соответствуют последовательным элементам спирали.

Program Spir; {Запись чисел в матрицу А по спирали}

Var

i,j: integer; {Индексы строк и столбцов А} k: integer; {Индекс элемента спирали}

A: Array [1..10, 1..10] of integer; {Матрица А}

Begin

For k=l to 49 do Begin

Writeln ('i=', i j='j); {Ввод индексов A}

A[ij]:=k; {Запись в А элемента спирали}

End;

{Вывод матрицы А}

ClrScr; {Очистка экрана}

For i=l to 7 do Begin

For j=l to 7 do Begin

Write (A[i,j]):3); {Вывод элемента}

Writeln; {Возврат к началу строки}

End;

End;

End.

Изложим технологию составления программы поиска лучшего маршрута коня (задача 1.30, гл. 1, п. 4.1). Согласно укрупненного алгоритма (см. рис. 1.43), разработанного для решения этой задачи, необходимо составить программы инициализации обрамления доски (блок-схемы рис. 1.44, 1.45), инициализации непосредственно шахматной доски, построение маршрута коня и выделение лучшего маршрута (блок-схема рис. 1.46), вывода маршрута на экран с указанием его длины.

Вначале составим раздел объявлений переменных, пользуясь тем, что в алгоритме применяется двумерный массив d с количеством строк и столбцов, равных 12. Кроме этого, используется два одномерных массива целых констант ik, jk размером 8, два рабочих массива индексов rrij размерами 64 каждый и два массива индексов лучшего маршрута тн, т}1 также размером 64 элемента каждый. Таким образом, в программе будут использоваться 7 массивов, из которых один двумерный и шесть одномерных. Поэтому раздел объявлений будет таким:

Program Tour; {Маршрут (тур) коня}

Var

d: Array [1..12, 1..12] of byte; {Интерпретация доски}

k,}k'- Array f 1 ..81 of byte; {Константы для индексов}

Array [1..64] of byte; {Рабочие индексы маршрута} m,Y,rxjf. Array [ 1 ..64] of byte; {Индексы лучшего маршрута} ij: byte; {Индексы массива d} n: byte; {Номер очередного поля доски} k: byte; {Порядковый индекс хода коня}

1: byte; {Признак лучшего маршрута}

Теперь согласно общей блок-схеме алгоритма (см. рис. 1.43) вначале составим фрагменты программы инициализации обрамления доски. Для этого воспользуемся блок-схемами рис. 1.44, 1.45.

{Инициализация верхнего обрамления доски}

Begin

For i=l to 2 do Begin

For j=l to 12 do

d[i,jl :=66;

End;

{Инициализация нижнего обрамления доски}

For i=l 1 to 12 do Begin

Forj=l to 12 do

d[i,jl:=66;

End;

{Инициализация левого и правого обрамления доски}

For i=3 to 10 do Begin

d[i,l]:=66; d[i,2]:=66;

d[i,ll]:=66; d[i,12]:=66;

End;

Для работы программы необходимо организовать ввод массивов констант 4, jk. Это выполняет следующий фрагмент программы.

{Ввод массивов констант}

For i=l to 8 do Begin

Write In (,ik(,,i/jk(i,,),);

Readln (ik[i], jk[i]);

End;

Далее согласно общего алгоритма необходимо указать начальный индекс лучшего маршрута / = -1 и организовать перебор всех 64 маршрутов коня. Последние можно осуществить, реализовав структуру вложенных циклов от / = 3 до 10 и от у = 3 до 10. Затем следует инициализировать шахматную доску, положив для всех ее клеток d,у= 0. Поэтому получим

{Организация перебора всех маршрутов}

1:=-1;

For i=3 to 10 do Begin

For j=3 to 10 do Begin

{Инициализация доски}

For p=3 to 10 do Begin

For t=3 to 10 do d[p,t]:=0;

End;

End;

End;

После этого согласно блок-схеме рис. 1.47 программируем составление маршрута.

n:=l; d[ij]:=l; k:=l;

While k < 8 do {Начало цикла по k}

Begin

i:=i+ik[n]; j:=j+jk[n];

If d[ij]=0 Then k:=k+l Else

Begin

n:=n+l; d[ij]:=n; mi[n]:=i; mj[n]:=j;

Ы;

End;

End; {Конец цикла по k}

If n>l Then

For p=l to n do {Запись лучшего маршрута}

Begin

mil[p]:=mi[p]; mjl[p]:=mj[p]; l:=n;

End;{Конец записи лучшего маршрута}

End;

End; {Конец цикла no j}

End; {Конец цикла по i}

{Вывод лучшего маршрута и его длины}

Goto XY(32,3); Write ('Маршрут коня'); Writeln;

For i=l to n do Begin

For j=l to n do Write ('(',mil[i]',,,mil[j]

End;

Goto XY(31,12); Write ('Длина маршрута', = n:2);

End.

Завершая процесс составления программы, отметим, что для удобства восприятия маршрута выводится последовательность индексов полей шахматной доски, например (5,6) (3,5) (1,6)... . Полностью программу рекомендуем составить студентам.

Рассмотрим несколько задач обработки строк и записей. Необходимо составить список студентов группы, содержащий не более 30 фамилий. Затем вывести его на экран.

Очевидно, что ввод и вывод можно осуществить в одном цикле, что показано на следующей блок-схеме (рис. 4.12). Проверку условия «это фамилия?» осуществим с помощью функции Lenght (фамилия), определяющей длину слова. Если длина равна нулю, фамилия не выведена, а просто нажата клавиша Enter. Программа, реализующая алгоритм, приведена ниже.

Program Spisok; {Ввод списка студентов}

Var

Student: Array 11..30] of string; {Массив строк}

Farn: String (30); {Фамилия студента} i: integer; {Номер строки}

Begin

i:=l;

Repeat

Write ('Введите фамилию или нажмите Enter'); Readln (Fam);

If Length(Fam)=0 Then Break Else

Begin

Student[i]:=Fam; i:=i+l; Writeln (Fam);

End;

Until i>30;

End.

Программу можно было бы сократить, составив ее с применением цикла For — do. Однако в этом случае операции алгоритма / = 1, / = / + 1, / < 30 были бы скрыты в заголовке цикла For / = 1 to 30 do, что менее наглядно, чем это представляет оператор Repeat — Until.

Дано предложение, содержащее не более 80 символов. В предложении имеется несколько слов, разделенных пробелами. Требуется установить число слов и пробелов предложения.

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

Program Pred; {Подсчет слов в предложении}

Var

Р: String (80);

i: integer; {Индекс символа}

k: integer; {Число пробелов}

Begin

Write ('Введите предложение');

Readln (Р); к:=0;

For i=l to Length(P) do

If P[i]=” Then k:=k+1;

Writeln ('Число пробелов',= k:2,'Число символов', = (k+l):2);

End.

В программе значение функции Length определяет длину предложения.

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

Очевидное решение задачи такое. В цикле просматриваем предложение и сравниваем его символы с пробелом. При обнаружении пробела устанавливаем его номер, сдвигаем всю оставшуюся правую часть предложения на одну позицию влево и уменьшаем его длину на единицу. Затем снова возвращаемся к поиску очередного пробела и так действуем до тех пор, пока не исключим все пробелы. Блок-схема решающего алгоритма приведена ниже (рис. 4.13).

Алгоритм удаления пробелов из предложения

Рис. 4.13. Алгоритм удаления пробелов из предложения

Средства языка Turbo Pascal 7.0 позволяют вместе с тем существенно упростить запись программы. Для этого следует воспользоваться функцией обработки строк Pos (Подстрока, Строка), которая определяет номер позиции в строке, с которой начинается подстрока, и функцией Delete (Строка, р,п), которая удаляет из строки, начиная с позиции р, п символов. Фрагмент алгоритма будет таким (рис. 4.14).

Фрагмент алгоритма удаления пробела с использованием

Рис. 4.14. Фрагмент алгоритма удаления пробела с использованием

функций Pos, Delete

На основании двух блок-схем составляем следующую программу.

Program Udal; {Удаление символов из строки}

Var

X: String (80); {Строка}

i,k: integer; {Индексы элементов строки}

n: integer; {Длина строки}

Begin

Write ('Введите строку'); Readln (X);

n:= Length (X);

i:=l;

While i<=n do

Begin

k:=Pos(' ’,x);

If k=0 Then Break;

Else

Begin

Delete (x,k,l); n:=n-l; i:=i+l;

End;

End;

Writeln (x);

End.

В программе выход из цикла по оператору Break осуществляется тогда, когда результат функции Pos(' ',х) равен нулю, т. е. пробелов в предложении нет.

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

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

Фамилия И. О.

Год

рожд.

Курс

Группа

Дом.

адрес

Тел.

Отметка по математике

Отметка по ВТ

Отметка по истории

Рис. 4.15. Структура полей записи о студенте

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

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

Раздел объявлений программы может быть таким.

Program Student; {Формирование записей о студентах}

Stud: record; {Имя переменной типа «запись» - Stud}

Nom: byte; {Номер записи}

Fio: String(35); {Поле - Фамилия Имя Отчество}

God: integer; {Поле — год рождения}

Kours: byte; {Поле — курс }

Group: String (10); {Поле — группа}

Adress: String(35); {Поле — домашний адрес}

Telephone: integer; {Поле — телефон}

Math: byte; {Поле — отметка по математике}

Vt: byte; {Поле — отметка по ВТ}

History: byte; {Поле — отметка по истории}

End;

Var

S: Array fl..40] of Student; {Массив записей}

  • S Math: byte; {Средний балл по математике}
  • S VT: byte; {Средний балл по ВТ}
  • S History: byte; {Средний балл по истории}
  • S Group: byte; {Средний балл по группе} n.i: byte; {Число записей и индекс записи}

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

Begin

Write ('n=', n); Readln (n);

For i=l to n do Begin

Writeln ('Nom'); Readln (S[i].Nom);

Writeln ('Fio'); Readln (S[i].Fio);

Writeln ('God'); Readln (S[i].God);

Writeln ('Kours'); Readln (S[i].Kours);

Writeln ('Group'); Readln (S[i].Group);

Writeln ('Adress'); Readln (S[i].Adress);

Writeln ('Telephone'); Readln (S[i].Telephone);

Writeln ('Math'); Readln (S[i].Math);

Writeln ('Vt'); Readln (S[i].Vt);

Writeln ('History'); Readln (S[i].History);

End;

He следует забывать, что при вводе после окончания формирования очередной записи на клавиатуре необходимо нажимать клавишу Enter.

Фрагмент вычисления средних баллов успеваемости студентов может быть таким.

S_Math:=0;

S_VT:=0;

S_History:=0;

For i=l to n do Begin

S_Math:=S_Math+S[i].Math;

S_VT :=S_VT+S [ i ]. VT;

S_History:=S_History+S[i], History;

End;

S_Math:=S_Math/n;

S_VT:=S_VT/n;

S_History:=S_History/n;

S_Math:=S_Math/n;

S_Group:= (S_Math +S_VT+S_History)/3;

End;

Вывод результатов расчета очевиден.

Writeln ('Результаты расчета');

Writeln ('Ср. балл по математике =', S_Math);

Writeln ('Ср. балл по выч. технике =', S_Vt);

Writeln ('Ср. балл по истории =',S_History);

Writeln ('Ср. балл усп. по группе =',S_Group);

End.

Более удобный способ обращения к полям записи состоит в применении оператора With <переменная типа «запись»> do <опе-раторых Например, при вводе данных после заголовка цикла For i=l to n do можно было бы записать оператор With S[i] do и тогда операторы ввода полей допускалось бы писать как Readln (Nom), Readln (Fio) и т. д. Иными словами, указание на /'-ю переменную массива S[i] и точку можно было бы опускать. Аналогичным образом можно было бы поступить и при обработке массива записей.

 
< Пред   СОДЕРЖАНИЕ     След >