5.4.3 Преобразование матриц

Задача. По заданной вещественной матрице A размером 30 х 30 построить матрицу B такого же размера, в которой

Рис. 5.10. Матрица A с выделенной частью

Решение. Введем обозначение O(i,j) для множества чисел, находящихся в заштрихованной на рис. 5.10 части матрицы A. В первом решении мы пользуемся только (уже упоминавшимся) соотношением

max(M  U {x}) = max(max(M), x)

для непустого множества чисел M и числа x, чтобы строить независимые вычисления значений элементов 255#141. Для последовательного просмотра элементов 256#142 заштрихованной части матрицы A достаточно использовать два вложенных цикла со следующими заголовками:

for K := 1 to I do
for L := I+J-K to 30 do

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

module ПреобразованиеМатриц;
    const R = 30;
    var A : array R+1, R+1 of real; I,J,K,L : integer; МАКС :real;
begin
    for I := 1 to R do for J := 1 to R do read(A[I,J]) end end;
    for I := 1 to R do
        for J := 1 to R do
            МАКС := A[I,J];
            for K := 1 to I do for L := I+J-K to R do
                (*

                *)

                if МАКС $<$ A[K,L] then МАКС := A[K,L] end
                (*

                *)
            end;
            (* { MAKC = max(O(I,J)) } *)
            write( МАКС :4 :2)
        end;
        writeln
    end
end ПреобразованиеМатриц.

Для другого, более эффективного решения задачи мы воспользуемся более общим свойством функции 262#148:

для произвольных непустых множеств чисел 264#150. Используя это свойство, мы можем получить следующие соотношения для требуемых значений элементов матрицы A (рис. 5.11):

 
 

Рис.5.11. Матрица B с выделенными элементами

Эти соотношения позволяют строить элементы матрицы A в следующем порядке: сначала строим элементы последнего столбца матрицы B ( B[i,R]=A[i, R] для всех $i$), затем первую строку матрицы B (справа налево, используя соотношение 2), а потом строим последовательно вторую, третью, ..., последнюю строку матрицы B, получая ее элементы справа налево с помощью соотношения 1. Приведенная ниже программа реализует этот алгоритм, размещая элементы получаемой матрицы B на месте исходной матрицы A.

module МатричнаяФункция2;
    const R = 30;
    var A : array R+1, R+1 of real; I,J : integer; МАКС, T1,T2 : real;
begin
    for I := 1 to R do for J := 1 to R do read(A[I,J]) end end;
    (* *)
    for J := R-1 to 1 by -1 do
        (* { A[1,J+1] =max(O(1,J+1))} *)
        if A[1,J] $<$ A [1,J+1] then A[1,J] := A [1,J+1]
       (* { A[1,J] =max(O(1,J))} *)
    end;
    (* Закончено построение первой строки и
    последнего столбца матрицы В в матрице А *)
    for I := 2 to R do
        for J := R-1 to 1 by -1 do
            МАКС := A[I,J];
            T1 := A [I,J+1]; (* { T1 =max(O(I,J+1))} *)
            T2 := A [I-1,J+1]; (* { T2 =max(O(I-1,J+1))} *)
            if МАКС < T1 then МАКС := T1 end;
            if МАКС < T2 then МАКС := T2 end;
            A [I,J] := МАКС
            (* {MAKC= A[I,J] =max(O(I,J))} *)
        end
    end;
    (* Печать построенной матрицы B *)
    for I := 1 to R do
        for J := 1 to R do write(A[I,J] :4 :2) end;
        writeLn
    end
end МатричнаяФункция2.