Обработка матриц в Паскале
Матрица — это двумерный массив , каждый элемент которого имеет два индекса: номер строки и номер столбца.
Объявить двумерный массив (матрицу) можно так:
имя : array [ индекс1_нач.. индекс1_кон, индекс2_нач.. индекс2_кон ]
- тип определяет тип элементов массива,
- имя — имя матрицы,
- индекс1_нач..индекс1_кон — диапазон изменения номеров строк,
- индекс2_нач..индекс2_кон — диапазон изменения номеров столбцов матрицы.
var h : array [ 0.. 1 1, 1.. 10 ] of integer;
Описана матрица целых чисел h , состоящая из двенадцати строк и десяти столбцов (строки нумеруются от 0 до 11, столбцы от 1 до 10).
Существует ещё один способ описать матрицы, для этого надо создать новый тип данных :
новый_тип=array [ индекс1_нач.. индекс1_кон ] of тип;
имя : array [ индекс2_нач.. индекс2_кон ] of новый_тип;
новый_тип=array [ список_диапазонов ] of тип;
В данном случае в матрицах a и b есть 10 строк и 30 столбцов, а с — матрица , в которой есть 16 строк и 14 столбцов.
Для обращения к элементу матрицы необходимо указать её имя и в квадратных скобках через запятую номер строки и номер столбца:
имя [ номер_строки, номер_столбца ]
имя [ номер_строки ] [ номер_столбца ]
Например, h[2,4] 1 Или h[2][4]. — элемент матрицы h , находящийся в строке под номером два и столбце под номером четыре.
Для обработки всех элементов матрицы необходимо использовать два цикла . Если матрица обрабатывается построчно, то во внешнем цикле последовательно перебираются строки от первой до последней, затем во внутреннем — все (первый, второй, третий и т. д.) элементы текущей строки. При обработке элементов матрицы по столбцам внешний цикл будет перебирать столбцы, внутренний — строки. На рис. 6.1 представлена блок-схема алгоритма обработки матрицы по строкам, на рис. 6.2 — по столбцам. Здесь i — номер строки, j — номер столбца, N — количество строк, M — количество столбцов матрицы A .
Рассмотрим основные операции , выполняемые над матрицами при решении задач.
6.1 Ввод-вывод матриц
Матрицы, как и массивы, нужно вводить (выводить) поэлементно. Вначале следует ввести размеры матрицы, а затем уже в двойном цикле вводить элементы. Блок-схема ввода элементов матрицы изображена на рис. 6.3.
Вывод можно осуществлять по строкам или по столбцам, но лучше, если элементы располагаются построчно, например,
Алгоритм построчного вывода элементов матрицы приведён на рис. 6.4.
Об описании матриц на языке Паскаль было рассказано в разделе 5.2 главы 5, обращение к элементу матрицы можно осуществить c помощью конструкции
или
.
Рассмотрим реализацию ввода-вывода матриц в консольных приложениях.
Для организации построчного ввода матрицы в двойном цикле по строкам и столбцам можно использовать оператор read .
В этом случае элементы каждой строки матрицы можно разделять символами пробела или табуляции, и только в конце строки нажимать Enter .
Ниже приведён пример консольного приложения ввода-вывода матрицы.
На рис. 6.5 представлены результаты работы программы.
Ввод матрицы также можно организовать с помощью следующего цикла .
Авторы предлагают читателю самостоятельно разобраться, в чём будет отличие ввода матрицы в этом случае.
Для ввода-вывода матриц можно использовать компонент типа TStringGrid, с которым мы познакомились в главе 5.
В качестве примера рассмотрим следующую задачу.
Блок-схема транспонирования матрицы приведена на рис. 6.6. При транспонировании матрицы получается матрица B
.
Рассмотрим частный случай транспонирования матрицы фиксированного размера A(4,3) .
На форме разместим метки Label1 и Label2 со свойствами Caption — Заданная матрица и Транспонированная матрица
, два компонента типа TStringGrid , изменив их свойства так, как показано в табл. 6.1, и кнопку Транспонирование матрицы.
Окно формы приложения представлено на рис. 6.7.
Ниже приведён текст подпрограммы с комментариями, которая будет выполняться, если пользователь щёлкнет по кнопке Транспонирование матрицы.
Транспонирование матрицы на языке Паскаль
ФИО автора: Трофимов Виктор Геннадьевич
Место работы: ГКООУ санаторная школа-интернат №28 г. Ростова-на-Дону
Должность: учитель информатики и ИКТ
Задача: дана матрица K [ X , Y ], значения X и Y вводятся пользователем (не более 10), матрица заполняется случайными целыми числами. Сформировать транспонированную матрицу P , вывести её на экран.
Кроме владения языком программирования, вам потребуются следующие знания: двумерные массивы, циклы, вложенные циклы и небольшое понимание декартовой системы координат.
Для решения этой задачи нам потребуются двумерные массивы, k и p , при этом массив k будет служить массивом-источником матрицы, массив p — получателем.
При работе с двумерными матрицами очень часто программисты путают значения осей x и y , для избегания такой путаницы достаточно представить трансформированную декартову систему координат, где точка 0 будет находиться в левом верхнем углу, ось X — вертикальная, ось Y — горизонтальная. Чёткое понимание подобной модели даст преимущество в написании программы и позволит не путаться между счётчиками цикла i , j .
Декартова система координат:
Система координат для работы с массивами:
Опираясь на систему координат с измененными осями X и Y нам не составит труда проконтролировать работу вложенного цикла (с которым обычно и происходит путаница при работе с двумерными массивами).
Идея проста. Определяем двумерный массив размерностью X , Y , заносим случайные числа от -128 до +127 и следующим же шагом транспонируем матрицу.
Сама программа реализует следующее:
1. Запрашиваем у пользователя значения X и Y
2. Если хоть одно значение больше 10, то присваиваем ему 10.
3. С помощью вложенного цикла заполняем массив k случайными числами.
4. Выводим на экран массив k для контроля.
5. Транспонируем массив, одновременно передавая значения в массив p .
6. Выводим результат на экран.
Ниже привожу блоки программы с пояснением:
program transponirovanie ; // название программы
uses crt ;// библиотека для использования процедур очистки экрана и
// финального ожидания нажатой клавиши
var k : array [1..10, 1..10] of shortint ;// объявление первого массива
p : array [1..10, 1..10] of shortint ;// объявление второго массива
x , y , i , j : byte ;// переменные, нужные нам для ввода
// пользователем размерности массива
// и для счётчиков цикла
Для массивов взяты значения типа shortint , позволяющие указать данные в диапазоне от -128 до +127, целые числа. Для размерности массива и счётчиков цикла достаточно значения типа byte , так как даже в максимальном случае у нас получится всего 10 итераций для любого из циклов.
begin // Начало программы
clrscr ;// Очистка экрана
randomize ;// Активация генератора случайных чисел
В этом блоке вводятся значения с клавиатуры — X и Y , после чего выполняется проверка. Если X или Y больше 10, то им присваивается максимально возможноей значение — 10.
write (‘Введите размер матрицы ( X x Y ), не больше 10 ‘);
if (x > 10) then x := 10;
if ( y > 10) then y := 10;
Заполнение массива. Не забываем, что x — «подправленная» ось нашей системы координат, направлена слева-сверху вниз. Y — горизонтальная ось, увеличение происходит слева-направо.
for i := 1 to x do
for j := 1 to y do
k [ i , j ] := -128 + random (256);// Генератор случайных чисел, который формирует число
// от -128 до +127 (минимальный random (256) может
// вернуть число 0, а максимальный число 255)
gotoxy ( j * 5, 1 + i );// Позиция на экране для вывода значения
writeln ( k [ i , j ]);// Вывод массива для контроля
Здесь выполняется транспонирование матрицы. Всё просто — меняем оси местами, «вращая» массив на 90 градусов по часовой стрелке. Это достигается путём замены счётчиков цикла i (ось x в исходном массиве) на j (ось y в исходном массиве). Вообразите шахматную доску с расставленными фигурами и «поверните» её на девяносто градусов, тогда стоявшие вверху фигуры окажутся расположены на правой линии, второй сверху ряд — на второй справа линии и так далее. В приведенном коде происходит то же самое.
(Труднее будет перевернуть матрицу на заданное количество градусов, допустим, 45 по часовой, или 30 против часовой. Некоторое подобие алгоритма применяется в игре тетрис, а более сложные его формы — практически во всех современных играх или программах, работающих с фото- видеоматериалами).
for i := 1 to x do
for j := 1 to y do
p [ j , i ] := k [ i , j ];
Вывод получившегося транспонированного массива. Формирование позиций на экране для вывода значений происходит путём расчёта ( j * 5, 2 + x + i ), ось y , формируемая формулой 2 + x + i, всегда будет ниже, чем предыдущий вывод исходного массива.
for i := 1 to y do
for j := 1 to x do
gotoxy(j * 5, 2 + x + i);
readkey;// Ожидания нажатия клавиши
end.// Наконец, конец программы!
Трудность алгоритма заключается именно в определении осей массива и умении программиста сориентироваться, переопределив оси X и Y так, чтобы они подходили для обработки в циклах for . Вот и всё 🙂
Транспонирование матрицы.
Дата добавления: 2014-11-28 ; просмотров: 3025 ; Нарушение авторских прав
Транспонированной матрицей называется матрица, у которой столбцы соответствуют строкам исходной квадратной матрицы. При этом элементы главной диагонали исходной и транспонированной матриц, одни и те же.
Операция транспонирования сводится к обмену элементов матрицы, расположенных симметрично главной диагонали.
Фрагмент программы транспонирования матрицы:
for j:=i+1 to n do
Контрольные вопросы:
1. Какие из приведенных описаний одномерных массивов являются неправильными и почему:
а) var dim:array[-1..1] of real;
б) type mas=array[char] of char;
в) type massiv=array[‘A’..’D’];
г) var vector:array[integer] of char;
д) var mm:array[false..true] of char;
е) type ss=array[-20..0] of integer;
ж) type tr=array[1..n,1..m] of real;
pak:array[1..k] of integer;
2. Может ли типом индекса массива быть тип integer или real?
var a:array[1..n] of real;
a) напишите операторы для ввода элементов в массив а;
б) напишите операторы для заполнения массива а случайными числами в интервале от -16 до 73;
в) напишите операторы для вывода элементов массива а в строку, разделяя их двумя пробелами;
г) напишите операторы для вывода элементов массива а в строку, разделяя их таким количеством пробелов, каков порядковый номер выводимого элемента;
д) напишите операторы вывода элементов массива в обратном порядке по n чисел в строке.
4. Чем одномерный массив отличается от двумерного?
5. Почему массивы называются структурами данных с прямым доступом?
6. Приведите примеры программ, где прямой доступ необходим.
7. Установите, какая задача решается в предложенном фрагменте программы. Назовите все операторы и типы данных, использованные в нем, расскажите как они работают:
var u,v,w:array [1..n] of integer;
for j:=n downto 1 do
8. Задан массив . Установите, каким будет значение С после выполнения операторов:
Существенен ли порядок, в котором выбираются значения индексов i и j?
9. Установите, какая задача решается в предложенном фрагменте программы. Назовите все операторы и типы данных, использованные в нем, расскажите как они работают:
for i:=p to q-(p-q+1) div 2 do
10. Установите, какая задача решается в предложенном фрагменте программы. Назовите все операторы и типы данных, использованные в нем, расскажите как они работают:
a[i,j]:=(i div j) * (j div i).
11. Установите, какая задача решается в предложенном фрагменте программы. Назовите все операторы и типы данных, использованные в нем, расскажите как они работают:
for i:=1 to n-1 do
for j:=i+1 to n do
12. Какую задачу решает предложенный фрагмент алгоритма? Определите значение массива А после выполнения следующих операторов при N=3 и :
for i:=1 to n-1 do
for j:=i+1 to n do
13. Какую задачу решает предложенный фрагмент программы? Определите значение массива C после выполнения следующих операторов при N=3, M=2 и :
for i:=1 to n do s:=s+a[i,j];
14. Какую задачу решает предложенный фрагмент программы? Определите значение массива C после выполнения следующих операторов для заданных массивов и
:
15. Какую задачу решает предложенный фрагмент программы? Определите значение массива A после выполнения следующих операторов при N=8, K=2 и А=(4, -3, 5, -2, 3, 10, 9, 0):
for i:=k to n do a[i]:=a[i+1].
16. Какую задачу решает предложенный фрагмент программы? Определите значение массива A после выполнения следующих операторов при M=3, N=5, D=6 и А=(5, 2, -8, 1, -3):
then begin s:=s+a[i];
23. Какую задачу решает предложенный фрагмент программы? Определите значение массива C после выполнения следующих операторов для заданных массивов N=3, и
:
24. Сформулируйте задачу, решаемую в предложенном фрагменте программы, где a[i,j] – элемент массива размерности . Определите значение массива А при N=4, M=5, K=3,
:
for j:=k to m-1 do a[i,j]:=a[i,j+1].
25. Задан одномерный массив А=(7, 5, 4, 6, 3, 2, 1). Какое значение будет выведено в результате выполнения программы:
var a:array[1..7] of integer;
begin write(‘Введите семь элементов массива ‘);
for k:=1 to 7 do read(a[k]);
for k:=1 to 100 do
begin j:=a[i]; a[i]:=i; i:=j; c:=c+i end;
26. Какое значение будет выведено в результате выполнения программы:
var i,k,k1,c : longint;
begin k:=3; k1:=1; c:=80;
for i:=64 to 174 do
begin k1:=-k1; k:=k+k1; c:=c+k*i end;
Задачи
1. Найти сумму всех элементов некоторого двумерного массива и сравнить их с произведением элементов некоторой строки.
Компонентный Паскаль/Транспонирование одномерных матриц
Содержание
Понятие о транспонировании [ править ]
Слово «транспонирование» очень умное, но самом деле ничего заумного в этом нет. Для того, чтобы понять что это такое возьмите лист бумаги, нарисуйте таблицу умножения Пифагора, например 10х5 клеток: по вертикали от 1 до 5, а по горизонтали от 1 до 10. Теперь положите эту таблицу на бок. Если не считать за недостаток, что все цифры теперь лежат на боку, вы только что успешно выполнили транспонирование матрицы. Если матрица небольших размеров, то можно и руками повернуть. А что если в матрице 5 млн на 40 млн элементов? От руки такую матрицу не то, что не напишешь — нет таких листов бумаги нигде в мире.
Пример транспонирования одномерного массива [ править ]
Надо сразу сказать, что в матрицах просто меняя порядок обращения к индексам многомерных массивов можно не прибегая к таким преобразованиям «эмулировать» транспонирование. Но в нашем учебном примере рассмотрим решение «в лоб».
Уже было упоминание о том, что начинать индексацию массивов с нуля, а заканчивать на «размер_массива — 1» «гражданским» непривычно. Поэтому существует небольшая хитрость, которая заключается в том, чтобы обращаться к массивам с «1», а размер массива объявлять «размер_массива+1». Если массив очень большой многомерный, то это не очень хорошая практика, если же одномерный — то вполне приемлемо [1] .
Создание пользовательского типа [ править ]
Для решения поставленной задачи, например, возьмём отрывок из «Трёх законов робототехники» Айзека Азимова. Как вводить, данные в программу, уже было разобрано. Как создать массив, тоже понятно, с той поправкой, что желательно, чтобы он был больше, чем выбираемый отрывок, и обеспечить правильную охрану цикла для ввода и транспонирования. Если считать, что размер отрывка составит десятки мегабайтов, рекурсия тут точно не поможет — никакого стека не хватит. Остаётся только перестановка на месте. Для решения это задачи зададимся несколькими вспомогательными структурами. Одной из них, пусть будет безопасный тип строки:
C помощью записи создаётся новый пользовательский тип TString. Он содержит в себе отдельным полем свою длину, и сам массив текста определён на 1 символ больше, чем степень числа «2» (2049 вместо 2048). Это сделано специально, чтобы можно было индексировать начиная с «1». Кроме того есть поле, означающее максимальную длину массива. Также стоит обратить внимание на то, как изменилась форма определения записи — использована новая привязка POINTER TO («указатель на»). Указатель, как следует из названия «указывает на что-либо». В данном случае — на запись. И такой подход несколько меняет работу с переменными такого типа (POINTER TO).
Инициализация тип TString [ править ]
Поскольку теперь у нас не просто массив литер в кодировке Unicode, а целая запись с полями — прежде чем использовать такую структуру её нужно привести в порядок. Из примеров, которые встречались ранее известно, что переменные без начального присвоения содержат мусор. Ниже приводится текст процедуры, которая как раз подготавливает к использования пользовательский тип TString:
В этой процедуре сразу заметно отличие объявления процедуры от того, что объявлено ранее. Перед именем процедуры в скобках приведён параметр тип «TString». Таким образом происходит привязка этой процедуры к записи. После такого определения можно обратиться к этой процедуре следующим образом:
Запись компактна, и не возникает вопросов по поводу принадлежности процедуры «Init». Процедур «Init» даже в одном модуле может быть определено несколько, если они обладают различной принадлежностью и параметрами. При программировании на типизированных языках процедуры с одинаковым именем, но разными параметрами обладают разными сигнатурами(«подписями»), именно по ним компилятор и различает эти процедуры. Определение процедур с одинаковыми сигнатурами недопустимо.
После имени процедуры следует ключевое слово NEW. Это означает, что для эта процедура вводится в-первые. Записи объединённые с процедурами в КП называются объектами. А процедуры, привязанные к записям (и, автоматически уже объектам) — методами объекта. Поля записей в составе объектов называются свойства объекта (так реализуется объектно-ориентированный подход (ООП) в Компонентном Паскале).
Метод, который производит первоначальную настройку объекта в ООП принято называть инициализацией.
В самой процедуре происходит начальное присвоение полям записи первичных значений, массив литер получает в каждом элементе значение «пробел». Целочисленный цикл перебирает элементы массива с индекса «0» по «2048», т.е. всего 2049 элементов. Но, элемент с индексом «0» в дальнейшем использовать не предполагается.
В целях отладки, чтобы убедиться в правильности процедуры — при начале её работы выводится контрольная строка, которую в конечной программе можно удалить.
Ввод данных [ править ]
Ввод данных уже разбирался, применим его снова в виде метода объекта:
В этом методе опять можно наблюдать привязку к записи типа «TString», не используются никакие сторонние переменные. Заполнение массива будет производиться до тех пор, пока либо не закончится текст, либо не будет исчерпана длина массива. После каждого успешного ввода длина текста наращивается на единицу. Обратите внимание, что индексация позиции вставки текстового массива осуществляется через свойство самого объекта «len_txt».
Вывод текста [ править ]
Вывод текста не является обязательной задачей, но всё-таки сделаем это, чтобы убедиться, что текст действительно будет «развёрнут на месте». Этот же метод будет использован для вывода перевёрнутого текста. Текст метода:
В связи с тем, что литерный массив выводится не полностью, а только та часть, что получила заполнение, пришлось ввести локальную переменную «i». Он позволит выводить массив до тех пор, пока он не станет равным заполнению на вводе.
Разворот текста на месте [ править ]
Разворот массива на месте выполним с помощью дополнительной переменной литерного типа, в качестве промежуточного хранилища элемента литерного массива. Середина введённого текста может быть найдена через целочисленное деление длины ведённого текста пополам. Для этого используется ключевое слово DIV (сокращение от DIVISION, «деление»). В остальном, метод похож на предыдущие.
Точно также в начале метода используется диагностический вывод.
Главная процедура модуля [ править ]
По аналогии с предыдущими программами, эта процедура будет называться «Start». Общий вид процедуры:
Часть кода занято диагностическим выводом, другая вызовом методов переменной, имеющей тип «TString», и здесь тоже всё достаточно прозрачно. Единственная инструкция, требующая пояснения: NEW(txt). «txt» — это переменная, имеющая тип «POINTER TO RECORD» (тип «УКАЗАТЕЛЬ НА ЗАПИСЬ»). Ключевое слово NEW указывает на то, что эта переменная создаётся динамически. Динамическое создание переменных используется очень часто, и использование NEW широко распространено. Если определить переменную «txt» не как динамическую, а как статическую, то размер программы сразу вырастит до примерно 4600 байт — за счёт массива CHAR на 2049 элементов (4098 байт). Без статического определения массива программа занимает порядка 640 байт.
Итоговый текст программы [ править ]
Пример текста модуля ниже.
Ввод и вывод данных [ править ]
Для ввода данных использовать этот текст:
Вывод программы, если всё сделано училось правильно:
Как видно, вместо переводов строк появился символ «0DX». Это символ перевода строки. Результат не совсем такой, как ожидалось. Как работать со строками будет рассмотрено отдельно.






Транспонирование матрицы паскальСсылка на основную публикацию


×
×
Исходная матрица | Транспонированная матрица |