СибГУТИ Контрольная работа Теория сложности вычислительных процессов и структур Операционные системы скачать бесплатно

Задание

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

M1[r0xr1], M2[r1xr2], M3[r2xr3], M4[r3xr4], M5[r4xr5], M6[r5xr6], M7[r6xr7], M8[r7xr8], M9[r8xr9], M10[r0xr10], M11[r10xr11], M12[r11xr12].

Размерности матриц считать из файла. 

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

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

r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r11 r12 

0 8 6 2 5 9 3 6 4 7 3 9 7 2 

1 6 9 4 8 9 3 5 6 8 7 2 6 8 

2 5 3 2 6 9 7 4 9 2 6 7 4 7 

3 4 6 6 9 7 5 6 4 2 9 3 7 5 

4 9 5 2 8 5 6 9 8 3 4 7 9 2 

5 5 8 3 4 9 5 7 6 8 4 9 2 6 

6 6 3 9 4 9 4 8 6 4 7 9 9 6 

7 2 2 9 6 9 3 7 7 9 8 3 4 2 

8 5 6 8 7 2 3 2 9 4 4 4 8 5 

9 6 5 5 9 7 8 9 8 3 2 8 4 6 

Описание алгоритма

Задача решается с помощью следующего алгоритма:

1) Заполняем трудоемкости матриц:

Трудоемкости на главной диагонали равны 0:

for i:=1 to n do f(i,i):=0;

2) Внешний цикл по t – длине перемножаемого блока;

Средний цикл по k – местоположению блока;

Внутренний – поиск минимума по j. 

for t:=1 to n–1 do

for k:=1 to n–t do

Текст программы на языке Pascal

...

Результаты работы программы

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

    0  240  520  268  298  300  390  408  440  472  576  626

    0    0  336  208  244  244  352  356  388  420  532  576

    0    0    0  112  160  152  296  276  308  340  468  500

    0    0    0    0   42   40  166  156  188  220  340  378

    0    0    0    0    0   12   48  100  132  164  228  308

    0    0    0    0    0    0   54   96  128  160  248  310

    0    0    0    0    0    0    0   72  104  136  200  280

    0    0    0    0    0    0    0    0  144  208  480  484

    0    0    0    0    0    0    0    0    0   64  192  304

    0    0    0    0    0    0    0    0    0    0  128  240

    0    0    0    0    0    0    0    0    0    0    0  160

    0    0    0    0    0    0    0    0    0    0    0    0

Матрица для расстановки скобок:

    0    1    2    1    4    4    6    4    4    4    4    4

    0    0    2    2    4    4    6    4    4    4    4    4

    0    0    0    3    4    3    6    4    4    4    4    4

    0    0    0    0    4    4    6    4    4    4    4    4

    0    0    0    0    0    5    6    6    6    6   10   11

    0    0    0    0    0    0    6    6    6    6    6    6

    0    0    0    0    0    0    0    7    8    9   10   11

    0    0    0    0    0    0    0    0    8    8    8    8

    0    0    0    0    0    0    0    0    0    9   10   10

    0    0    0    0    0    0    0    0    0    0   10   10

    0    0    0    0    0    0    0    0    0    0    0   11

    0    0    0    0    0    0    0    0    0    0    0    0

Результат: ((М1*(М2*(М3*М4)))*((((М5*М6)*(((М7*М8)*М9)*М10))*М11)*М12))

Полученная трудоемкость: 626