Шифр 11. Написать программу, которая оптимальным образом расставляет скобки при перемножении матриц

  • ID: 51140 
  • 6 страниц

Фрагмент работы:

Задание

Написать программу, которая оптимальным образом расставляет скобки при перемножении матриц. Размерности матриц считать из файла. На экран вывести промежуточные вычисления и результат.

Номер варианта выбирается по последней цифре пароля.

Вариант 1

М1[2x5], M2[5x7], M3[7x4], М4[4x5], M5[5x6], M6[6x3], M7[3x2], M8[2x9].

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

program kontr;

const

inputFile = 'input.txt';

outputFile = 'output.txt';

nMax = 10;

type

TMatrix = array[1..nMax, 1..nMax] of Integer;

var

n: Integer; { Количество матриц }

p: array[0..nMax] of Integer; { Массив размерностей матриц }

m: TMatrix; { Матрица минимальных трудоемкостей }

s: TMatrix; { Матрица для расстановки скобок }

{ Рассчитывает оптимальное перемножение матриц }

procedure Calc;

var

i, j, l, k: Byte;

q: Longint;

begin

for l := 2 to n do { Количество перемножаемых матриц }

for i := 1 to n - l + 1 do

begin

j := i + l - 1;

m[i, j] := MaxInt;

for k := i to j - 1 do

begin

{ Рассчитываем трудоемкость перемножения матриц }

q := m[i, k] + m[k + 1, j] + p[i - 1] * p[k] * p[j];

if q < m[i, j] then { Определяем минимальную трудоемкость }

begin

m[i, j] := q;

s[i, j] := k;

end;

end;

end;

end;

{ Выводит результат расстановки скобок }

procedure WriteResults(i, j: Integer);

var

st: String;

begin

if i = j then { Саму на себя матрицу не умножаем }

begin

Str(i, st);

Write('М' + st);

end

else

begin

Write('(');

WriteResults(i, s[i, j]); { Вызов для меньшего количества матриц }

Write('*');

WriteResults(s[i, j] + 1, j);

Write(')');

end;

end;

{ Выводит матрицу }

procedure WriteMatrix(m: TMatrix);

var

i, j: Integer;

begin

for i := 1 to n do

begin

for j := 1 to n do

Write(m[i, j]: 5);

Writeln;

end;

end;

var

i: Integer;

begin

Assign(Input, inputFile);

Reset(Input);

Assign(Output, outputFile);

Rewrite(Output);

Read(n);

for i := 0 to n do

Read(p[i]);

FillChar(m, SizeOf(m), 0);

FillChar(s, SizeOf(s), 0);

Calc;

Writeln('Матрица минимальных трудоемкостей:');

WriteMatrix(m);

Writeln('Матрица для расстановки скобок:');

WriteMatrix(s);

Write('Результат: ');

WriteResults(1, n);

Writeln;

Writeln('Полученная трудоемкость: ', m[1, n]);

end.