- •1. Постановка задачи:
- •Структура программы на Паскале
- •Классификация типов
- •Стандартные типы данных Логические типы Внутреннее представление
- •Операции
- •Целые типы Внутреннее представление
- •Операции
- •Стандартные функции и процедуры
- •Вещественные типы Внутреннее представление
- •Операции
- •Стандартные функции
- •Символьный тип
- •Порядковые типы
- •Алфавит языка
- •6.2. Идентификаторы
- •6.3. Константы
- •6.4. Выражения
- •6.5. Операции
- •Составной оператор
- •Оператор if выполняется так:
- •Оператор if может иметь сокращенную форму. Её синтаксис:
- •10.1. Процедура
- •10.2. Функция
- •10.3. Формальные и фактические параметры
- •10.3.1. Параметры-значения
- •Динамическая память
- •1. Объявление указателей
- •2. Выделение и освобождение динамической памяти
- •3. Процедуры и функции для работы с динамической памятью
- •Работа с файлами на языке программирования pascal. Типы файлов, команды для работы с файлами, типизированные, нетипизированные и текстовые файлы
- •Работа с файлами в языке Pascal. Файлы прямого доступа.
- •16. Графические возможности языка. Модуль Graph.
- •6.1. Массив
- •6.2. Строка типа string
- •6.3. Asciiz-строка
- •6.4. Запись
- •6.5. Множество
- •6.6. Файл
- •3.1. Алгоритмы обработки массивов
- •3.2. Ввод-вывод элементов одномерного массива
- •3.3. Вычисление суммы элементов массива
- •3.4. Вычисление произведения элементов массива
- •3.5. Поиска максимального элемента в массиве и его номера
- •3.6. Сортировка элементов в массиве
- •3.6.1. Сортировка методом "пузырька"
- •3.6.2. Сортировка выбором
- •3.6.3. Сортировка вставкой
- •3.7. Удаление элемента из массива
- •3.8. Примеры алгоритмов обработки массивов
- •20.Алгоритмы обработки массивов: алгоритмы на двумерных массивах.
- •21.Динамические структуры данных: очередь.
- •Занесение элемента в очередь
- •Извлечение элемента из очереди
- •Занесение элемента в стек
- •Извлечение элемента из стека
- •Абстрактные типы данных
- •Объекты и классы
- •Базовые принципы ооп
- •Пакетирование (инкапсуляция)
- •Наследование
- •Полиморфизм
- •Описание объектного типа
- •Иерархия типов (наследование)
- •Полиморфизм и виртуальные методы
- •Статические методы
- •Виртуальные методы
20.Алгоритмы обработки массивов: алгоритмы на двумерных массивах.
ТИПОВЫЕ АЛГОРИТМЫ ОБРАБОТКИ ДВУМЕРНЫХ МАССИВОВ
• Обработка всего массива.
• Обработка отдельно по строкам и столбцам.
• Обработка относительно диагоналей.
Обработка всего массива
Типовой алгоритм |
Программная реализация |
Заполнение |
... for i:=1 to n do for j:=1 to m do readln (x[i,j]); ... |
Вывод |
... for i:=1 to n do begin for j:=1 to m do write (x[i,j], ' '); writeln; end; ... |
Сумма, произведение |
... s:=0; p:=1; for i:=1 to n do for j:=1 to m do begin s:=s+x[i,j]; p:=p*x[i,j]; end; writeln (s, p); ... |
Максимальный (минимальный) элемент |
... max:=x[1,1]; min:=x[1,1]; for i:=1 to n do for j:=1 to m do begin if x[i,j]>max then max:=x[i,j]; if x[i,j]<min then min:=x[i,j]; end; writeln (max, min); ... |
Выбор по условию |
... for i:=1 to n do for j:=1 to m do if {условие} then {действие} ... |
Типовые алгоритмы обработки двумерного массива отдельно по строкам
Типовой алгоритм |
Программная реализация |
Сумма |
... for i:=1 to n do s[i]:=0; for i:=1 to n do for j:=1 to m do s[i]:=s[i]+x[i,j]; for i:=1 to n do write (s[i]); ... |
Произведение |
... for i:=1 to n do p[i]:=1; for i:=1 to n do for j:=1 to m do p[i]:=p[i]*x[i,j]; for i:=1 to n do write (p[i]); … |
Максимальный (минимальный) элемент |
... for i:=1 to n do begin max[i]:=x[i,1]; min[i]:=x[i,1]; end; for i:=1 to n do for j:=1 to m do begin if x[i,j]>max[i] then max[i]:=x[i,j]; if x[i,j]<min[i] then min[i]:=x[i,j]; end; for i:=1 to n do write (max[i]); writeln; for i:=1 to n do write (min[i]); ... |
Выбор по условию |
... for i:=1 to n do begin rez[i]:=0; end; for i:=1 to n do for j:=1 to m do if {условие} then {rez[i]:=...}; for i:=1 to n do write (rez[i]); ... |
Типовые алгоритмы обработки двумерного массива отдельно по столбцам
Типовой алгоритм |
Программная реализация |
Сумма |
... for j:=1 to m do s[j]:=0; for j:=1 to m do for i:=1 to n do s[j]:=s[j]+x[i,j]; for j:=1 to m do write (s[j]); ... |
Произведение |
… for j:=1 to m do p[j]:=1; for j:=1 to m do for i:=1 to n do p[j]:=p[j]*x[i,j]; for j:=1 to m do write (p[j]); ... |
Максимальный (минимальный) элемент |
... for j:=1 to m do begin max[j]:=x[i,1]; min[j]:=x[i,1]; end; for j:=1 to m do for i:=1 to n do begin if x[i,j]>max[j] then max[j]:=x[i,j] if x[i,j]<min[j] then min[j]:=x[i,j] end; for j:=1 to m do write (max[j]); writeln; for j:=1 to m do write (min[j]); ... |
Выбор по условию |
... for j:=1 to m do rez[j]:=0; for j:=1 to m do for i:=1 to n do if {усл.} then {rez[i]:=...}; for j:=1 to m do write (rez[j]); … |
Обработка двумерных массивов
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Рассмотрим типовые задачи обработки двумерных массивов с использованием вложенных циклов. Задача.
Т
Составить
программу подсчета суммы и произведения
элементов двумерного массива
вещественных чисел.
program matr; uses crt; var a:array [1...10, 1...10] of real; i, j, n, m: integer; s,p :real; begin clrscr; writeln(‘ Введите n<=10 , m<=10 ’); readln (n,m); writeln(‘ Введите элементы массива по строкам ’); for i:=1 to n do for j:=1 to m do readln(a[i, j]); s:=0; p:=1; { поиск суммы и произведения } for i:=1 to n do for j:=1 to m do begin s:=s + a[i,j]; p:=p * a[i,j]; end; writeln(‘ Сумма элементов s=’,s:8:3); writeln(‘ Произведение элементов p=’,p:8:3); readln; end. Задача. Задана квадратная матрица целых чисел. Составить программу подсчета суммы элементов, расположенных над главной диагональю. Таблица идентификаторов
program matr_1; uses crt; var a:array [1..10, 1..10] of real; i, j, n, m : integer; s,p : real; begin clrscr; writeln(‘ Введите n<=10 , m<=10 ’); readln (n,m); writeln(‘ Введите элементы массива по строкам ’); for i:=1 to n do for j:=1 to m do readln(a[i,j]); for i:=1 to 3 do for j:=i +1 to 3 do s:=s+a[i,j]; writeln('Сумма элементов s=', s); readln; end. Для ввода элементов массива используются вложенные циклы с указанием номера вводимого элемента. Для поиска суммы элементов над главной диагональю во внутреннем цикле задан закон изменения параметра внутреннего цикла: j:=i+1. Задача. Задана целочисленная квадратная матрица. Определить является ли она симметричной относительно главной диагонали. Таблица идентификаторов
program matr_2; uses crt; var a : array [1..10, 1..10] of integer; i, j, n, f : integer; begin clrscr; writeln(‘ Введите n<=10 ’); readln (n,m); writeln(‘ Введите элементы массива по строкам ’); for i:=1 to n do for j:=1 to n do readln(a[i,j]); f:=0 for i:=1 to n do for j:=i to n do if a[i,j]<>a[j,i] then f:=1; if f=0 then writeln(‘ матрица симметрична’) else writeln (‘матрица не симметрична’); readln; end. При решении этой задачи сравниваются элементы расположенные над главной диагональю ( a[ i,j ] ) с элементами, расположенными под главной диагональю ( a[ j,i ] ) .
Задача. Задана матрица вещественных чисел. Образовать одномерный массив, где каждый j – й элемент равен произведению элементов j-ого столбца двумерного массива.
Таблица идентификаторов
programmatr_3; uses crt; var a: array [1...10, 1...10] of integer; b: array [ 1..10 ] of integer; i, j, n, f : integer; begin clrscr; writeln(‘ Введите n<=10 , m<=10 ’); readln (n,m); writeln(‘ Введите элементы массива по строкам ’); for i:=1 to n do for j:=1 to m do readln (a[i, j]); writeln(‘ Исходная матрица ’); for i:=1 to n do begin for j:= 1 to n do write( a[I,j] , ‘ ‘); writeln; end; writeln(‘ Образованный одномерный массив ’); for j:=1 to m do begin b[ j ]:=1; { накапливается произведение элементов j столбца } for i:=1 to n do b[ j ]:= b[ j ] * a[ i, j ]; write( b[ j] , ‘ ‘); end; readln; end. Задача. Задана целочисленная матрица a(m*n). Упорядочить элементы каждой строки по возрастанию.
Таблица идентификаторов
program mart_4; uses crt; var a: array[1...10, 1...10] of integer; i,j,n,f : integer; begin clrscr; writeln(‘ Введите n<=10 , m<=10 ’); readln (n,m); writeln(‘ Введите элементы массива по строкам ’); for i:=1 to n do for j:=1 to m do readln(a[i, j]); writeln(‘ Исходная матрица ’); for i:=1 to n do begin for j:=1 to n do write(a[I,j],‘ ‘); writeln; end; { переход от строки к строке } for i:=1 to n do { сортировка i-ой строки } repeat f:=0; for j:=1to m-1 do if a[i,j]>a[i,j+1] then begin p:=a[i,j]; a[i,j]=a[i,j+1]; a[i,j+1]:=p; f:=1; end; untilf=0; writeln(‘ Преобразованная матрица ’); for i:=1 to n do begin for j:= 1 to n do write( a[I,j] , ‘ ‘); writeln; end; readln; end. f =0 – признак того, что все элементы данной строки упорядочены. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Задача.
Составить программу нахождения максимального среди элементов двумерного массива вещественных чисел. Определить номер строки и номер столбца, на пересечении которых был найден максимальный элемент.
Таблица идентификаторов.
№ |
Наименование переменной |
Обозначения в программе |
1 |
Имя двумерного массива |
a |
2 |
Количество строк |
n |
3 |
Количество столбцов |
m |
4 |
Индексы массива |
I,j |
5 |
Значение максимального элемента |
max |
6 |
Номер строки, где найден максимальный элемент |
kmax |
7 |
Номер столбца, где найден максимальный элемент |
lmax |
Листинг программы.
program lab6;
uses
crt;
var
a: array [1...10, 1...10] of real;
i, j, n, m , kmax , lmax: integer;
max :real;
begin
clrscr;
writeln(‘ Введите n<=10 , m<=10 ’);
readln(n,m);
writeln(‘ Введите элементы массива по строкам ’);
for i:=1 to n do
for j:=1 to m do
readln(a[i,j]);
{за максимальный принимается элемент a11 }
max:=a[1,1];
kmax:=1;
lmax:=1;
for i:=1 to n do
for j:=1 to m do
if a[i,j]>max then
begin
max:=a[i,j];
kmax:=i;
lmax:=j;
end;
writeln(‘max=’, max:8:3);
writeln(‘строка - ‘, kmax,’ столбец - ’,lmax);
readln; end.