Массивы. Матрицы. Типичные задачи. Опции

[Altair]

Содержание:

• Задание массивов, задание матриц, ввод массивов/матриц
• Решения: Матрицы, Массивы. Задачи (by AlaRic)
• Суммы различных элементов матриц (диагонали, элементы над/под диагоналями, и т.д.)
• Вычисление произведения матриц (квадратных/сцепленных), нахождение детерминанта матрицы(рекурсивное/приведением к диагональному виду)
• Инициализация массивов/матриц случайными значениями
• Заполнение массива по-спирали
• Модуль для работы с динамическими массивами (by Oleg_Z)
• Модуль для работы с динамическими массивами (by Volvo)
• Модуль для работы с матрицами
• Как найти в массиве максимальную последовательность одинаковых символов/максимальную возрастающую последовательность?
• Как задать матрицу, чтобы быстро поменять местами ее строки/столбцы?
• Как вычислить заданный многочлен от матрицы A?
• Как вычислить ранг матрицы?
  
• Нахождение максимальных/минимальных элементов массива

----- ----- ----- ----- -----

Одномерные и многомерные массивы (матрицы) в Паскале.

Задание массивов.
Тип массив в Паскале задается следующим образом:

<имя типа> = ARRAY [<сп.индексов типов>] OF <тип>


Где
<имя типа> - правильный идентификатор.
ARRAY, OF - зарезервированные слова (массив, из)
[<сп.индексов типов>] - список из одного или нескольких индексных типов. (задается размерность массива)
<тип> - любой тип Паскаля, кроме файлового.
После описания типа массива, можно описывать переменные этого типа.

Можно не описывать отдельно тип массив, а описать конкретную переменную, как переменную типа массив:

<variable> : Array[<index>] OF <type>

Где
<variable> - правильный идентификатор.
Array, OF- зарезервированные слова.
<index> - индекс задающий размерность массива.
<type> - любой тип Паскаля, кроме файлового.

Вкачестве индексных типов можно использовать любые порядковые типы, кроме longint
Оюычно в качестве индекстного типа употребляется тип-диапазон, в котором задаются границы изменения индексов.

Вложенные массивы или многомерные или матрицы

Собственно определение матрицы - прямоугольная сетка чисел, справедливо и для многомерных массивов. По сути это и есть матрица.

Задать матрицу в Паскале можно следующим образом:

const
	NN = 10; MM = 10;
type
	matrix = array[1..NN] of array[1..MM] of integer;

В данном случае мы описали матрицу размеров NNxMM.
Т.е. матрица в понимании компилятора - это массив из массивов.

[e1,1]  [e1,2]  [e1,3]  ... [e1,NN]
[e2,1]  [e2,2]  [e2,3]  ... [e2,NN]
...
[eMM,1] [eMM,2] [eMM,3] ... [eMM,NN]

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

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

{вывод на экран элемент массива A с индексом 5}
write(A[5]); 

{ввод элемента массива A с индексом 6}
readln(A[6]);

{
  присваиваем элементу массива с индексом 7 сумму эл-тов
  массива A с индексами 5 и 6
} 
A[7]:=A[5]+A[6];

Нуль-основанный символьный массив - это такой массив, в котором индекс первого элемента
равен нулю, а последнего - положительному ненулевому целому числу. Например:

   Array [0..X] Of Char;

Если вы включаете расширенный синтаксис (с помощью директивы компилятора {$X+}), то
нуль-основанный символьный массив может быть инициализирован строкой, длина которой меньше
чем объявленная длина массива.
(в нулевом элемент такого массива хранится длинна строки. см. FAQ по строкам)

Работа с матрицами, ввод матрицы, операции над матрицами, распространенные задачи с матрицами.

Матрица - прямоугольная сетка чисел. Элементы матрицы - числа.
Каждый элемент матрицы имеет два индекса - номер строки и номер столбца, в котором он расположен.
Принято сначала указывать индекс строки, а затем индекс столбца.
Создадим тип матрицы:

const
	NN = 10;	{ число СТРОК! }
	MM = 10;	{ число СТОЛБЦОВ! }
type
	TElem = integer; 
	Matrix = array[1..NN, 1..MM] of TElem;

Очень часто при решении задач, необходимо проходить по всем элементам строки\столбца\строк и столбуов.
Для этого используют цикл со счетчиком. (FOR ... TO ... DO )

Ввод матрицы:
Опишем процедуры ввода и вывода на экран матрицы.

const
	NN = 10;	{ число СТРОК! }
	MM = 10;	{ число СТОЛБЦОВ! }
type
	TElem = integer; 
	Matrix = array[1..NN, 1..MM] of TElem; 
	
(* Построчный ввод матрицы *)
Procedure ReadMatr(var A:Matrix; var n,m:word );
var i, j: word;
begin
	repeat
		write('Введите количество строк: '); readln(N)
	until (N>0) and (N<=NN); 
	repeat
		write('Введите количество столбцов: '); readln(m)
	until (M>0) and (M<=MM);
	For i:=1 to n do begin
		For j:=1 to m do begin
			write('A[',i,j,']= '); readln(A[i,j])
		end 
	end
end; 

(* Построчный вывод матрицы *) 
Procedure PrintMatr(A:Matrix; n,m:word);
Var i, j: word;
begin
	For i:=1 to n do begin
		For j:=1 to m do write(A[i,j],' ');
		writeln
	end
end;

{ тестовая программа} 
var
	n, m: word;
	a: matrix;
begin
	Readmatr(a,n,m);
	PrintMatr(a,n,m)
end.

Сообщение отредактировано: volvo - 13.01.2009 13:35

[volvo]

Вычисление произведения "сцепленных" матриц.

Например:
(2, 3) Х (3, 3) = (2, 3)
(3, 2) Х (2, 5) = (3, 5)

Type
  TType = Integer;

Const
  nRowFirst  = 3; { Количество строк первой матрицы }
  nCommon    = 2; { Количество столбцов первой и строк второй матрицы }
  nColSecond = 5; { Количество столбцов второй матрицы }

Type
  TFirst = { Тип данных для хранения первой матрицы }
    Array[1 .. nRowFirst, 1 .. nCommon] Of TType; 
  TSecond = { Тип данных для хранения второй матрицы }
    Array[1 .. nCommon, 1 .. nColSecond] Of TType; 
  TResult = { Тип данных для хранения результата }
    Array[1 .. nRowFirst, 1 .. nColSecond] Of TType; 

{ Собственно процедура перемножения матриц: (res) = (a) X (B) }
Procedure matrixMult(Var res: TResult;
          a: TFirst; b: TSecond);
  Var i, j, k: Integer;
  Begin
    For i := 1 To nRowFirst Do
      For j := 1 To nColSecond Do
        Begin
          res[i, j] := 0;
          For k := 1 To nCommon Do
            res[i, j] := res[i, j] + a[i, k] * b[k, j];
        End
  End;

var
  iRow, iCol: Integer;
  m1: TFirst; m2: TSecond;
  mr: TResult;
begin
  WriteLn('Ввод первой матрицы: (', nRowFirst, 'x', nCommon, ')');
  For iRow := 1 To nRowFirst Do
    For iCol := 1 To nCommon Do
      Begin
        Write('m1[', iRow, ',', iCol,'] : ');
        ReadLn(m1[iRow, iCol])
      End;

  WriteLn('Ввод второй матрицы: (', nCommon, 'x', nColSecond, ')');
  For iRow := 1 To nCommon Do
    For iCol := 1 To nColSecond Do
      Begin
        Write('m2[', iRow, ',', iCol,'] : ');
        ReadLn(m2[iRow, iCol])
      End;

  matrixMult(mr, m1, m2); { Вызов процедуры перемножения }

  WriteLn('Результирующая матрица: (', nRowFirst, 'x', nColSecond, ')');
  For iRow := 1 To nRowFirst Do
    Begin
      For iCol := 1 To nColSecond Do
        Write(mr[iRow, iCol]:4);
      WriteLn
    End;
end.

Вычисление детерминанта (определителя) матрицы с помощью рекурсии.

Const
  max_n = 4;

Type
  matrix = Array[1 .. max_n, 1 .. max_n] Of real;

{ Матрица, для которой будет вычисляться определитель }
Const 
 a: matrix =
   ((2, 9, 9, 4),
    (2, -3, 12, 8),
    (4, 8, 3, -5),
    (1, 2, 6, 4));

function minusOne(n: integer): integer;
  begin
    minusOne := (1 - 2*Byte(Odd(n)));
  end;

function get_addr(i, j: integer;
         const n: integer): integer;
  begin
    get_addr := pred(i) * n + j
  end;

{ Рекурсивное определение определителя }
Function det(Var p; Const n: integer): real;
  Type
    matrix = Array[1 .. max_n * max_n] Of real;
  Var
    my_p: matrix Absolute p;
    pp: ^matrix;
    s: real;
    i, j, curr: integer;
  Begin
    s := 0.0;

    If n = 2 Then
      Begin
        det := my_p[1]*my_p[4] - my_p[2]*my_p[3]; exit
      End;

    For i := 1 To n Do
      Begin
        GetMem(pp, Sqr(Pred(n)) * SizeOf(real));
        curr := 1;
        For j := 1 To n Do
          If j <> i Then
            Begin
              move(my_p[get_addr(j, 2, n)], pp^[get_addr(curr, 1, Pred(n))],
                   pred(n) * SizeOf(real));
              inc(curr);
            End;

        s := s + minusOne(Succ(i)) * my_p[get_addr(i, 1, n)] *
                 det(pp^, Pred(n));
        FreeMem(pp, Sqr(Pred(n)) * SizeOf(real))
      End;

    det := s
  End;

begin
  WriteLn( det(a, 4):0:0 );
end.

Скачать:  REC_DET.PAS ( 1.28 килобайт ) Кол-во скачиваний: 1891