Контрольная работа

Задание на контрольную работу
Написать программу, которая оптимальным образом расставляет скобки при перемножении матриц M₁M₂M₃M₄M₅M₆M₇M₈M₉M₁₀M₁₁M₁₂. Матрицы имеют следующие размерности:

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

Номер варианта r0 r1 r2 r3 r4 r5 r6
0 8 6 2 5 9 3 6
1 6 9 4 8 9 3 5
2 5 3 2 6 9 7 4
3 4 6 6 9 7 5 6
4 9 5 2 8 5 6 9
5 5 8 3 4 9 5 7
6 6 3 9 4 9 4 8
7 2 2 9 6 9 3 7
8 5 6 8 7 2 3 2
9 6 5 5 9 7 8 9

=============================================

ЛАБОРАТОРНАЯ РАБОТА 1.«Поиск минимального остова»

Задание на лабораторную работу
Написать программу, которая по алгоритму Краскала находит остов
минимального веса для связного взвешенного неориентированного графа,
имеющего 10 вершин. Граф задан матрицей смежности (0 означает, что
соответствующей дуги нет). Данные считать из файла.
Вывести ребра остова минимального веса в порядке их присоединения и вес
остова.

Номер варианта выбирается по последней цифре пароля.
Вариант 0
0 10 23 11 0 18 22 22 15 18
10 0 4 0 4 13 17 26 10 22
23 4 0 0 15 16 21 22 25 3
11 0 0 0 16 20 15 16 0 14
0 4 15 16 0 3 8 9 21 28
18 13 16 20 3 0 27 13 7 0
22 17 21 15 8 27 0 19 13 27
22 26 22 16 9 13 19 0 16 21
15 10 25 0 21 7 13 16 0 23
18 22 3 14 28 0 27 21 23 0
Вариант 1
0 10 13 17 18 14 6 23 7 9
10 0 13 6 13 3 2 19 13 4
13 13 0 17 12 15 19 19 9 0
17 6 17 0 2 10 0 13 16 14
18 13 12 2 0 15 18 17 9 14
14 3 15 10 15 0 15 3 6 8
6 2 19 0 18 15 0 2 0 0
23 19 19 13 17 3 2 0 0 4
7 13 9 16 9 6 0 0 0 21
9 4 0 14 14 8 0 4 21 0
2
Вариант 2
0 8 13 8 12 6 17 6 6 3
8 0 8 3 6 2 10 0 13 17
13 8 0 15 11 2 16 0 17 4
8 3 15 0 12 5 0 10 7 0
12 6 11 12 0 18 1 10 15 3
6 2 2 5 18 0 17 5 13 0
17 10 16 0 1 17 0 13 10 4
6 0 0 10 10 5 13 0 14 9
6 13 17 7 15 13 10 14 0 12
3 17 4 0 3 0 4 9 12 0
Вариант 3
0 5 0 9 10 13 18 16 20 21
5 0 20 12 5 4 17 20 10 17
0 20 0 7 18 0 19 6 17 19
9 12 7 0 5 12 14 5 21 25
10 5 18 5 0 19 19 0 20 8
13 4 0 12 19 0 5 21 0 21
18 17 19 14 19 5 0 13 5 0
16 20 6 5 0 21 13 0 11 22
20 10 17 21 20 0 5 11 0 16
21 17 19 25 8 21 0 22 16 0
Вариант 4
0 14 0 19 18 8 21 21 8 4
14 0 17 15 17 9 5 19 21 4
0 17 0 11 0 14 14 12 0 6
19 15 11 0 25 12 18 6 7 4
18 17 0 25 0 7 0 14 16 16
8 9 14 12 7 0 22 14 7 4
21 5 14 18 0 22 0 9 7 0
21 19 12 6 14 14 9 0 14 5
8 21 0 7 16 7 7 14 0 18
4 4 6 4 16 4 0 5 18 0
Вариант 5
0 22 25 0 24 0 14 15 15 0
22 0 29 29 9 6 0 25 14 28
25 29 0 5 0 15 19 6 24 11
0 29 5 0 21 11 12 22 7 22
24 9 0 21 0 8 13 12 9 18
0 6 15 11 8 0 11 13 0 11
14 0 19 12 13 11 0 9 19 26
15 25 6 22 12 13 9 0 20 17
15 14 24 7 9 0 19 20 0 24
0 28 11 22 18 11 26 17 24 0
3
Вариант 6
0 0 24 0 14 16 24 13 16 0
0 0 9 23 6 26 19 0 10 27
24 9 0 14 5 23 22 19 8 10
0 23 14 0 22 7 16 5 11 25
14 6 5 22 0 15 18 22 23 26
16 26 23 7 15 0 29 0 23 21
24 19 22 16 18 29 0 4 8 26
13 0 19 5 22 0 4 0 8 7
16 10 8 11 23 23 8 8 0 28
0 27 10 25 26 21 26 7 28 0
Вариант 7
0 16 16 17 5 2 2 10 0 7
16 0 4 4 10 4 0 21 7 14
16 4 0 21 9 6 0 15 5 19
17 4 21 0 20 7 3 19 0 15
5 10 9 20 0 18 18 8 2 12
2 4 6 7 18 0 0 12 19 12
2 0 0 3 18 0 0 14 9 15
10 21 15 19 8 12 14 0 2 6
0 7 5 0 2 19 9 2 0 15
7 14 19 15 12 12 15 6 15 0
Вариант 8
0 14 9 3 22 17 16 0 14 18
14 0 19 0 2 0 11 14 21 20
9 19 0 17 20 22 4 4 8 9
3 0 17 0 11 3 20 12 10 15
22 2 20 11 0 14 19 17 15 19
17 0 22 3 14 0 0 6 10 0
16 11 4 20 19 0 0 3 11 9
0 14 4 12 17 6 3 0 7 4
14 21 8 10 15 10 11 7 0 7
18 20 9 15 19 0 9 4 7 0
Вариант 9
0 6 20 10 13 9 6 10 2 3
6 0 0 11 7 0 9 16 17 2
20 0 0 20 17 10 2 14 2 4
10 11 20 0 2 18 14 16 15 0
13 7 17 2 0 21 6 0 13 18
9 0 10 18 21 0 4 7 18 9
6 9 2 14 6 4 0 3 15 10
10 16 14 16 0 7 3 0 8 3
2 17 2 15 13 18 15 8 0 0
3 2 4 0 18 9 10 3 0 0

ЛАБОРАТОРНАЯ РАБОТА 2. «Поиск кратчайшего расстояния между двумя вершинами»

Задание на лабораторную работу
Написать программу, которая по алгоритму Дейкстры (если Ваша фамилия
начинается с гласной буквы) или Форда-Беллмана (если Ваша фамилия
начинается с согласной буквы) находит кратчайшее расстояние от вершины с
номером Вашего варианта до всех остальных вершин связного взвешенного
неориентированного графа, имеющего 10 вершин (нумерация вершин
начинается с 0).
Граф задан матрицей смежности (0 означает, что соответствующей дуги
нет). Данные считать из файла.
Вывести все найденные кратчайшие расстояния и соответствующие им пути
(в виде последовательности ребер).

Номер варианта выбирается по последней цифре пароля.
Вариант 0
0 3 11 0 10 11 0 5 11 6
3 0 4 10 11 0 6 3 4 5
11 4 0 1 10 8 0 5 5 4
0 10 1 0 6 12 4 1 4 7
10 11 10 6 0 9 0 3 6 2
11 0 8 12 9 0 7 6 5 7
0 6 0 4 0 7 0 6 0 5
5 3 5 1 3 6 6 0 8 7
11 4 5 4 6 5 0 8 0 10
6 5 4 7 2 7 5 7 10 0
Вариант 1
0 1 11 2 9 3 0 8 3 6
1 0 4 5 6 0 11 10 10 10
11 4 0 6 11 11 0 7 3 1
2 5 6 0 0 2 4 10 0 1
9 6 11 0 0 0 10 2 8 11
3 0 11 2 0 0 5 8 3 6
0 11 0 4 10 5 0 8 4 7
8 10 7 10 2 8 8 0 10 5
3 10 3 0 8 3 4 10 0 7
6 10 1 1 11 6 7 5 7 0
2
Вариант 2
0 11 1 11 3 0 0 10 8 9
11 0 6 8 2 2 8 9 1 1
1 6 0 11 0 8 5 9 7 4
11 8 11 0 5 10 3 2 2 7
3 2 0 5 0 10 11 6 7 1
0 2 8 10 10 0 0 11 10 7
0 8 5 3 11 0 0 1 9 0
10 9 9 2 6 11 1 0 4 11
8 1 7 2 7 10 9 4 0 2
9 1 4 7 1 7 0 11 2 0
Вариант 3
0 9 8 0 7 4 10 6 6 4
9 0 1 7 8 6 4 8 7 2
8 1 0 8 6 4 0 9 2 4
0 7 8 0 2 0 0 7 3 0
7 8 6 2 0 0 10 7 5 0
4 6 4 0 0 0 6 3 10 0
10 4 0 0 10 6 0 10 2 10
6 8 9 7 7 3 10 0 9 6
6 7 2 3 5 10 2 9 0 11
4 2 4 0 0 0 10 6 11 0
Вариант 4
0 5 4 7 6 7 2 7 8 0
5 0 10 1 0 8 7 7 10 8
4 10 0 0 3 8 4 7 3 4
7 1 0 0 3 11 9 8 7 0
6 0 3 3 0 4 7 2 2 11
7 8 8 11 4 0 1 6 5 10
2 7 4 9 7 1 0 8 4 0
7 7 7 8 2 6 8 0 6 3
8 10 3 7 2 5 4 6 0 4
0 8 4 0 11 10 0 3 4 0
Вариант 5
0 11 12 0 7 5 5 1 10 7
11 0 0 8 1 0 1 11 1 0
12 0 0 5 2 14 0 7 3 5
0 8 5 0 0 1 13 6 4 6
7 1 2 0 0 11 4 0 5 12
5 0 14 1 11 0 13 10 14 0
5 1 0 13 4 13 0 11 3 1
1 11 7 6 0 10 11 0 12 6
10 1 3 4 5 14 3 12 0 13
7 0 5 6 12 0 1 6 13 0
3
Вариант 6
0 0 8 8 7 5 5 6 1 2
0 0 3 1 6 3 7 3 0 9
8 3 0 11 2 3 0 8 1 10
8 1 11 0 6 4 0 11 7 9
7 6 2 6 0 2 11 6 3 4
5 3 3 4 2 0 2 1 3 3
5 7 0 0 11 2 0 3 3 7
6 3 8 11 6 1 3 0 0 8
1 0 1 7 3 3 3 0 0 8
2 9 10 9 4 3 7 8 8 0
Вариант 7
0 1 5 5 1 4 0 8 5 6
1 0 6 0 0 8 6 3 5 10
5 6 0 7 7 2 1 6 9 0
5 0 7 0 6 5 9 5 0 4
1 0 7 6 0 4 5 0 9 7
4 8 2 5 4 0 6 1 2 0
0 6 1 9 5 6 0 2 1 3
8 3 6 5 0 1 2 0 2 6
5 5 9 0 9 2 1 2 0 11
6 10 0 4 7 0 3 6 11 0
Вариант 8
0 11 0 0 1 1 4 0 0 3
11 0 5 6 6 8 5 11 4 8
0 5 0 3 9 6 6 9 2 11
0 6 3 0 7 6 3 7 11 8
1 6 9 7 0 3 3 9 9 0
1 8 6 6 3 0 9 3 1 7
4 5 6 3 3 9 0 3 7 10
0 11 9 7 9 3 3 0 0 3
0 4 2 11 9 1 7 0 0 10
3 8 11 8 0 7 10 3 10 0
Вариант 9
0 2 1 2 8 1 1 4 9 6
2 0 9 4 7 5 4 0 0 10
1 9 0 6 3 4 0 0 4 0
2 4 6 0 0 5 2 9 11 5
8 7 3 0 0 7 8 6 8 6
1 5 4 5 7 0 5 10 0 1
1 4 0 2 8 5 0 2 0 5
4 0 0 9 6 10 2 0 9 8
9 0 4 11 8 0 0 9 0 7
6 10 0 5 6 1 5 8 7 0

ЛАБОРАТОРНАЯ РАБОТА 3. «Решение задачи о рюкзаке методом динамического программирования»

Задание на лабораторную работу
Имеется склад, на котором присутствует некоторый ассортимент товаров.
Запас каждого товара неограничен. У каждого товара своя стоимость сi и
масса mi. Написать программу, которая методом динамического
программирования формирует набор товаров максимальной стоимости таким
образом, чтобы его суммарная масса не превышала заданную
грузоподъемность М.
Вывести промежуточные вычисления, сформированный набор, его
стоимость и массу.

Номер варианта выбирается по последней цифре пароля.
Вариант 0
Номер товара, i mi сi M
1 3 14
44 2 5 24
3 7 28
4 6 35
Вариант 1
Номер товара, i mi сi M
1 7 28
43 2 9 43
3 12 51
4 8 34
Вариант 2
Номер товара, i mi сi M
1 8 25
62 2 10 32
3 14 45
4 18 50
Вариант 3
Номер товара, i mi сi M
1 7 15
95 2 14 48
3 13 33
4 15 50
2
Вариант 4
Номер товара, i mi сi M
1 12 24
67 2 15 37
3 9 35
4 10 48
Вариант 5
Номер товара, i mi сi M
1 11 32
80 2 9 27
3 7 15
4 15 54
Вариант 6
Номер товара, i mi сi M
1 6 11
63 2 4 15
3 10 45
4 9 37
Вариант 7
Номер товара, i mi сi M
1 6 15
68 2 13 42
3 9 28
4 7 15
Вариант 8
Номер товара, i mi сi M
1 8 41
57 2 11 56
3 7 28
4 6 32
Вариант 9
Номер товара, i mi сi M
1 9 28
50 2 10 25
3 8 16
4 6 15