Дослідження алгоритмів з використанням різних структур даних: черг та графів

Размещено на http://www.allbest.ru

Зміст

черга граф програмування

Вступ

1. Завдання 1

1.1 Теоретична частина

1.2 Алгоритм розв'язку

1.3 Система тестів

1.4 Специфікація програми

1.5 Результати виконання програми

2. Завдання 2

2.1 Теоретична частина

2.2 Алгоритм розв'язку

2.3 Система тестів

2.4 Специфікація програми

2.5 Результати виконання програми

Висновки

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

Додаток

Вступ

Структура даних - програмна одиниця, що дозволяє зберігати і обробляти безліч однотипних і / або логічно пов'язаних даних в обчислювальній техніці. Для додавання, пошуку, зміни та видалення даних структура даних надає деякий набір функцій, складових її інтерфейс. Структура даних часто є реалізацією будь-якого абстрактного типу даних.

При розробці програмного забезпечення велику роль грає проектування сховища даних і представлення всіх даних у вигляді безлічі пов'язаних структур даних.

Добре спроектоване сховище даних оптимізує використання ресурсів (таких як час виконання операцій, на обсяг оперативної пам'яті, число звернень до дискових накопичувачів), необхідних для виконання найбільш критичних операцій.

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

Різні види структур даних підходять для різних додатків; деякі з них мають вузьку спеціалізацію для певних завдань. Наприклад, B-дерева зазвичай підходять для створення баз даних, в той час як хеш-таблиці використовуються повсюдно для створення різного роду словників, наприклад, для відображення доменних імен в інтернет-адреси комп'ютерів.

При розробці програмного забезпечення складність реалізації і якість роботи програм істотно залежить від правильного вибору структур даних. Це розуміння дало початок формальним методам розробки та мов програмування, в яких саме структури даних, а не алгоритми, є наріжним архітектури програмного засобу. Велика частина таких мов володіє певним типом модульності, що дозволяє структурам даних безпечно використовуватися в різних додатках. Об'єктно-орієнтовані мови, такі як Java, C # і C + +, є прикладами такого підходу.

Багато класичних структур даних представлені в стандартних бібліотеках мов програмування або безпосередньо вбудовані в мови програмування. Наприклад, структура даних хеш-таблиця вбудована в мови програмування Lua, Perl, Python, Ruby, Tcl і ін. Широко використовується стандартна бібліотека шаблонів STL мови C + +.

1. Завдання 1

1.1 Теоретична частина

Черга в програмуванні -- динамічна структура даних, що працює за принципом "перший прийшов - перший пішов" (англ. FIFO -- first in, first out). У черги є голова (англ. head) та хвіст (англ. tail). Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові.

Така черга повністю аналогічна звичній "базарній" черзі, в якій хто перший встав в неї, той першим буде обслуженим (але, на відміну від реальної черги, імовірність пройти поза чергою виключена)

Основні операції з чергою

англ. enqueue -- "поставити в чергу". Операція додавання елемента в "хвіст" черги. При цьому довжина черги збільшується на одиницю. Якщо відбувається намагання додати елемент у вже заповнену чергу, відбувається її переповнення (англ. queue overflow).

англ. dequeue -- "отримання з черги". Операція, яка повертає елемент з голови та видаляє його з черги, таким чином встановлюючи голову на наступний за видаленим елемент та зменшуючи довжину на одиницю. При намаганні видалити елемент з пустої черги, виникає ситуація "незаповнення" (англ. queue underflow).

Реалізація на мовах програмування

Черга може бути реалізована за допомогою масива Q[1...n], в якому зберігаються дані та двох додаткових змінних head[Q] та tail[Q], в яких зберігаються індекси відповідно "голови" та "хвоста" черги, lenght[Q] -- довжина черги.

1.2 Алгоритм розв'язку

Рис.1.2.1. Блок-схема алгоритму роботи програми 1

1.3 Система тестів

У випадку коли T < t1 або T < t2 або будь-яка змінна з вхідних даних = 0 вхідні дані задані невірно. У інших випадках йде обрахунок і виводиться на екран результат у вигляді списку, в якому вказаний час та подія яка в цей час відбулася.

Результати виконання показано в відповідному розділі.

У випадку введення невірних даних програма видає відповідне повідомлення про помилку.

1.4 Специфікація програми

В клас стандартного діалогового вікна було додано такі елементи:

Edit1- поле для вводу кількості покупців m

Edit2- поле для вводу t1

Edit3- поле для вводу t2

Edit4- поле для вводу t3

Edit5- поле для вводу t4

Edit6- поле для вводу t5

Edit7- поле для вводу періоду часу на якому проводиться дослідження T

StaticText1- текстове поле, в якому виводиться стан черги після виконання програми

Button1 - кнопка за допомогою якої відкривається вікно з детальною умовою поставленої задачі

Button2 - кнопка за допомогою якої формується черга та виводиться результат роботи програми на екран

StaticText - текстові поля які виводять допоміжні повідомлення

В клас стандартного діалогового вікна було додано такі функції:

afx_msg void OnBnClickedButton1() - функція для керування кнопкою 1

afx_msg void OnBnClickedButton2() - функція для керування кнопкою 2

void dodavsja() - функція, що додає до черги покупця

void obslygily() - функція, що вилучає з черги покупця

void pilgoviy() - функція, що додає до черги пільгового покупця

void zvaluv() - функція, що вилучає з черги покупця, який не витримав очікування в черзі

В клас стандартного діалогового вікна було додано такі змінні:

int now_get1 - Змінна для запам'ятовування покупця, який зараз додається до черги

int now_get2 - Змінна для запам'ятовування покупця, який зараз вилучається з черги

int now_time - Змінна, в якій задається текучий час

int real1 - Змінна, в яку записується випадкове значення, з діапазону 1..t1

int real2 - Змінна, в яку записується випадкове значення, з діапазону 1..t2

int real3 - Змінна, в яку записується випадкове значення, з діапазону 1..t3

int real4 - Змінна, в яку записується випадкове значення, з діапазону 1..t4

CString zalushok - рядок для виводу залишку черги

CString str1 - рядок для виводу процесу додавання та обслуговування покупців.

1.5 Результати виконання програми

Рис 1.5.1. Результат виконання програми з вхідними даними 1

Рис 1.5.2. Результат виконання програми з вхідними даними 2

2. Завдання 2

2.1 Теоретична частина

Граф -- це сукупність об'єктів із зв'язками між ними.

Об'єкти розглядаються як вершини, або вузли графу, а зв'язки -- як дуги, або ребра. Для різних областей використання види графів можуть відрізнятися орієнтовністю, обмеженнями на кількість зв'язків і додатковими даними про вершини або ребра.

Велика кількість структур, які мають практичну цінність в математиці та інформатиці, можуть бути представлені графами. Наприклад, будову Вікіпедії можна змоделювати за допомогою орієнтованого графу, в якому вершини -- це статті, а дуги (орієнтовані ребра) -- посилання на інші статті.

Першою працею з теорії графів як математичної дисципліни вважають статтю Леонарда Ейлера (1736), у якій розглядалася задача проКенігсбергські мости. Наступний імпульс теорія графів отримала близько 100 років потому з розвитком досліджень по електричним мережам, кристалографії, органічній хімії та іншим наукам.

Теорія графів не має стійкої термінології. В різних статтях під одними й тими ж термінами розуміють різні поняття. Наведені нижче визначення є одними з найбільш розповсюджених.

Граф або неорієнтований граф G -- це впорядкована пара G: = (V,E), для якої виконуються наступні умови:

V -- множина вершин або вузлів,

E -- множина пар (у випадку неорієнтованого графу -- невпорядкованих) вершин, які називають ребрами.

V (і так само E) зазвичай вважаються скінченними множинами. Велика кількість результатів, отриманих для скінченних графів, невірна (або інша) для нескінченних графів. Це пов'язано з тим, що певний набір ідей стає хибним у випадку нескінченних множин.

Граф (геометричний граф) -- це фігура на площині, яка складається з непорожньої скінченної множини V точок (вершин) і скінченної множини E орієнтованих чи не орієнтованих ліній (ребер), що з'єднують деякі пари вершин.

2.2 Алгоритм розв'язку

Рис 2.2.1. Блок-схема алгоритму роботи програми 2

2.3 Система тестів

Залежно від вхідного файлу з даними створюється певна структура даних (граф) з вершинами, що задані у вхідному файлі та з ребрами (зв'язками) між вершинами, які задаються парою вершин у вхідному файлі.

Вигляд вхідного файлу (файл input.txt):

<Вершина1><пробіл><Вершина2> <ентер>

<Вершина1><пробіл><Вершина2> <ентер>

……

<Вершина1><пробіл><Вершина2> <ентер>

У випадку введення невірних даних (наприклад тексту) програма їх ігнорує.

Всі дані з файлу зберігаються у графі під час роботи програми. При перезагрузці програми необхідно знову сформувани структуру даних з файлу.

Результати виконання показано у відповідному розділі.

2.4 Специфікація програми

В клас стандартного діалогового вікна було додано такі елементи:

Button1 - кнопка за допомогою якої відкривається вікно з детальною умовою поставленої задачі

Button2 - кнопка за допомогою якої формується граф з вхідного файлу та виводиться результат обрахунку на екран

StaticText1- текстове поле яке виводить допоміжне повідомлення (Необхідно )

StaticText2- текстове поле яке виводить кількість необхідних поліцейських

StaticText3- текстове поле яке виводить допоміжне повідомлення (поліцейських.)

StaticText - текстове поле яке виводить допоміжне повідомлення

В клас стандартного діалогового вікна було додано такі функціїї:

afx_msg void OnBnClickedButton1() - функція для керування кнопкою 1

afx_msg void OnBnClickedButton2() - функція для керування кнопкою 2

В клас стандартного діалогового вікна було додано такі змінні:

CString text1 - змінна, що зберігає допоміжне повідомлення (Необхідно )

int int1 - змінна, в яку записується кількість необхідних поліцейських

CString text2 - звінна, що зберігає допоміжне повідомлення (поліцейських.)

int from[500] - змінна, в яку записуються вершини графа

int to[500] - змінна, в яку записуються зв'язки(ребра) графа

2.5 Результати виконання програми

Рис. 2.5.1. Текстовий файл з вхідними даними та граф, який під цим розуміється

Рис. 2.3. Результат роботи програми

Висновки

Виконуючи дану курсову роботу, я закріпив основи роботи з такими структурами даних як черга та граф. Вивчив методи і принципи роботи з ними і алгоритми роботи черги та графа. Закріпив знання про створення проектів MFC.

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

ГОСТ 19.701-90 (ИСО 5807-85) ЕСПД. Схемы алгоритмов и прог-рамм, данных и систем. Условные обозначения и правила выполнения.

Берзтисс А.Т. Структуры данных . - М.:Статистика, 1974 - 408 с.

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

Уильям Топп, Уильям Форд. Структуры данных в С++. - М.:Бином, 2000 - 700 с.

Eppstein, David (1999), "Spanning trees and spanners", in Sack, J.-R. & Urrutia, J., Handbook of Computational Geometry, Elsevier, pp. 425-461; Mareљ, Martin (2004), "Two linear time algorithms for MST on minor closed graph classes", Archivum mathematicum Т. 40 (3): 315-320.

http://ru.wikipedia.org/wiki/Структура_данных

http://uk.wikipedia.org/wiki/Черга

http://uk.wikipedia.org/wiki/Граф_(Структура_даних)

Додаток

Загальне меню

/**************************************************************\

FILE: IPZ_TEODOROVYCH1Dlg.h

AUTHOR: Teodorovych Taras

DESCRIPTION: Course_work

CLASSES: CIPZ_TEODOROVYCH1App

COPYRIGHT: Copyright

\**************************************************************/

#pragma once

// диалоговое окно CIPZ_TEODOROVYCH1Dlg

class CIPZ_TEODOROVYCH_course1Dlg : public CDialog

{

// Создание

public:

CIPZ_TEODOROVYCH_course1Dlg(CWnd* pParent = NULL);// стандартный конструктор

// Данные диалогового окна

enum { IDD = IDD_IPZ_TEODOROVYCH1_DIALOG };

protected:

virtual void DoDataExchange(CDataExchange* pDX);// поддержка DDX/DDV

// Реализация

protected:

HICON m_hIcon;

// Созданные функции схемы сообщений

virtual BOOL OnInitDialog();

afx_msg void OnSysCommand(UINT nID, LPARAM lParam);

afx_msg void OnPaint();

afx_msg HCURSOR OnQueryDragIcon();

DECLARE_MESSAGE_MAP()

public:

afx_msg void OnBnClickedButton1();

afx_msg void OnBnClickedButton2();

};

/**************************************************************\

FILE: IPZ_ TEODOROVYCH1Dlg.cpp

AUTHOR: Teodorovych Taras

DESCRIPTION: Course_work

CLASSES: CAboutDlg

CIPZ_TEODOROVYCH1Dlg

COPYRIGHT: Copyright

\**************************************************************/

#include "stdafx.h"

#include "IPZ_TEODOROVYCH1.h"

#include "IPZ_TEODOROVYCH1Dlg.h"

#include "MyDialog1.h"

#include "MyDialog2.h"

#ifdef _DEBUG

#define new DEBUG_NEW

#endif

MyDialog1 obj1;

MyDialog2 obj2;

// Диалоговое окно CAboutDlg используется для описания сведений о приложении

class CAboutDlg : public CDialog

{

public:

CAboutDlg();

// Данные диалогового окна

enum { IDD = IDD_ABOUTBOX };

protected:

virtual void DoDataExchange(CDataExchange* pDX); // поддержка DDX/DDV

// Реализация

protected:

DECLARE_MESSAGE_MAP()

};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)

{

}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)

{

CDialog::DoDataExchange(pDX);

}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)

END_MESSAGE_MAP()

// диалоговое окно CIPZ_Tostogan_course1Dlg

CIPZ_TEODOROVYCH1Dlg::CIPZ_TEODOROVYCHDlg(CWnd* pParent /*=NULL*/)

: CDialog(CIPZ_TEODOROVYCHDlg::IDD, pParent)

{

m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);

}

void CIPZ_TEODOROVYCHDlg::DoDataExchange(CDataExchange* pDX)

{

CDialog::DoDataExchange(pDX);

}

BEGIN_MESSAGE_MAP(CIPZ_TEODOROVYCH1Dlg, CDialog)

ON_WM_SYSCOMMAND()

ON_WM_PAINT()

ON_WM_QUERYDRAGICON()

//}}AFX_MSG_MAP

ON_BN_CLICKED(IDC_BUTTON1, &CIPZ_Tostogan_course1Dlg::OnBnClickedButton1)

ON_BN_CLICKED(IDC_BUTTON2, &CIPZ_Tostogan_course1Dlg::OnBnClickedButton2)

END_MESSAGE_MAP()

// обработчики сообщений CIPZ_TEODOROVYCH1Dlg

BOOL CIPZ_TEODOROVYCHDlg::OnInitDialog()

{

CDialog::OnInitDialog();

// Добавление пункта ''О программе...'' в системное меню.

// IDM_ABOUTBOX должен быть в пределах системной команды.

ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);

ASSERT(IDM_ABOUTBOX < 0xF000);

CMenu* pSysMenu = GetSystemMenu(FALSE);

if (pSysMenu != NULL)

{

CString strAboutMenu;

strAboutMenu.LoadString(IDS_ABOUTBOX);

if (!strAboutMenu.IsEmpty())

{

pSysMenu->AppendMenu(MF_SEPARATOR);

pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);

}

}

// Задает значок для этого диалогового окна. Среда делает это автоматически,

// если главное окно приложения не является диалоговым

SetIcon(m_hIcon, TRUE);// Крупный значок

SetIcon(m_hIcon, FALSE);// Мелкий значок

// TODO: добавьте дополнительную инициализацию

obj1.Create(IDD_DIALOG1, this);

obj1.ShowWindow(SW_HIDE);

obj2.Create(IDD_DIALOG2, this);

obj2.ShowWindow(SW_HIDE);

return TRUE; // возврат значения TRUE, если фокус не передан элементу управления

}

void CIPZ_TEODOROVYCHDlg::OnSysCommand(UINT nID, LPARAM lParam)

{

if ((nID & 0xFFF0) == IDM_ABOUTBOX)

{

CAboutDlg dlgAbout;

dlgAbout.DoModal();

}

else

{

CDialog::OnSysCommand(nID, lParam);

}

}

// При добавлении кнопки свертывания в диалоговое окно нужно воспользоваться приведенным ниже кодом,

// чтобы нарисовать значок. Для приложений MFC, использующих модель документов или представлений,

// это автоматически выполняется рабочей средой.

void CIPZ_TEODOROVYCHDlg::OnPaint()

{

if (IsIconic())

{

CPaintDC dc(this); // контекст устройства для рисования

SendMessage(WM_ICONERASEBKGND, reinterpret_cast<WPARAM>(dc.GetSafeHdc()), 0);

// Выравнивание значка по центру клиентского прямоугольника

int cxIcon = GetSystemMetrics(SM_CXICON);

int cyIcon = GetSystemMetrics(SM_CYICON);

CRect rect;

GetClientRect(&rect);

int x = (rect.Width() - cxIcon + 1) / 2;

int y = (rect.Height() - cyIcon + 1) / 2;

// Нарисуйте значок

dc.DrawIcon(x, y, m_hIcon);

}

else

{

CDialog::OnPaint();

}

}

// Система вызывает эту функцию для получения отображения курсора при перемещении

// свернутого окна.

HCURSOR CIPZ_TEODOROVYCHDlg::OnQueryDragIcon()

{

return static_cast<HCURSOR>(m_hIcon);

}

void CIPZ_TEODOROVYCHDlg::OnBnClickedButton1()

{

obj1.ShowWindow(SW_SHOW);

// TODO: добавьте свой код обработчика уведомлений

}

void CIPZ_TEODOROVYCH1Dlg::OnBnClickedButton2()

{

obj2.ShowWindow(SW_SHOW);

// TODO: добавьте свой код обработчика уведомлений

}

Завдання 1

/**************************************************************\

FILE: MyDialog1.h

AUTHOR: Teodorovych Taras

DESCRIPTION: Course_work

CLASSES: MyDialog1

COPYRIGHT: Copyright

\**************************************************************/

#pragma once

// диалоговое окно MyDialog1

class MyDialog1 : public CDialog

{

DECLARE_DYNAMIC(MyDialog1)

public:

MyDialog1(CWnd* pParent = NULL); // стандартный конструктор

virtual ~MyDialog1();

// Данные диалогового окна

enum { IDD = IDD_DIALOG1 };

protected:

virtual void DoDataExchange(CDataExchange* pDX); // поддержка DDX/DDV

DECLARE_MESSAGE_MAP()

public:

afx_msg void OnBnClickedButton1();

afx_msg void OnBnClickedButton3();

int m;

int t1;

int t2;

int t3;

int t4;

int t;

int

now_get1,

now_get2,

now_time;

int

real1,

real2,

real3,

real4;

void dodavsja();

void obslygily();

void pilgoviy();

void zvaluv();

CString zalushok;

CString str1;

};

/**************************************************************\

FILE: MyDialog1.cpp

AUTHOR: Teodorovych Taras

DESCRIPTION: Course_work

CLASSES: MyDialog1

COPYRIGHT: Copyright

\**************************************************************/

// MyDialog1.cpp: файл реализации

//

#include "stdafx.h"

#include "IPZ_TEODOROVYCH1.h"

#include "MyDialog1.h"

#include <stdlib.h>

#include <time.h>

// диалоговое окно MyDialog1

IMPLEMENT_DYNAMIC(MyDialog1, CDialog)

MyDialog1::MyDialog1(CWnd* pParent /*=NULL*/)

: CDialog(MyDialog1::IDD, pParent)

, m(0)

, t1(0)

, t2(0)

, t3(0)

, t4(0)

, t(0)

, zalushok(_T(""))

, str1(_T(""))

{

}

MyDialog1::~MyDialog1()

{

}

void MyDialog1::DoDataExchange(CDataExchange* pDX)

{

CDialog::DoDataExchange(pDX);

DDX_Text(pDX, IDC_EDIT1, m);

DDX_Text(pDX, IDC_EDIT2, t1);

DDX_Text(pDX, IDC_EDIT3, t2);

DDX_Text(pDX, IDC_EDIT4, t3);

DDX_Text(pDX, IDC_EDIT5, t4);

DDX_Text(pDX, IDC_EDIT6, t);

DDX_Text(pDX, IDC_STATIC2, zalushok);

DDV_MinMaxInt(pDX, m, 1, 999);

DDV_MinMaxInt(pDX, t1, 1, 9999);

DDV_MinMaxInt(pDX, t2, 1, 9999);

DDV_MinMaxInt(pDX, t3, 1, 9999);

DDV_MinMaxInt(pDX, t4, 1, 9999);

DDV_MinMaxInt(pDX, t, 1, 9999);

DDX_Text(pDX, IDC_EDIT7, str1);

}

BEGIN_MESSAGE_MAP(MyDialog1, CDialog)

ON_BN_CLICKED(IDC_BUTTON1, &MyDialog1::OnBnClickedButton1)

ON_BN_CLICKED(IDC_BUTTON3, &MyDialog1::OnBnClickedButton3)

END_MESSAGE_MAP()

// обработчики сообщений MyDialog1

void MyDialog1::OnBnClickedButton1()

{

MessageBox("У магазині стоїть черга з m покупців. Час обслуговування покупця з черги - це випадкове ціле число в діапазоні від 1 до t1. Час додавання нового покупця до черги - це випадкове ціле число в діапазоні від 1 до t2.\r\nПромоделювати стан черги:\r\nа) вивести повідомлення про час виникнення подій ( обслуговування та додавання покупця ) за період часу T (T >> t1, T >> t2); \r\nб) показати залишок черги;\r\nв) розв'язати задачу, передбачивши, що через випадковий час від 1 до t3 до початку черги додається „пільговий” покупець, який обслуговується першим, а через випадковий час від 1 до t4 не витримує та йде з черги останній покупець.", "Умова задачі 3.1", MB_OK);

// TODO: добавьте свой код обработчика уведомлений

}

void MyDialog1::OnBnClickedButton3()

{

UpdateData();

srand(time(0));

str1.Empty();

now_get1 = 1;

now_get2 = 1;

now_time = 0;

if((t <= t1) || (t <= t2))

MessageBox("Введіть Т більшим за t1 та t2..", "", MB_OK);

else

{

str1 += "*** Час - Подія ***\r\n";

real1 = rand()%(t1) + 1;

real2 = rand()%(t2) + 1;

real3 = rand()%(t3) + 1;

real4 = rand()%(t4) + 1;

bool

sudden_escape;

sudden_escape = false;

dodavsja();

while((now_get2 <= m) && (now_time <= t) && (real1 > 0) && (real2 > 0))

{

if((now_time < real3) && (now_time < real4))

{

while(((real2 <= real1) && (now_get1 <= m) && (now_time <= t) ) || (sudden_escape))

{

real1 -= real2;

dodavsja();

sudden_escape = false;

}

}

if(now_get1 > m)

real2 = 9999;

if((real1 < real2) && (now_get1 <= now_get2))

{

sudden_escape = true;

}

if((real1 < real2) && (now_get1 > now_get2) && (now_time <= t) )

{

obslygily();

}

if(now_time >= real3)

{

pilgoviy();

real3 = 9999;

}

if(now_time >= real4)

{

zvaluv();

real4 = 9999;

}

}

////////////////////////////////////////////

}

char

temp[50];

int

a = now_get2,

b = now_get1;

int

tmp;

zalushok.Empty();

if(a < b)

{

zalushok += "В даний момент в черзі стоять покупці ";

while (a < b)

{

for(int i = 0; i < 50; i++)

temp[i] = 0;

if(a < 10)

{

temp[0] = a + '0';

}

else

{

if(a < 100)

{

temp[0] = a/10 +'0';

temp[1] = a%10 +'0';

}

else

{

temp[2] = a%10 +'0';

tmp = a/10;

temp[1] = a%10 + '0';

temp[0] = a/10 + '0';

}

}

zalushok += temp;

zalushok += ", ";

a++;

}

zalushok += "\r\n";

}

else

zalushok += "В черзі зараз немає покупців.\r\n";

a = b;

if(a <= m)

{

zalushok += "До черги ще не підійшли покупці ";

while (a <= m)

{

for(int i = 0; i < 50; i++)

temp[i] = 0;

if(a < 10)

{

temp[0] = a + '0';

}

else

{

if(a < 100)

{

temp[0] = a/10 +'0';

temp[1] = a%10 +'0';

}

else

{

temp[2] = a%10 +'0';

tmp = a/10;

temp[1] = a%10 + '0';

temp[0] = a/10 + '0';

}

}

zalushok += temp;

zalushok += ", ";

a++;

}

zalushok += "\r\n";

}

UpdateData(false);

// TODO: добавьте свой код обработчика уведомлений

}

void MyDialog1::dodavsja()

{

if(now_get1 <= m)

{

char

temp[50];

for(int i = 0; i < 50; i++)

temp[i] = 0;

now_time += real2;

if(now_time < 10)

{

temp[0] = now_time + '0';

}

else

{

if(now_time < 100)

{

temp[0] = now_time/10 +'0';

temp[1] = now_time%10 +'0';

}

else

{

temp[2] = now_time%10 +'0';

int tmp = now_time/10;

temp[1] = tmp%10 + '0';

temp[0] = tmp/10 + '0';

}

}

str1 += temp;

for(int i = 0; i < 50; i++)

temp[i] = 0;

str1 += " (1..t2) До черги додався покупець ";

if(now_get1 < 10)

{

temp[0] = now_get1 + '0';

}

else

{

if(now_get1 < 100)

{

temp[0] = now_get1/10 +'0';

temp[1] = now_get1%10 +'0';

}

else

{

temp[2] = now_get1%10 +'0';

int tmp = now_get1/10;

temp[1] = tmp%10 + '0';

temp[0] = tmp/10 + '0';

}

}

now_get1++;

str1 += temp;

for(int i = 0; i < 50; i++)

temp[i] = 0;

str1 += ".\r\n";

real2 = rand()%(t2) + 1;

}

}

void MyDialog1::obslygily()

{

if(now_get2 <= m)

{

real2 -= real1;

char

temp[50];

for(int i = 0; i < 50; i++)

temp[i] = 0;

now_time += real1;

if(now_time < 10)

{

temp[0] = now_time + '0';

}

else

{

if(now_time < 100)

{

temp[0] = now_time/10 +'0';

temp[1] = now_time%10 +'0';

}

else

{

temp[2] = now_time%10 +'0';

int tmp = now_time/10;

temp[1] = tmp%10 + '0';

temp[0] = tmp/10 + '0';

}

}

str1 += temp;

for(int i = 0; i < 50; i++)

temp[i] = 0;

str1 += " (1..t1) Обслужили покупця ";

if(now_get2 < 10)

{

temp[0] = now_get2 + '0';

}

else

{

if(now_get2 < 100)

{

temp[0] = now_get2/10 +'0';

temp[1] = now_get2%10 +'0';

}

else

{

temp[2] = now_get2%10 +'0';

int tmp = now_get2/10;

temp[1] = tmp%10 + '0';

temp[0] = tmp/10 + '0';

}

}

now_get2++;

str1 += temp;

for(int i = 0; i < 50; i++)

temp[i] = 0;

str1 += ".\r\n";

real1 = rand()%(t1) + 1;

}

}

void MyDialog1::pilgoviy()

{

if(now_get1 <= m)

{

char

temp[50];

for(int i = 0; i < 50; i++)

temp[i] = 0;

now_time += 2;

if(now_time < 10)

{

temp[0] = now_time + '0';

}

else

{

if(now_time < 100)

{

temp[0] = now_time/10 +'0';

temp[1] = now_time%10 +'0';

}

else

{

temp[2] = now_time%10 +'0';

int tmp = now_time/10;

temp[1] = tmp%10 + '0';

temp[0] = tmp/10 + '0';

}

}

str1 += temp;

for(int i = 0; i < 50; i++)

temp[i] = 0;

str1 += " (1..t3) До черги додався покупець ";

if(now_get1 < 10)

{

temp[0] = now_get1 + '0';

}

else

{

if(now_get1 < 100)

{

temp[0] = now_get1/10 +'0';

temp[1] = now_get1%10 +'0';

}

else

{

temp[2] = now_get1%10 +'0';

int tmp = now_get1/10;

temp[1] = tmp%10 + '0';

temp[0] = tmp/10 + '0';

}

}

now_get1++;

str1 += temp;

for(int i = 0; i < 50; i++)

temp[i] = 0;

str1 += " (пільговий).\r\n";

real2 = rand()%(t2) + 1;

}

}

void MyDialog1::zvaluv()

{

char

temp[50];

for(int i = 0; i < 50; i++)

temp[i] = 0;

now_time += 2;

if(now_time < 10)

{

temp[0] = now_time + '0';

}

else

{

if(now_time < 100)

{

temp[0] = now_time/10 +'0';

temp[1] = now_time%10 +'0';

}

else

{

temp[2] = now_time%10 +'0';

int tmp = now_time/10;

temp[1] = tmp%10 + '0';

temp[0] = tmp/10 + '0';

}

}

str1 += temp;

for(int i = 0; i < 50; i++)

temp[i] = 0;

str1 += " (1..t4) Не витримав та пішов з черги покупець ";

if(now_get2 < 10)

{

temp[0] = now_get2 + '0';

}

else

{

if(now_get2 < 100)

{

temp[0] = now_get2/10 +'0';

temp[1] = now_get2%10 +'0';

}

else

{

temp[2] = now_get2%10 +'0';

int tmp = now_get2/10;

temp[1] = tmp%10 + '0';

temp[0] = tmp/10 + '0';

}

}

now_get2++;

str1 += temp;

for(int i = 0; i < 50; i++)

temp[i] = 0;

str1 += ".\r\n";

}

Завдання 2

/**************************************************************\

FILE: MyDialog2.h

AUTHOR: Teodorovych Taras

DESCRIPTION: Course_work

CLASSES: MyDialog2

COPYRIGHT: Copyright

\**************************************************************/

#pragma once

// диалоговое окно MyDialog2

class MyDialog2 : public CDialog

{

DECLARE_DYNAMIC(MyDialog2)

public:

MyDialog2(CWnd* pParent = NULL); // стандартный конструктор

virtual ~MyDialog2();

// Данные диалогового окна

enum { IDD = IDD_DIALOG2 };

protected:

virtual void DoDataExchange(CDataExchange* pDX); // поддержка DDX/DDV

DECLARE_MESSAGE_MAP()

public:

afx_msg void OnBnClickedButton1();

CString text1;

int int1;

CString text2;

afx_msg void OnBnClickedButton2();

int

from[500],

to[500];

};

/**************************************************************\

FILE: MyDialog2.cpp

AUTHOR: Teodorovych Taras

DESCRIPTION: Course_work

CLASSES: MyDialog2

COPYRIGHT: Copyright

\**************************************************************/

// MyDialog2.cpp: файл реализации

//

#include "stdafx.h"

#include "IPZ_TEODOROVYCH1.h"

#include "MyDialog2.h"

#include <fstream>

#include <iostream>

using namespace std;

// диалоговое окно MyDialog2

IMPLEMENT_DYNAMIC(MyDialog2, CDialog)

MyDialog2::MyDialog2(CWnd* pParent /*=NULL*/)

: CDialog(MyDialog2::IDD, pParent)

, text1(_T(""))

, int1(0)

, text2(_T(""))

{

}

MyDialog2::~MyDialog2()

{

}

void MyDialog2::DoDataExchange(CDataExchange* pDX)

{

CDialog::DoDataExchange(pDX);

DDX_Text(pDX, IDC_STATIC1, text1);

DDX_Text(pDX, IDC_STATIC2, int1);

DDX_Text(pDX, IDC_STATIC3, text2);

}

BEGIN_MESSAGE_MAP(MyDialog2, CDialog)

ON_BN_CLICKED(IDC_BUTTON1, &MyDialog2::OnBnClickedButton1)

ON_BN_CLICKED(IDC_BUTTON2, &MyDialog2::OnBnClickedButton2)

END_MESSAGE_MAP()

// обработчики сообщений MyDialog2

void MyDialog2::OnBnClickedButton1()

{

MessageBox("Задача Ларсона. Нехай G - кінцевий неорієнтований зв'язний граф. Припустимо, що він являє собою систему тунелів, у яких може ховатися втікач. Група з S поліцейських, рухаючись по тунелях, прагне схопити цього втікача, що може рухатися з будь-якою швидкістю, прагнучи, щоб його не спіймали. Знайти мінімальну кількість поліцейських S, що гарантовано спіймають втікача.", "Умова задачі 5.7", MB_OK);

// TODO: добавьте свой код обработчика уведомлений

}

void MyDialog2::OnBnClickedButton2()

{

UpdateData();

ifstream f ("input.txt");

char str1[20];

int i;

int max_versh = 0;

for (i = 0; (i < 500) && (f.eof() != true); i++)

{

f >> from[i];

if (from[i] > max_versh)

max_versh = from[i];

f >> to[i];

if (to[i] > max_versh)

max_versh = to[i];

}

f.close();

int j;

int max_count = 0;

int tmp_count;

for(j = 0; j < max_versh+1; j++)

{

tmp_count = 0;

for(int k = 0; k < i; k++)

{

if(from[k] == j)

tmp_count++;

if(to[k] == j)

tmp_count++;

}

if(tmp_count > max_count)

max_count = tmp_count;

}

int1 = max_count;

text1 += "Необхідно ";

text2 += "поліцейських.";

UpdateData(false);

// TODO: добавьте свой код обработчика уведомлений

}

Размещено на www.allbest.ru