Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Отчет по расчетно-графической работе по дисциплине: «Алгоритмы и структуры данных» - файл


скачать (41.8 kb.)


Федеральное государственное бюджетное образовательное учреждение

высшего образования

«Омский государственный технический университет» Факультет информационных технологий и компьютерных систем

Кафедра «Автоматизированные системы обработки информации и управления»


ОТЧЕТ ПО РАСЧЕТНО-ГРАФИЧЕСКОЙ РАБОТЕ

по дисциплине: «Алгоритмы и структуры данных»


Вариант 1

Выполнил:

студент гр. ПИН – 191 И. П. Абиев

Принял: доцент

В.Н. Цыганенко
Омск 2021


Оглавление

Введение 3

Часть 1. Методика решения 4

Часть 2. Структура данных 5

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

Часть 4. Текст программы 7

Вывод 10


Список литературных источников 11

Введение

Задача РГР – разработка программы средней вычислительной сложности с целью отработки самостоятельной разработки структуры данных и алгоритма. Программа должны быть реализована с использованием языка программирования и IDE по усмотрению студента. Пользовательский интерфейс может быть разработан либо как консольное приложение, либо на основе GUI.

Задание: Две кучи. Имеется N (от 3 до 23) камня с целочисленными весами W1; W2; : : : ; WN . Требуется разложить их на две кучи таким образом, чтобы разница в весе куч была минимальной. Каждый камень должен принадлежать ровно одной куче.

Часть 1. Методика решения

Наша задание является оптимизационной версией разбиения множества чисел. Задача разбиения множества чисел — это задача определения, можно ли данное мультимножество S положительных целых чисел разбить на два подмножества S1 и S2, таких, что сумма чисел из S1 равна сумме чисел из S2. Хотя задача разбиения чисел является NP-полной, существует решение псевдополиномиального времени методом динамического программирования существуют эвристические алгоритмы решения для многих конкретных задач либо оптимально, либо приближённо. По этой причине задачу называют ``простейшей NP-трудной задачей''. Существует оптимизационная версия задачи разбиения, в которой требуется разбить мультимножество S на два подмножества S1 и S2, таких, что разность между суммой элементов S1 и суммой элементов S2 минимальна. Оптимизационная версия является NP-трудной задачей, но на практике может быть решена эффективно.



Часть 2. Структура данных


При решении задачи, была разработана структура данных- односвязный список, в которой были реализованы методы: вставки, удаления, получения значения элемента, получения длины списка и сортировки.

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



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


Для решения задачи был выбран алгоритм полного перебор, так как по условию задачи количество элементов варьируется от 3 до 23, в связи с чем использование алгоритмов динамического программирования являются излишними, так как они не дадут существенного ускорения алгоритма, но при этом могут дать не самый оптимальный ответ, в отличии от алгоритма полного перебора, который всегда дает самый оптимальный ответ.

Описание алгоритма: Входной список сортируется от большего к меньшему значению, для каждой итерации вычисляем сумму каждой кучи, а затем добавляем элемент в кучу с минимальной суммой. Найдем все группы элементов (x,y) , где x находится в куче 1, y -в куче 2 и |x-y| < |sum(heap1) - sum(heap2)|, меняем значения x и y, проверяем больше ли минимальное значение в куче с наибольшей суммой, чем разница между кучами, если это так, переносим его в другую кучу.



Часть 4. Текст программы



Рисунок 1 – Список и его методы


Рисунок 2 – Остальные методы списка


Рисунок 3 – алгоритм решения задачи


Рисунок 4 – Результат работы программы



Вывод


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

Список литературных источников



1. Ахо Альфред В., Хопкрофт Джон, Ульман Джеффри Д. Структуры данных и алгоритмы: Пер. с англ.: Уч.пос.- М.: Издательский дом “Вильямс”, 2000.

2. Белик, А. Г. Проектирование и архитектура программных систем: учеб. пособие / А. Г. Белик, В. Н. Цыганенко; Минобрнауки России, ОмГТУ. – Омск: Изд-во ОмГТУ, 2016. – 96 с.



3. Белик, А. Г. Теория и технология программирования: учеб. пособие / А. Г. Белик, В. Н. Цыганенко; Минобрнауки России, ОмГТУ. – Омск: Изд-во ОмГТУ, 2013. – 88 с.


Скачать файл (41.8 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации