Сёмов Основы разработки алгоритмов и программ. Учебное пособие для студентов факультета дистанционных форм обучения миигаик москва 2020 2 Рецензенты

• Название: Учебное пособие для студентов факультета дистанционных форм обучения миигаик москва 2020 2 Рецензенты
• Дата: 15.12.2022
• Размер: 391.34 Kb.
• Имя файла: Сёмов Основы разработки алгоритмов и программ.pdf
• Тип: Учебное пособие; #846031
• страница: 5 из 6

Program Test_Max;
Var k, M : integer;{M – количество элементов в обрабатываемом массиве }
S : real; {S – переменная для хранения максимального элемента массива}
A : array[1..100] of real ;
Begin
Write('Введите М <= 100 –количество элементов в вашем массиве');
ReadLn(M);
S := 0;
for k := 1 to M do
Begin
ReadLn(a[k]);
if (k = 1) or (a[k] > S) then
S := a[k];
End;
WriteLn('Наибол. элем. массива А= ', S);
End.
Замечание. Если в условном операторе заменить отношение a [ k ] > S на a [ k ] < S, то получится алгоритм определения наименьшего элемента массива.
Два предыдущих алгоритма являются типичными из простейших алгоритмов обработки одномерных массивов.

64
3.
Найти количество положительных элементов массива А=(1.1, -2.2, 6, 4, -5);
Блок-схема алгоритма представлена на Рис. 8
A [ k ] > 0
A [ k ]
S : = 0
Вывод ' Введите M <= 100 '
Ввод M
k : = 1 , M
'Количество = ' , S
false tru e
S : = S+1
Рис.8 Блок-схема алгоритма

65
Ниже приведена программа, составленная для рассматриваемого алгоритма.
Program Test_Plus;
Var
k, M : integer;
S : integer; {S – переменная для хранения количества положительных элементов массива}
A : array[1..100] of real ;
Begin
Write('Введите М <= 100 –количество элементов в вашем массиве');
ReadLn(M);
S := 0;
for k := 1 to M do
Begin
ReadLn(a[k]);
if (a[k] > 0 then S := S + 1;
End;
WriteLn(‘Кол-во полож. элем.= ', S);
End.
Замечание. Если в условном операторе заменить отношение a [ k ] > 0 на a [ k ] < 0, то получится алгоритм определения количества отрицательных элементов массива. Если условие заменить на (a [ k ] > b ) and (a [ k ] <с), то получится алгоритм определения количества элементов, значения которых находятся в интервале от b до c.

66
4. Сформировать массив В, записав в него ненулевые элементы массива А. Вывести
на строку консоли массив В.
Ниже приведена программа, составленная для рассматриваемого алгоритма.
Program Test_Compress;
Var
k, M, s : integer; {k-параметр циклов, M –количество элементов в массиве А,
s - количество элементов в массиве В }
A, B : array[1..100] of real ;
Begin
Write('Введите М <= 100 –количество элементов в вашем массиве');
ReadLn(M);
s := 0;
for k := 1 to M do
Begin
Write('Введите очередной элемент вашего массива ');
ReadLn(a[k]);
if (a[k] > 0) then
begin
s := s + 1;
b [ s ] := a [ k ];
end;
End;
Writeln ('количество элементов в новом массиве = ', s );
Writeln (' элементы нового массива ');
for k := 1 to s do
Write( b[k]:6:2, ‘ ‘); {Значения элементов нового массива отделяются друг от друга тремя пробелами}
End.

67
5.Выполнить сортировку массива А по возрастанию.
Блок-схема алгоритма представлена на Рис. 10.
R : = A[k]
A [ n ] <= A[k]
k : = 1 , M - 1
k : = 1 , M
n : = k + 1 , M
Вывод ' Массив по сле сортир овки '
Вывод ' Введите M <= 100 '
Ввод M
A[k] : = A[n ]
A[n ] := R
Вывод ' Введите элементы масс. '
k : = 1 , M
Ввод A [ k ]
Вывод А [ k ]
false true
Рис.10 Блок-схема алгоритма

68
Ниже приведена программа, составленная для рассматриваемого алгоритма.
Program Test_Sort;
Var
k, M, s : integer
A, B
: array[1..100] of real ;
r : real;
Begin
Write('Введите М <= 100 –количество элементов в вашем массиве');
ReadLn(M);
Writeln(‘Введите элементы массива ’);
for k := 1 to M do
begin
Write('Введите очередной элемент вашего массива ');
ReadLn(a[k]);
end;
for k := 1 to M – 1 do
{Фиксируем К-ую позицию}
for n := k + 1 to M do
{Перебираем элементы с К+1-го по М-ый }
Begin { каждого n-го сравниваем с К-м}
if (a[ n ] < a[ k ]) then { меняем их местами}
begin
r := a [ k ];
a[ k ] := a [ n ];
a [ n ] := r ;
end;
End;
WriteLn(‘Массив после сортировки по возрастанию’);
for k := 1 to M do
Write( a[k]:6:2, ‘ ‘); {Значения элементов отсортированного массива выводятся в одну строку и отделяются друг от друга тремя пробелами}
End.

69
5.5. Примеры алгоритмов и программ обработки двумерных массивов
Прежде всего, следует заметить, что алгоритмы вычисления суммы, произведения или количества элементов массива, удовлетворяющих некоторому условию, алгоритмы поиска наибольшего и наименьшего значений двумерного массива аналогичны рассмотренным выше алгоритмам для одномерных массивов.
Также обратим ваше внимание на правильное объявление двумерных статических
массивов (матриц=таблиц) в секции объявлений Паскаль программы на примере конкретной задачи.
Но сначала обсудим еще раз понятие двумерного массива.
Прямоугольную таблицу чисел в математике называют матрицей, в программировании –
двумерным массивом. Каждое число массива хранится в отдельной ячейке памяти ЭВМ. Этот набор ячеек удобно представлять себе в виде таблицы:
1 2
3
…
1 2
…
Вся таблица ячеек имеет имя. Имя массива. Например, А. Каждая ячейка памяти в массиве имеет имя A[i, j], где i – имя ячейки памяти, в которой лежит номер строки, а j – имя ячейки памяти, в которой лежит номер столбца таблицы ячеек А. Указывая в программе имя ячейки массива в левой части оператора присваивания, мы даем команду записать туда число, а если – в правой части, то извлечь из ячейки число и вставить его в формулу вычисления.
Строки массива в программе нумеруются, как правило, как в математике от 1. Столбцы тоже.
При объявлении имени массива в секции var программы, транслятор выделяет таблицу ячеек памяти для хранения чисел – значений элементов массива. Чтобы выбрать последовательно все ячейки памяти массива для обработки в программе используют вложенные циклы. Внешний цикл for назначает конкретное число для i – номера строки, а внутренний цикл for при фиксированном i перебирает вся значения для j – номера столбца.
В качестве примера, приведем фрагмент программы, который вычисляет сумму элементов массива А, состоящего из 10 строк и 15 столбцов.
s:=0; {обнуление сумматора}
for i:=1 to 10 do {заголовок внешнего цикла}
for j:=1 to 15 do {заголовок внутреннего цикла}
s:=s+A[i,j]; {тело внутреннего цикла}

70
А теперь приведем и прокомментируем текст программы, которая вычисляет сумму элементов матрицы А, состоящей из mf строк и nf столбцов. Значения для mf и nf вводятся как исходные данные, причем известно, что максимальное возможное значение mf равно 20, а максимальное возможное значение nf равно 30.
Секция описаний переменных и массивов для этой программы и организация ввода
значений этих массивов должны стать образцом для ваших программ с двумерными и
одномерными массивами.
Program P1;
сonst mmax = 20; { максимально возможное количество строк в массиве}
nmax = 30; {максимально возможное количество столбцов в массиве}
type mas2 = array[1..mmax,1..nmax] of real; {определили имя структуры данных и что она из себя представляет: количество строк и количество столбцов в ней; количество ячеек памяти = mmax*nmax, в каждой можно хранить число с дробной частью (real)}
var A : mas2; {транслятор выделяет «таблицу» ячеек памяти для хранения значений элементов массива A[i,j]}
i, j : integer; {параметры циклов for}
mf, nf : integer; {фактическое количество строк и столбцов в массиве (матрице). Эти два числа программа введет с консоли в режиме диалога с пользователем }
s : real; {ячейка, в которую программа будет накапливать сумму}
begin
{введем mf и nf}
Write('Введите количество строк в вашей матрице ');
Readln( mf);
Write('Введите количество столбцов в вашей матрице ');
Readln( mf);
{Введем значения элементов матрицы (массива) из строк консоли. В каждую строку консоли вводим значения элементов одной строки матрицы через пробел. После ввода значения последнего элемента строки матрицы нажимаем клавишу “ Enter”}
for i:=1 to mf do
begin

71
for j:=1 to nf do
Read (A[i,j]);
Readln; {Чтение кода конца строки. Переход к новой строке ввода}
end;
s:=0;
for i:=1 to mf do
for j:=1 to nf do
s:=s+A[i,j];
Writeln('Сумма элементов массива А= ', s);
end;
Приведем еще три типичных алгоритма и программы работы с матрицами. Внимательно их изучите. Но заметьте, что для упрощения, ввод данных в этих программах сделан не так как в предыдущей программе (без mf и nf ). Он хуже. Объясните почему.
1. Рассмотрим алгоритм транспонирования матрицы. Задана матрица А. Определить
элементы матрицы B = A
T
.
По определению элемент матрицы В определяется формулой b
k, r
= a
r, k.
(1-ая строка А становится 1-ым столбцом В, 2-ая строка А – 2-ым стобцом В и так далее)
На Рис.11 изображена блок-схема алгоритма.

72
Вывод код а ко нца стр оки b [ k , r ] : = a [ r , k ]
n : = 3 ; m : = 4:
r : = 1 , n
Ввод a [ r , k ]
k : = 1 , m
Ввод код а ко нца стр оки k : = 1 , m r : = 1 , n
Вывод b [ k , r ]
Рис.11 Блок-схема алгоритма

73
Запишем по блок-схеме программу.
Program Trans_Matrix;
Const n = 3;
m = 4;
Type matr_nxm = array[1..n,1..m] of real; {}
matr_mxn = array[1..m, 1..n] of real; {}
Var A : matr_nxm;
B : matr_mxn;
r, k : integer;
Begin
Writeln(
'Введите элементы двумерного массива (матрицы =
таблицы) из '
);
Writeln(
'трех строк и четырех столбцов. Элементы строки вводите в строку консоли через пробел.'
);
Writeln(
После ввода последнего элемента строки '
);
Writeln(
' нажмите клавишу «Ввод» = «Enter»'
);
for r := 1 to n do
begin
for k := 1 to m do {читает r-ую строку матрицы из одной строки консоли}
begin
Read(a[r, k]);
b[k, r] := a[r, k];
end;
Readln; {Чтение кода конца строки. Переход к новой строке ввода}
end;
for k := 1 to m do
begin
for r := 1 to n do {Цикл выводит строку матрицы на одну строку экрана}
Write(b[k, r]);
writeln; {Переход к новой строке вывода}
end;
End.

74 2. Рассмотрим алгоритм сложения двух матриц. Даны матрицы А и В. Определить
матрицу С = А + В.
Правило сложения матриц определяется формулой с
r, k
=
a
r, k
+ b
r, k. ,
где r и k
–
соответственно номер строки и столбца в каждой из матриц (сложение элементов матриц,
стоящих в одинаковых позициях)
На Рис.12 представлена блок-схема алгоритма.
n := 3; m := 4 :
r : = 1 , n
Вывод кода конца строк и k : = 1 , m
Ввод a [ r , k ] , b [ r ,k ]
c [ r , k ] : = a [ r , k ] + b [ r , k ]
Вывод c [ r , k ]
r : = 1 , n k : = 1 , m
Рис.12 Блок-схема алгоритма

75
Запишем по блок-схеме программу.
Program Add_Matrix;
Const
n = 3;
m = 4;
Type
matr_nxm = array[1..n,1..m] of real;
Var
A, B, C : matr_nxm;
r, k : integer;
Begin
for r := 1 to n do
for k := 1 to m do
begin
Readln(a[r, k], b[r, k]);
c[r, k] := a[r, k] + b[r,k];
end;
for r := 1 to m do
begin
for k := 1 to n do
Writeln(c[r, k]);
writeln;
end;
End.

76
3.
Рассмотрим алгоритм произведения двух матриц ( Рис.13).
Заданы матрицы А и В .Определить матрицу С = А * В. Элемент матрицы С
стоящий в k-ой строке и в r-ом столбце вычисляется как скалярное произведение k-ой строки
матрицы А(как вектора) на r-ый столбец матрицы В (как вектор).
Чтобы не усложнять понимание алгоритма, укажем только ту часть алгоритма, где выполняется перемножение матриц. Ввод исходных матриц и вывод матрицы результата обозначим кратко.
j : = 1 , m
Ввод матрицы А
Ввод матрицы Б
Вывод м атрицы С
k : = 1 , n r : = 1 , s
C [ k , r ] : = 0
c [ k , r ] : = c [ k , r ] + a [ k , j ] * b [ j , r ]
Рис.13 Блок-схема алгоритма

77
Программа имеет вид.
Program Mult_Matrix;
Const
n = 3;
m = 4;
s = 2;
Type
matr_nxm = array1..n,1..m] of real;
matr_mxs = array[1..m,1..s] of real;
matr_nxs = array[1..n,1..s] of real;
Var
A : matr_nxm;
B : matr_mxs;
C : matr_nxs;
r, k, j : integer;
Begin
{Здесь вводятся исходные матрицы A и B}
for k := 1 to n do
for r := 1 to s do
begin
c[k, r] := 0;
for j := 1 to m do
c[k, r] := c[k, r] + a[k, j]*b[j, r];
end;
{Здесь выводится результирующая матрица С}
End.

78
6. Работа со строковыми переменными
6.1. Строковые переменные
Строковый тип данных определяет множество символьных цепочек произвольной длины
(от нуля символов до заданного их числа). Для определения строкового типа используется зарезервированное слово STRING, вслед за которым в квадратных скобках может быть указана максимальная длина строки.
Type
Line = string [80];
Var
MyLine : Line;
В приведенном примере переменная MyLine в качестве своего значения может иметь любую последовательность символов произвольной длины в пределах от 0 до 80 символов.
Указание максимальной длины для строки может быть опущено, в этом случае подразумевается число 255. Такая длина является максимально возможной для строковых типов.
6.2. Операции со строковыми переменными
Значения строковой переменной может быть присвоено оператором присваивания или введено оператором ввода.
Для строк определена операция конкатенации («+»), например:
MyLine := ‘Строка’;
MyLine := MyLine + ‘стала длиннее’
Значением переменной MyLine будет строка ‘Строка стала длиннее’
Важнейшее отличие строк от обычных символьных массивов заключается в том, что строки могут динамически изменять свою длину.
В случае присваивания строковой переменной строкового выражения с длиной,
большей, чем максимально допустимая для данной переменной, происходит отбрасывание последних символов выражения до максимальной длины строки.
Для описания строковой переменной длиной N отводится N+1 байтов памяти, из которых
N байтов предназначены для хранения символов строки, а один байт – для значения текущей длины этой строки. Для определения текущей длины строки, используется стандартная функция LENGTH, единственным параметром которой является выражение строкового типа.
Эта функция возвращает целое значение, равное длине строки.

79
Кроме операции конкатенации, над значениями строковых типов определены операции сравнения: <, <=, >, >=, =, <>.
Строки сравнивают по первой паре несовпадающих символов. Чей символ меньше
(раньше в кодировочной таблице (в алфавите)) та строка меньше. Если у двух строк имеющиеся пары символов совпадают, но одна строка короче другой, то она считается меньше.
Приведем примеры:
‘abce’ < ‘abcx’ ,так как у первой пары несовпадающих символов e < x (стоит в алфавите раньше);
‘abce’ > ‘abc’, так как имеющиеся пары символов совпадают, но 2-ая строка короче.
Элементы строки нумеруются целыми числами, начиная с единицы. Доступ к отдельным элементам строк производится аналогично доступу к элементам одномерного массива: после имени строковой переменной необходимо в квадратных скобках указать выражение целого типа, обозначающее номер элемента строки. Ниже приведенная программа формирует строку из заглавных букв латинского алфавита.
Var Str : string[26]; I : integer;
Begin
Str :=’’;
For I := 1 to 26 do
Str := Str + Chr (Ord (‘A’) + I – 1);
WriteLn(Str);
End.
Поясним программу. Встроенная функция Ord (‘A’) возвращает код(номер) символа А в кодировочной таблице (в алфавите ЭВМ). Номер каждой последующей буквы в кодировочной таблице (алфавите ЭВМ) на 1 больше. Встроенная функция Chr (Ord (‘A’) + I – 1) по вычисленному для неё номеру возвращает соответствующий символ алфавита, который заносится очередным символом в строку Str.
Кроме стандартной функции LENGTH, в ТП имеется несколько процедур и функций,
работающих со строками.
1. Concat (s1 [,s2, …, sn ] : string) : string;
Эта функция выполняет слияние строк-параметров, которых может быть произвольное количество. Каждый параметр является выражением строкового типа. Если длина результирующей строки превышает 255 символов, то она усекается до 255 символов. Данная функция эквивалентна операции конкатенации и работает немного эффективнее, чем эта операция.

80 2.