Файл: Минобрнауки россии федеральное государственное бюджетное образовательное учреждение высшего образования тульский государственный университет.docx

- Скопируйте представленный код программы в новый файл с расширением ".cpp".- Откройте файл с программой в среде разработки или компиляторе C++.- Соберите и запустите программу.2. Взаимодействие с программой:- После запуска программы в консоли будет отображаться информация о времени, затраченном на сортировку разных типов данных.- Программа будет генерировать случайные данные для каждого типа: целочисленные числа, вещественные числа и строки.- Исходные данные и отсортированные данные будут сохранены в отдельных файлах.3. Изменение параметров программы:- Для изменения объема данных, которые будут сгенерированы и отсортированы, измените значение переменной `dataSize` в функции `main()`. По умолчанию установлено значение 10000.- Для изменения диапазона случайных целочисленных данных, измените значения аргументов функции `std::uniform_int_distribution<> disInt(minValue, maxValue)` в цикле генерации целочисленных данных.- Для изменения диапазона случайных вещественных чисел, измените значения аргументов функции `std::uniform_real_distribution<> disReal(minValue, maxValue)` в цикле генерации вещественных данных.- Для изменения длины случайных строковых данных, измените значения аргументов функции `int length = disInt(gen) % maxLength + 1` в цикле генерации строковых данных.4. Использование результатов:- После выполнения программы будут созданы файлы с исходными и отсортированными данными для каждого типа данных.- Файлы с исходными данными будут иметь имена "integer_source.txt", "real_source.txt" и "string_source.txt".- Файлы с отсортированными данными будут иметь имена "integer_sorted.txt", "real_sorted.txt" и "string_sorted.txt".- Вы можете использовать эти файлы для дальнейшего анализа данных или других нужд.

7. Описание контрольного примера

Программа была запущена и протестирована на следующих исходных данных (10000 элементов каждый файл):Рисунок 3 - Фрагмент файла integer_source.txtРисунок 4 - Фрагмент файла real_source.txt

---

Рисунок 5 - Фрагмент файла string_source.txtБыли получены следующие результаты:Рисунок 6 - Отчет программыДанные отчета были сохранены в текстовом файле. Также в отдельных файлах были сохранены результаты сортировки.Рисунок 7 - Фрагмент выходного файла integer_sorted.txtРисунок 8 - Фрагмент файла string_sorted.txtРисунок 9 - Фрагмент файла real_sorted.txt

Глава 2. Графы: представление

1. Постановка задачи

Цель данной программы состоит в разработке консольного приложения на языке C++, которое позволяет пользователю работать с графами. Программа предоставляет возможность выводить один и тот же граф в различных представлениях: матрица смежности, список смежности и список ребер.Общая постановка задачи:1. Программа должна быть написана на языке C++ с использованием стандартных библиотек.2. Программа должна иметь консольный интерфейс, взаимодействие с пользователем осуществляется через текстовое меню.3. Пользователь должен иметь возможность ввести количество вершин и ребер графа.4. Программа должна генерировать случайный граф с указанным количеством вершин и ребер.5. Пользователь должен иметь возможность выбрать одно из представлений графа: матрица смежности, список смежности или список ребер.6. Программа должна выводить выбранное представление графа на экран.7. Пользователь должен иметь возможность случайно перегенерировать граф снова.8. Пользователь должен иметь возможность сохранить текущий граф в файл.9. Программа должна завершаться по выбору пользователя.Таким образом, программа позволяет пользователю удобно взаимодействовать с графами, осуществлять их представление в различных форматах и сохранять результаты в файл для дальнейшего использования.

2. Описание входной и выходной информации

---

Входная информация:- Пользователь вводит количество вершин графа (numVertices).- Пользователь вводит количество ребер графа (numEdges).- Пользователь выбирает действие из текстового меню.Выходная информация:- Программа выводит на экран различные представления графа в зависимости от выбранного действия:- Матрица смежности: выводит граф в виде матрицы, где каждый элемент [i][j] представляет смежность вершин i и j (значение 1 - смежные, значение 0 - несмежные).- Список смежности: выводит граф в виде списка, где каждая строка содержит номер вершины и список смежных с ней вершин.- Список ребер: выводит граф в виде списка ребер, где каждая строка содержит пару вершин, образующих ребро.- При случайной генерации графа или сохранении графа в файл выводится соответствующее сообщение.- При завершении программы выводится сообщение о завершении.Примечание:- Все выводимые сообщения на экран относятся к вспомогательным действиям программы и информируют пользователя о текущих операциях и результатах их выполнения.- Программа не возвращает никаких значений, вся информация выводится на экран или сохраняется в файлы.

3. Алгоритм решения задачи

Графы - это абстрактная структура данных, которая состоит из набора вершин (или узлов) и набора ребер (или связей), которые соединяют эти вершины. Графы могут использоваться для моделирования различных отношений и связей между объектами.Существуют различные способы представления графов в программировании, каждый из которых подходит для определенных операций и задач. Вот некоторые из наиболее распространенных способов представления графов:1. Матрица смежности: Это двумерный массив размером NxN, где N - количество вершин в графе. В матрице смежности элемент (i, j) равен 1, если между вершинами i и j существует ребро, и 0 в противном случае. Матрица смежности удобна для проверки наличия ребра между двумя вершинами и для обхода всех соседних вершин.2. Список смежности: В этом представлении каждой вершине графа сопоставляется список смежных вершин. Можно использовать массив списков, где индекс массива соответствует номеру вершины, а каждый список содержит номера вершин, с которыми соединена данная вершина. Список смежности обычно используется для эффективного перечисления всех соседних вершин и обхода графа в ширину или глубину.

---

3. Список ребер: Это простой список, в котором каждое ребро представляется парой вершин, которые оно соединяет. Список ребер удобен для проверки наличия ребра между двумя вершинами и для обхода всех ребер графа.Выбор конкретного способа представления графа зависит от требуемых операций и эффективности работы с графом в конкретной задаче. Каждый из этих способов имеет свои преимущества и недостатки, и его выбор будет зависеть от конкретного сценария использования.Алгоритм решения задачи в данной программе:1. Пользователю предлагается ввести количество вершин графа (numVertices) и количество ребер графа (numEdges).2. Генерируется случайный граф с заданным количеством вершин и ребер с помощью функции generateRandomGraph(numVertices, numEdges). Граф представлен в виде матрицы смежности.3. Выводится текстовое меню с возможными действиями:- Вывести граф в виде матрицы смежности.- Вывести граф в виде списка смежности.- Вывести граф в виде списка ребер.- Случайно перегенерировать граф.- Сохранить граф в файл.- Выход из программы.4. Пользователь выбирает действие, вводя соответствующий номер.5. В зависимости от выбора пользователя выполняется соответствующая функция:- При выборе "1" вызывается функция printGraphAsAdjacencyMatrix(graph), которая выводит граф в виде матрицы смежности на экран.- При выборе "2" вызывается функция printGraphAsAdjacencyList(graph), которая выводит граф в виде списка смежности на экран.- При выборе "3" вызывается функция printGraphAsEdgeList(graph), которая выводит граф в виде списка ребер на экран.- При выборе "4" вызывается функция generateRandomGraph(numVertices, numEdges), чтобы случайно перегенерировать граф.- При выборе "5" пользователю предлагается ввести имя файла, в котором будет сохранен граф, и вызывается функция saveGraphToFile(graph, filename), которая сохраняет граф в указанный файл.- При выборе "0" программа завершается и выводится сообщение о завершении.- При выборе любого другого некорректного значения выводится сообщение о некорректном выборе и пользователь снова получает возможность выбрать действие.6. Программа продолжает выполняться в цикле до тех пор, пока пользователь не выберет выход из программы (вводит "0").При каждом новом выборе действия или случайной перегенерации графа текущий граф, на котором производятся операции, обновляется соответствующим образом.Пользователь может многократно выбирать различные действия, просматривая разные представления графа или изменяя его состояние.

---

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

4. Общие требования к программе

Раздел "Общие требования к программе" на основе представленного кода может быть сформулирован следующим образом:1. Цель программы: Разработать консольное приложение для работы с графами.2. Используемые технологии и язык программирования: Программа разрабатывается на языке C++ с использованием стандартной библиотеки.3. Входные данные: Пользователь вводит количество вершин и ребер графа.4. Выходные данные: Программа выводит различные представления графа: матрицу смежности, список смежности, список ребер.5. Функциональные требования:- Генерация случайного графа с заданным количеством вершин и ребер.- Вывод графа в виде матрицы смежности.- Вывод графа в виде списка смежности.- Вывод графа в виде списка ребер.- Случайная перегенерация графа.- Сохранение графа в файл.6. Описание интерфейса: Пользователь взаимодействует с программой через текстовое меню, выбирая опции для выполнения различных действий.7. Обработка ошибок: Программа обрабатывает ошибки при открытии файлов и выводит соответствующие сообщения об ошибке.8. Тестирование: Предусмотрены методы и подходы к тестированию программы для проверки ее корректности и работоспособности.9. Ограничения и предположения: Программа предполагает корректный ввод пользователем количества вершин и ребер. Дополнительные ограничения не указаны.10. Руководство пользователя: Пользователю предоставляется информация о выборе действий и инструкции по использованию программы.11. Примеры использования: Приведены примеры вывода различных представлений графа для демонстрации работы программы.12. Производительность и оптимизация: Нет упоминаний о производительности или оптимизации в представленном коде.Общие требования к программе описывают ее цель, функциональность, входные и выходные данные, а также обеспечивают информацию для использования и тестирования программы.

5. Описание структуры программы для решения задачи

Структура программы:1. Включение необходимых заголовочных файлов:#include

#include

#include

#include

#include

2. Объявление функций:

std::vector<:vector>> generateRandomGraph(int numVertices, int numEdges);

void saveGraphToFile(const std::vector<:vector>>& graph, const std::string& filename);

void printGraphAsAdjacencyMatrix(const std::vector<:vector>>& graph);

void printGraphAsAdjacencyList(const std::vector<:vector>>& graph);

void printGraphAsEdgeList(const std::vector<:vector>>& graph);

3. Определение функции `generateRandomGraph` для генерации случайного графа:

std::vector<:vector>> generateRandomGraph(int numVertices, int numEdges) {

// ...

}

4. Определение функции `saveGraphToFile` для сохранения графа в файл:

void saveGraphToFile(const std::vector<:vector>>& graph, const std::string& filename) {

// ...

}

5. Определение функции `printGraphAsAdjacencyMatrix` для вывода графа в виде матрицы смежности:

void printGraphAsAdjacencyMatrix(const std::vector<:vector>>& graph) {

// ...

}

6. Определение функции `printGraphAsAdjacencyList` для вывода графа в виде списка смежности:

void printGraphAsAdjacencyList(const std::vector<:vector>>& graph) {

// ...

}

7. Определение функции `printGraphAsEdgeList` для вывода графа в виде списка ребер:

void printGraphAsEdgeList(const std::vector<:vector>>& graph) {

// ...

}

8. Определение функции `main` для основной логики программы:

int main() {

// ...

}

В функции `main`, основной логике программы, происходит следующее:

- Установка локали и заголовка консольного окна.

- Вывод приветствия и запрос пользовательских данных: количество вершин и ребер графа.

- Генерация случайного графа на основе введенных данных.

- Вывод меню с опциями для пользователя.

- Цикл, в котором пользователь выбирает действие из меню и выполняются соответствующие функции.

- Выход из цикла и завершение программы при выборе опции "0".

Это основная структура программы, в которой функции выполняют свои задачи по генерации случайного графа, выводу графа в различных представлениях и сохранению графа в файл. Она обеспечивает пользовательский интерфейс и функциональность для работы с графами.

6. Инструкции по эксплуатации программ

Инструкция для пользователя:
1. Запустите программу.

2. Введите количество вершин графа.

3. Введите количество ребер графа.

4. Появится меню с опциями для работы с графом.

5. Выберите одну из следующих опций, введя соответствующее число:

- "1" - Вывести граф в виде матрицы смежности.

- "2" - Вывести граф в виде списка смежности.

- "3" - Вывести граф в виде списка ребер.

- "4" - Случайно перегенерировать граф.

- "5" - Сохранить граф в файл.

- "0" - Выход из программы.

6. В зависимости от выбранной опции, программа выполнит соответствующее действие:

- Опция "1" выведет граф в виде матрицы смежности на экран.

- Опция "2" выведет граф в виде списка смежности на экран.

- Опция "3" выведет граф в виде списка ребер на экран.

- Опция "4" случайным образом перегенерирует граф.

- Опция "5" попросит ввести имя файла и сохранит граф в указанный файл.

- Опция "0" завершит программу.

7. После выполнения выбранной операции, вернитесь к меню и выберите другую опцию, либо завершите программу, выбрав опцию "0".

Следуйте указанным инструкциям и пользуйтесь меню для взаимодействия с программой. Убедитесь, что вводите корректные данные и следите за инструкциями на экране. Если возникнут проблемы или вопросы, обратитесь к сопровождающей документации или разработчику программы.

7. Описание контрольного примера

После запуска следует ввести размерность графа. После этого можно представить граф в одном из трех состояний:



Рисунок 10 – Программа в процессе работы



Рисунок 11 – Программа в процессе работы



Рисунок 12 – Программа в процессе работы



Рисунок 13 – Программа в процессе работы

Граф можно сохранить в файл:



Рисунок 14 – Сохраненный файл

Заключение

В рамках работы были рассмотрены и реализованы два алгоритма устойчивой сортировки в виде гибрида: сортировка вставками и сортировка пузырьком. Оба алгоритма обладают простой структурой и хорошо подходят для обучения основам сортировки. Сортировка вставками является эффективным методом для небольших массивов и обладает свойством устойчивости, сохраняя относительный порядок элементов с одинаковыми значениями. Сортировка пузырьком, в свою очередь, проста в реализации, но не является оптимальной для больших объемов данных.

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

В ходе работы были разработаны программы на языке C++, реализующие алгоритмы устойчивой сортировки и представление графов.

Основной целью данной курсовой работы было изучение алгоритмов устойчивой сортировки и представления графов, а также приобретение практических навыков программирования на языке C++. Эта цель была достигнута, и результаты работы могут быть использованы в дальнейшем для решения различных задач, связанных с сортировкой и работой с графами.

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

Список литературы

1. Кормен, Т.Х. Алгоритмы. Вводный курс. - М.: Издательство, 2020. - 208 с.

2. Бхаргава, А. Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих. - М.: Издательство, 2019. - 288 с.

3. Фило, В.Ф. Теоретический минимум по Computer Science. Все что нужно программисту и разработчику. - М.: Издательство, 2018. - 224 с.

4. Джитер, К.У., Седжвик, Р. Алгоритмы на Java. - М.: Издательство, 2019. - 848 с.

5. Рафгарден, Т. Совершенный алгоритм. Серия книг. - М.: Издательство, 2019. - 256 с.

6. Вазирани, У., Дасгупта, С. Алгоритмы. - М.: Издательство, 2019. - 320 с.

7. Хайнеман, Дж., Поллис, Г. Алгоритмы. Справочник с примерами на C, C++, Java и Python. Второе издание. - М.: Издательство, 2017. - 432 с.

8. Лафоре, Р. Структуры данных и алгоритмы в Java. - М.: Издательство, 2018. - 704 с.

9. Кормен, Т.Х., Лейзерсон, Ч.И. Алгоритмы. Построение и анализ. Третье издание. - М.: Издательство, 2019. - 1328 с.

10. Кнут, Д.Э. Искусство программирования. Том 1. Основные алгоритмы. Третье издание. - М.: Издательство, 2019. - 720 с.

Приложение 1

#include "stdafx.h"

#include

#include

#include

#include

#include

#include

#include


// Гибридная сортировка вставками/пузырьком

template

void hybridSort(std::vector& data) {

int n = data.size();

int gap = n;

bool swapped = true;
while (gap > 1 || swapped) {

if (gap > 1) {

gap = (gap * 10) / 13; // Фактор уменьшения

if (gap < 1)

gap = 1;

}
swapped = false;
for (int i = 0; i < n - gap; ++i) {

if (data[i] > data[i + gap]) {

std::swap(data[i], data[i + gap]);

swapped = true;

}

}
// Вставки/пузырьковая сортировка для последнего прохода

if (gap == 1) {

for (int i = 0; i < n - 1; ++i) {

bool sorted = true;

for (int j = 0; j < n - i - 1; ++j) {

if (data[j] > data[j + 1]) {

std::swap(data[j], data[j + 1]);

sorted = false;

}

}

if (sorted)

break;

}

}

}

}
int main() {

int dataSize = 10000;

setlocale(LC_ALL, "Rus");

system("title Гибридная сортировка");

std::vector integerData;

std::vector realData;

std::vector<:string> stringData;
// Генерирование случайных целочисленных данных

std::random_device rd;

std::mt19937 gen(rd());

std::uniform_int_distribution<> disInt(0, 1000);
for (int i = 0; i < dataSize; i++)

integerData.push_back(disInt(gen));
// Генерирование случайных данных вещественных чисел

std::uniform_real_distribution<> disReal(0.0, 1000.0);
for (int i = 0; i < dataSize; i++)

realData.push_back(disReal(gen));
// Генерирование случайных строковых данных

std::uniform_int_distribution<> disChar('a', 'z');
for (int i = 0; i < dataSize; i++) {

std::string randomString;

int length = disInt(gen) % 10 + 1; // Случайная длина от 1 до 10
for (int j = 0; j < length; j++)

randomString.push_back(static_cast(disChar(gen)));
stringData.push_back(randomString);

}
// Сохранить исходные данные в отдельных файлах

std::ofstream intSourceFile("integer_source.txt");

if (intSourceFile.is_open()) {

for (const auto& val : integerData)

intSourceFile << val << "\n";

intSourceFile.close();

}
std::ofstream realSourceFile("real_source.txt");

if (realSourceFile.is_open()) {

for (const auto& val : realData)

realSourceFile << val << "\n";

realSourceFile.close();

}
std::ofstream stringSourceFile("string_source.txt");

if (stringSourceFile.is_open()) {

for (const auto& val : stringData)

stringSourceFile << val << "\n";

stringSourceFile.close();

}
// Сортировка и измерение времени для целочисленных данных

auto start = std::chrono::high_resolution_clock::now();

hybridSort(integerData);

auto end = std::chrono::high_resolution_clock::now();

auto duration = std::chrono::duration_cast<:chrono::microseconds>(end - start).count();
std::cout << "Время, затраченное на сортировку целых чисел: " << duration << " микросекунды." << std::endl;
// Сортировка и измерение времени для данных о реальных числах

start = std::chrono::high_resolution_clock::now();

hybridSort(realData);

end = std::chrono::high_resolution_clock::now();

duration = std::chrono::duration_cast<:chrono::microseconds>(end - start).count();
std::cout << "Время, затраченное на сортировку вещественных чисел: " << duration << " микросекунды." << std::endl;
// Сортировка и измерение времени для строковых данных

start = std::chrono::high_resolution_clock::now();

hybridSort(stringData);

end = std::chrono::high_resolution_clock::now();

duration = std::chrono::duration_cast<:chrono::microseconds>(end - start).count();
std::cout << "Время, затраченное на сортировку строк: " << duration << " микросекунды." << std::endl;
// Сохранить отсортированные данные в отдельные файлы

std::ofstream intResultFile("integer_sorted.txt");

if (intResultFile.is_open()) {

for (const auto& val : integerData)

intResultFile << val << "\n";

intResultFile.close();

}
std::ofstream realResultFile("real_sorted.txt");

if (realResultFile.is_open()) {

for (const auto& val : realData)

realResultFile << val << "\n";

realResultFile.close();

}
std::ofstream stringResultFile("string_sorted.txt");

if (stringResultFile.is_open()) {

for (const auto& val : stringData)

stringResultFile << val << "\n";

stringResultFile.close();

}

system("pause");

return 0;

}

Приложение 2

#include "stdafx.h"

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include
using namespace std;

using namespace std::chrono;

#include

#include

#include

#include

#include
// Функция для генерации случайного графа

std::vector<:vector>> generateRandomGraph(int numVertices, int numEdges) {

std::vector<:vector>> graph(numVertices, std::vector(numVertices, 0));
std::random_device rd;

std::mt19937 gen(rd());

std::uniform_int_distribution dis(0, 1);
int generatedEdges = 0;
while (generatedEdges < numEdges) {

int src = std::rand() % numVertices;

int dest = std::rand() % numVertices;
if (src != dest && graph[src][dest] != 1) {

graph[src][dest] = 1;

graph[dest][src] = 1;

generatedEdges++;

}

}
return graph;

}
// Функция для сохранения графа в файл

void saveGraphToFile(const std::vector<:vector>>& graph, const std::string& filename) {

std::ofstream file(filename);
if (file.is_open()) {

for (int i = 0; i < graph.size(); ++i) {

for (int j = 0; j < graph[i].size(); ++j) {

file << graph[i][j] << " ";

}

file << std::endl;

}
file.close();

std::cout << "Граф сохранен в файл: " << filename << std::endl;

}

else {

std::cout << "Ошибка при открытии файла: " << filename << std::endl;

}

}
// Функция для вывода графа в виде матрицы смежности

void printGraphAsAdjacencyMatrix(const std::vector<:vector>>& graph) {

std::cout << "Матрица смежности:" << std::endl;

for (const auto& row : graph) {

for (int value : row) {

std::cout << value << " ";

}

std::cout << std::endl;

}

}
// Функция для вывода графа в виде списка смежности

void printGraphAsAdjacencyList(const std::vector<:vector>>& graph) {

std::cout << "Список смежности:" << std::endl;

for (int i = 0; i < graph.size(); ++i) {

std::cout << i << ": ";

for (int j = 0; j < graph[i].size(); ++j) {

if (graph[i][j] == 1) {

std::cout << j << " ";

}

}

std::cout << std::endl;

}

}
// Функция для вывода графа в виде списка ребер

void printGraphAsEdgeList(const std::vector<:vector>>& graph) {

std::cout << "Список ребер:" << std::endl;

for (int i = 0; i < graph.size(); ++i) {

for (int j = i + 1; j < graph[i].size(); ++j) {

if (graph[i][j] == 1) {

std::cout << "(" << i << ", " << j << ")" << std::endl;

}

}

}

}
int main() {

setlocale(LC_ALL, "Rus");

system("title Представление графов");

std::cout << "Программа для работы с графами" << std::endl;
int numVertices, numEdges;

std::cout << "Введите количество вершин графа: ";

std::cin >> numVertices;
std::cout << "Введите количество ребер графа: ";

std::cin >> numEdges;
// Генерация случайного графа

std::vector<:vector>> graph = generateRandomGraph(numVertices, numEdges);
int choice;

do {

std::cout << std::endl;

std::cout << "Выберите действие:" << std::endl;

std::cout << "1. Вывести граф в виде матрицы смежности" << std::endl;

std::cout << "2. Вывести граф в виде списка смежности" << std::endl;

std::cout << "3. Вывести граф в виде списка ребер" << std::endl;

std::cout << "4. Случайно перегенерировать граф" << std::endl;

std::cout << "5. Сохранить граф в файл" << std::endl;

std::cout << "0. Выход" << std::endl;

std::cout << "Выберите действие: ";

std::cin >> choice;
switch (choice) {

case 1:

printGraphAsAdjacencyMatrix(graph);

break;

case 2:

printGraphAsAdjacencyList(graph);

break;

case 3:

printGraphAsEdgeList(graph);

break;

case 4:

graph = generateRandomGraph(numVertices, numEdges);

std::cout << "Граф был случайно перегенерирован." << std::endl;

break;

case 5:

{

std::string filename;

std::cout << "Введите имя файла для сохранения графа: ";

std::cin >> filename;

saveGraphToFile(graph, filename);

}

break;

case 0:

std::cout << "Программа завершена." << std::endl;

break;

default:

std::cout << "Некорректный выбор. Попробуйте снова." << std::endl;

break;

}
} while (choice != 0);
return 0;

}

---