МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное ГОСУДАРСТВЕННОЕ бюджетное ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ»
Факультет информатики и вычислительной техники
Кафедра ИиСП
Расчётно-графическая работа
По дисциплине «Математическая логика и теория алгоритмов»
Выполнил:
студент группы ПС-21
факультета Информатики
и Вычислительной Техники
специальности «Программная инженерия»
Васильев А.А.
Научный руководитель:
Доцент
Галочкин В.И.
г. Йошкар-Ола
Оглавление
Постановка задачи. 3
Описание алгоритма. 4
Структуры данных. 5
Используемые инструменты.. 6
Литература. 7
Постановка задачи
| На пилораму привезли брус длиной L метров. Требуется сделать N распилов. Распилы делят брус на части, длина которых выражается натуральными числами. Стоимость одного распила равна длине распиливаемого бруса. Определить минимальную стоимость распила. |
| Ввод. В первой строке содержатся через пробел натуральные числа L (2 ≤ L ≤ 105) и N (N < L) – длина бруса и число распилов. |
| Вывод. В единственной строке вывести минимальную стоимость распилов. |
Описание алгоритма
Возможны два метода распиливания, позволяющие минимизировать общую стоимость:
Отпилить брус длиной n, затем разбивая его на брусы единичной длины(минимальные из возможных). В таком случае, брус длиной N можно будет разбить на N-1 частей. Мы будем делить напополам его до тех пор, пока не получим все брусы единичной длины.
2. Распиливать пополам исходный брус. Этот метод эффективен при условии что N > L/2 (в большинстве случаев), тк стоимость первого распила всегда одинакова, мы не тратим лишней стоимости на отпиливание бруса меньшего размера, а сразу делим его пополам, повторяя данное действие для всех последующих брусов.
На каждом шаге распиливания мы прибавляем длину распиливаемого бруса к общей стоимости, а также увеличиваем счетчик распилов (n) на единицу. Если количество распилов будет равно N, то задача решена.
Программа генерирует дерево, демонстрирующее последовательность распилов бруса(сверху).
Дерево визуализируется при помощи утилиты graphviz, из записанного графа в формате.doc получаем картинку в формате.png.
Пример визуализированного дерева при помощи graphviz:
На рисунках показана очередность распилов (сверху вниз) для двух брусов (длиной 100 и 10 метров).
Структуры данных
Считывание из файла происходит следующим образом:
bool ReadFromFile(const std:: string & inputFileName, int & l, int & n)
{
std:: ifstream inputFile(inputFileName);
inputFile >> l;
inputFile >> n;
if (l > 100000 || l < 2 || n >= l)
{
std:: cout << "Error: incorrect input" << std:: endl;
return false;
}
return true;
}
Структура программы:
int main ()
{
Application application;
application.Visualize();
return 0;
}
struct Application
{
Application();
Font font;
Text text;
RenderWindow * window;
State state;
bool isStateChanged;
Buttons buttons;
ProgramData programData; //данные самой задачи
int result;
bool isResultCalculated = false;
void Update (); //метод, который обновляет состояние окна
void Draw (); //метод, который отвечает за отрисовку содержимого окна
void Visualize(); //метод, запускающий цикл самого приложения
};
void Application::Visualize()
{
while (window->isOpen() && state!= EXIT_PROGRAM)
{
window->clear(sf::Color::Black);
Update();
Draw();
window->display();
}
delete(programData.startNode);
delete(window);
}
struct ProgramData
{
bool load (); //считывание из файла
Node * startNode = new Node(); //верхний узел графа
int result; //результат
bool isResultCalculated = false;
bool isResultSaved = false;
bool isResultGraphSaved = false;
int length; //вводимая длина бруса
int nCuts; //вводимое количество распилов
};
int CalculateResult(int l, int n, Node & startNode)
{
std:: ofstream firstGraph("graph1.txt");
std:: ofstream secondGraph("graph2.txt");
std:: vector <Node> first;
std:: vector <Node> second;
int firstResult = StartCut(l, n, false, first);
int secondResult = StartCut(l, n, true, second);
if (firstResult <= secondResult)
{
startNode = first[0];
return firstResult;
}
startNode = second[0];
return secondResult;
}
Используемые инструменты
1. Язык C++