Используемые инструменты

Используемые инструменты

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ Русской ФЕДЕРАЦИИ

Федеральное ГОСУДАРСТВЕННОЕ экономное ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО Проф ОБРАЗОВАНИЯ

«ПОВОЛЖСКИЙ Муниципальный ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ»

Факультет информатики и вычислительной техники

Кафедра ИиСП

Расчётно-графическая работа

По дисциплине «Математическая логика и теория алгоритмов»

Выполнил:

студент группы ПС-21

факультета Информатики

и Вычислительной Техники

специальности «Программная инженерия»

Васильев А.А.

Научный управляющий:

Доцент

Галочкин В.И.

г. Йошкар Используемые инструменты-Ола


Оглавление

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

Описание метода. 4

Структуры данных. 5

Применяемые инструменты.. 6

Литература. 7


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

На пилораму привезли брус длиной L метров. Требуется сделать N распилов. Распилы делят брус на части, длина которых выражается натуральными числами. Цена 1-го распила равна длине распиливаемого бруса. Найти наименьшую цена распила.
Ввод. В первой строке содержатся через пробел Используемые инструменты натуральные числа L (2 ≤ L ≤ 105) и N (N < L) – длина бруса и число распилов.
Вывод. В единственной строке вывести наименьшую цена распилов.

Описание метода

Вероятны два способа распиливания, дозволяющие минимизировать общую цена:

Отпилить брус длиной n, потом разбивая его на брусы единичной длины(малые из вероятных). В таком случае, брус Используемые инструменты длиной N можно будет разбить на N-1 частей. Мы будем разделять пополам его до того времени, пока не получим все брусы единичной длины.

2. Распиливать напополам начальный брус. Этот способ эффективен при условии что N > L/2 (почти всегда), тк цена первого распила всегда схожа, мы не тратим излишней цены на отпиливание бруса наименьшего Используемые инструменты размера, а сходу делим его напополам, повторяя данное действие для всех следующих брусов.

На каждом шаге распиливания мы прибавляем длину распиливаемого бруса к общей цены, также увеличиваем счетчик распилов (n) на единицу. Если количество распилов будет равно N, то задачка решена.

Программка генерирует дерево, демонстрирующее последовательность распилов бруса Используемые инструменты(сверху).

Дерево визуализируется с помощью утилиты graphviz, из записанного графа в формате .doc получаем картину в формате .png.

Пример визуализированного дерева с помощью graphviz:

На рисунках показана очередность распилов (сверху вниз) для 2-ух брусов (длиной 100 и 10 метров).

Структуры данных

Считывание из файла происходит последующим образом:

bool ReadFromFile(const std::string & inputFileName Используемые инструменты, int & l, int & n)

{

std::ifstream inputFile(inputFileName);

inputFile >> l;

inputFile >> n;

if (l > 100000 || l = 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("graph Используемые инструменты1.txt");

std::ofstream secondGraph("graph2.txt");

std::vector first;

std::vector 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++


ispravte-oshibki-v-ispolzovanii-ustojchivih-slovosochetanij.html
stat.txt
ispolzovanie-prirodnih-resursov-chelovekom.html