Добавлен: 09.01.2024
Просмотров: 21
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
МИНИСТЕРСТВО ЦИФРОВОГО РАЗВИТИЯ, СВЯЗИ И МАССОВЫХ КОММУНИКАЦИЙ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение высшего образования
«Санкт-Петербургский государственный университет телекоммуникаций
им. проф. М. А. Бонч-Бруевича»
(СПбГУТ)
Факультет Информационных систем и технологий
Кафедра Безопасности информационных систем
Отчет
По предмету «Алгоритмы и структуры данных»
о практической работе №1:
«Разработка алгоритмов и программ обработки массивов данных»
Выполнил студент гр. ИСТ-022:
Волков Кирилл
// // //оценка подпись
Проверил: Бородянский Ю.М.
// //Подпись
Задача работы
Провести работу по разработке блок-схемы и программы по умножению матриц на языке С++, приобрести навыки и умения анализа алгоритма и всего кода разработанной программы в Big-O-нотации.
Блок-схема
Рассчет сложности Big-O
Строки 14 – 22: О(1)+O(1)+O(1)+O(1)+O(1) = O(1)
Строки 29– 32: (O(1)+O(1)+O(1))*O(n) = O(n)
Строка 28: O(n)*O(n) = O(n^2)
Строка 34-38: ((O(1)+O(1)+O(1))*O(n))*O(n) = O(n^2)
Строка 41-48: ((O(1)+O(1)+O(1))*O(n))*O(n) = O(n^2)
Строка 52-60: (O(1)*O(n))*O(n)
Строка 62-68: (((O(1)*O(n))+O(1))*O(n))*O(n) = O(n^3)
Строка 70-77: (O(1)*O(n))*O(n) = O(n^2)
Ответ: общая сумма сложности O(n^3);
Вывод
В результате работы была разработана программа, которая вычисляет произведение двух матриц, заполненных случайными числовыми данными,
Мы получили новые знания о языке программирования C++, узнали о генерации случайных чисел.
Была проведена работа по анализу программного кода и была вычислена сложность нотации Big-O.
Код программы находится в приложение 1.
Приложение
1
#include
#include
using namespace std;
int main()
{
SetConsoleOutputCP(1251);
SetConsoleCP(1251);
int a,b,c,d;
cout<<"Введите размер матрицы A -> ";
cin>>a; // O(1);
cin>>b; // O(1);
cout<<"Введите размер матрицы B -> ";
cin>>c; // O(1);
cin>>d; // O(1);
if (b!=c) // O(1);
cout<<"Программа не может выполнить задачу умножения. \nКоличество столбцов первой матрицы не равно количеству строк второй матрицы";
else
{
int matrix1[a][b],matrix2[c][d],matrix3[a][d];
for(int i=0;i
for(int j=0;j
{
matrix1[i][j] = -100 + rand() % 201; // O(max(1,1,1)=O(1)
}
for(int i=0;i
for(int j=0;j
{
matrix2[i][j] = -100 + rand() % 201; //O(max(1,1,1)=O(1)
}
cout<<"Матрица 1:"<
for(int i=0;i
for(int j=0;j
{
if (j == 0)
cout<<"\n";
else
cout<<"\t";
cout<
}
cout<
for(int i=0;i
for(int j=0;j
{
if (j == 0)
cout<<"\n";
else
cout<<"\t";
cout<
}
for(int i=0;i
for(int j=0;j
{
matrix3[i][j]=0;
for(int k=0;k
matrix3[i][j]+=(matrix1[i][k]*matrix2[k][j]);
} // O(n^3)
cout<
for(int i=0;i
for(int j=0;j
{
if (j == 0)
cout<<"\n";
else
cout<<"\t";
cout<
}
}
return 0;
}
Гор. Санкт-Петербург
2021