Foreversoft.ru

IT Справочник
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Возведение матрицы в степень паскаль

Возведение матрицы в степень паскаль

Решение практических задач на Паскале. Выпуск 6

Возведение матрицы в целочисленную степень

Преамбула

На нашем форуме (http://www.yourpascal.com/viewforum.php?f=6) был задан вопрос о возведении матрицы в степень в неподходящем для этого месте «нужно напечатать период дроби (на паскале)«. Отвечу в рассылке, в которой давно уже ничего не писал. Увы! Времени очень мало

В этом выпуске я представлю способ решения задачи с использованием рекурсии, так как давно искал повод для этого :)). Вот и пришло время .

Сейчас будет предложен вариант решения, в котором ранг матрицы фиксирован. Он задается константой max в модуле uMatrics . Если Вам захочется изменить ранг матрицы, то нужно изменить значение константы и заново откомпилировать программу. Это не очень удобно и в Delphi для решения такой проблемы существуют динамические массивы (которых в Паскале нет :(( ).

Но если нельзя, но хочется, то добрый старый Паскаль позволяет сделать все . Правда, для этого матрицу следует расположить в динамической памяти компьютера и работать с ней с помощью указателя. Чтобы было легче понять более сложный вариант, я и в этот раз буду размещать матрицу в динамической памяти. Это вовсе не обязательно. Можно обойтись «традиционными» двумерными массивами, объявленными в разделе VAR программы. Но используя указатели на массивы, размещенные в динамической памяти, позволяет использовать функции, а не процедуры. А это тоже плюс

Если описанный здесь способ покажется сложным, то напишите мне — я опишу и тот, более простой, способ решения с «обычными» массивами-матрицами.

Краткое описание

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

Достоинство метода рекурсий в том, что код получается маленький (и, вернее, он гусарский). Недостаток в том, что неэффективно используется память и при возведении в большую степень может не хватить стека. Тогда стек нужно увеличить за счет кучи. Как это делается, можно посмотреть в стандартной справке, если набрать $M и вызвать контекстную помощь, нажав сочетание .

Замечу, что испытания моей программы показали: переполнение стека наблюдается при возведении матрицы в степень больше 650. А для меньших степеней гораздо вероятнее получить ошибку переполнения. Она возникает, когда в переменную типа Real делается попытка записать значение больше допустимого.

Сначала приведу исходный код программы, а потом дам пояснения. Хотите — читайте .

Исходный код программы

Все основное находится в модуле uMatrics . Он показан в листинге 1.

Для тестирования используется программа Solve006.pas , текст которой приведен в листинге 2.

Пояснения

Как отмечено вначале, здесь использован самый дубовый прямой метод: матрица каждый раз умножается сама на себя столько раз, в какую степень хотим возвести ее. По определению: A 0 = E; A 1 = А; A N = A N-1 ·A. Здесь E — единичная матрица.

Читать еще:  Типы ошибок c

Расчет производится по формуле: ; где C, A и B — матрицы. — означает суммирование по индексу k от 1 до max. При этом число строк в матрице A должно быть равно числу столбцов в матрице . Следовательно, возводить в некоторую степень можно только квадратные матрицы, число столбцов в которых равно числу строк.

Краткое описание модуля uMatrix

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

В разделе объявлений модуля «объявляются» новые типы переменных:

  1. TMatrics = array [1..max, 1..max] of Real; — двумерный массив, то есть, матрица ранга max,
  2. PMatrix = ^TMatrix; — указатель на двумерный массив. Благодаря такой переменной программа будет знать о структуре массива-матрицы, размешенной в динамической памяти. Это позволит обращаться к его элементам по их индексам.

В модуле созданы следующие подпрограммы:

  1. function NewMatrix: PMatrix; — размещает в динамической памяти ЭВМ массив и возвращает указатель на него. Очень простая функция. Заключается просто в вызове «стандартной» процедуры New. Легко обойтись без нее. Но с этой функцией код программы читается легче.
  2. function PowMatrix(Source: PMatrix; pow: Integer): PMatrix; — самая главная. Она организует возведение матрицы, указатель на который передан ее в качестве первого параметра Source, в степень pow. Рекурсия происходит в строках

p:=MulMatrix(Source, PowMatrix(Source, Pow-1));
По-моему, подпрограмма простая

  • procedure ShowMatrix(matrix: PMatrix; Dest: String; Size, Digs: Byte; mes: String); — выводит содержимое матрицы matrixна экран, если параметр Dest пустой, или в файл. Если файл с заданным именем существует, то информация дописывается в конец этого файла. Параметры Size , Digsпредназначены для форматирования вывода. Сообщение mesможно добавить перед выводом матрицы.
  • procedure AutoFillMatrix(var Matrix: PMatrix); — подпрограмма автоматического заполнения матрицы. Она же проверяет, была ли уже создана матрица? Если нет, в этом случае указатель Matrixравен nil, то матрица инициализируется с помощью функции NewMatrix. Если захотите заполнить матрицу вводя значения элементов с клавиатуры, то лучше написать свою процедуру.
  • function MulMatrix(source1, source2: PMatrix): PMatrix; — выполняет умножение матрицы source1 на матрицу source2.
  • function UnitaryMatrix: PMatrix; — генерирует единичную матрицу. Все элементы такой матрицы равны нулю, кроме тех, что расположены на главной диагонали. Они равны единице.
  • При работе с динамической памятью могут возникнуть две неприятности:

    • система может не выделить блок нужного Вам размера. Если Вы запускаете программу под Windows, то это скорее всего произойдет, когда попытаетесь разместить матрицу, занимающую в памяти больше 64К. Паскаль — это ДОСовская программа. Она не умеет работать с большими блоками. (Хотя справедливости ради замечу, что Borland Pascal может. Я описывал это в одном из выпусков рассылки по Турбо Паскалю)
    • в предложенном простом варианте в динамической памяти могут остаться лишние массивы. Можно было бы и не делать их, точнее, своевременно удалять ненужные. Но тогда каждая из подпрограмм модуля была бы чуть сложнее. Я решил сделать так:
      • в начале работы программы я «запоминаю» вызовом самый «верхний» адрес в куче вызовом Mark(varForHeapRelease) в исполняемом блоке модуля;
      • когда программа завершает работу, нужно вызвать Release(varForHeapRelease). И я не хочу объяснять это каждому встречному и поперечному. Я использую тот факт, что у Паскаля есть процедура, которая вызывается независимо от Вашего желания. Я подменил ее своею, которая имеет такой код:
        procedure FreeAllMemory; far;
        begin
        Release(varForHeapRelease);
        ExitProc:=SaveExit;
        end;

        Она сначала освобождает память от запомненного уровня до самого верха, а потом «вспоминает» стандрантую процедуру выхода ( ExitProc:=SaveExit). В переменной SaveExit для этого перед установкой своей процедуры ( ExitProc:=@FreeAllMemory;) я запомнил адрес стандартной ( SaveExit:=ExitProc;) в исполняемом блоке модуля.
      • КОНЕЧНО, это способ нельзя признать удачным и абсолютно надежным, но до изобретения объектов (или, по крайней мере, до их использования) приходится мириться с недостатками

    Описание тестирующей программы

    Программа простая. Сначала определена переменная типа PMatrix, указатель на двумерный массив. Затем вызывается процедура автоматического заполнения матрицы. Если хотите, можете написать другую процедуру, которая значение элементов будет считывать с клавиатуры. Затем все просто:

    • сначала записываем содержимое исходной матрицы в файл;
    • возводим матрицу во вторую степень;
    • в тот же файл записываем матрицу после возведения в степень.

    В результате должен получиться файл с содержимым, показанным ниже

    Тестовый пример

    Это результаты работы программы: содержимое файла test.txt

    Заключительное замечание (реклама объектно-ориентированного программирования)

    Недостатком предложенного метода является то, что пользователь может вызвать некоторые из подпрограмм с неверными параметрами. В худшем случае ошибок времени выполнения может и не произойти. Тогда человек будет думать, что расчет выполнен правильно. Избавиться от этого недостатка можно только с помощью объектов. Там можно и удобный интерфейс предоставить и ошибки легко отслеживать. Добавьте еще отмеченные проблемы с использованием памяти

    Исходный текст программы и модуля можно скачать в виде архива по адресу http://www.borlpasc.narod.ru/Boris/Solve006.zip

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

    По всем вопросам можно писать либо в Гостевую книгу нашего сайта на www.turbopascal.tk, либо

    Постараюсь ответить на все вопросы и учесть все разумные предложения

    Рассылка поддерживается сайтом www.turbopascal.tk. При перепечатке ссылка на сайт обязательна

    Обращаем внимание: наш форум размещается на www.yourpascal.com .

    Внимание: сессия и экзамены еще не начались — самое время подписаться на нашу рассылку:

    Обработка матриц в Паскале

    Матрица — это двумерный массив , каждый элемент которого имеет два индекса: номер строки и номер столбца.

    Объявить двумерный массив (матрицу) можно так:

    имя : 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.

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

    Ссылка на основную публикацию
    Adblock
    detector