Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2011
Тип роботи:
Курсова робота
Предмет:
Інженерія програмного забеспечення
Частина тексту файла (без зображень, графіків і формул):
Міністерство Освіти і Науки
Національний Університет «Львівська Політехніка»
кафедра ЕОМ
Курсова робота
з предмету: «Інженерія програмного забезпечення»
Львів 2011
Завдання на курсову роботу :
3.2. Автостоянка має одну полосу, наякійможе бути розмiщено до 10 автомобiлiв. Машинив'їжджають з пiвденногокiнця стоянки i від'їжджають з пiвнiчного. Якщоавтомобiльвласника, щоприйшов на стоянку забратийого, не розташованийпiвнiчнiше за всі решту, то всiавтомобiлi, що стоять пiвнiчнiшейого, виїжджаютьiззупинки, потiмвиїжджаєйого машина і всімашиниповертаються в початковому порядку. Якщо машина залишає гараж, то всiмашинирозташованiпiвденнiше, перемiщаються вперед на стiлькипозицій, скiльки є вiльнихмiсць в пiвнiчнiйчастинi. Написатипрограмузчитуваннягрупирядків, кожний з якихмiститьлітеру "A" для прибуття i літеру "D" для вiдправлення, а також номер машини. Машиниприбувають i вiдправляються в порядку, щозадаєцей список рядків. Програмамаєвидаватиповiдомленняпри кожному прибуттіабовiдправленнімашини. При прибуттімашини в ньому повинно говоритись, чи є настоянцівiльнемiсце. Якщовiльнемiсцевiдсутнє, машина чекає до тих пiр, покивоно не звiльниться, або до моменту зчитування рядка, щоповідомляє про вiдправленняцьогоавтомобiля. Якщоз'являєтьсявiльнемiсце, повинно видаватисьiншеповiдомлення. При вiдправленнiавтомобiляповiдомлення повинно мiстити в собiкiлькiстьперемiщеньмашини в серединi стоянки (включаючиїївiдправлення, але не прибуття; це число рiвне 0, якщо машина булавiдправленапід час очiкуваннявільногомісця).
5.8. Усередині піраміди Хеопса є N кімнат, в яких встановлено M пристроїв, кожний з яких складається з двох модулів, що розташовуються в різних кімнатах, і призначені для швидкого переміщення між парою кімнат, у яких встановлені ці модулі. Переміщення відбувається за 0.5 умовних одиниць часу. У початковий момент часу модулі всіх пристроїв переходять у "підготовчий режим". Кожний з модулів має деякий свій цілочисельний період, під час якого він знаходиться в "підготовчому режимі". Після закінчення цього часу модуль миттєво "спрацьовує", після чого знову переходить у "підготовчий режим". Пристроєм можна скористатися тільки в той момент, коли одночасно "спрацьовують" обидва його модуля. Індіана Джонс зумів проникнути в гробницю фараона. Обстеживши її, він включив пристрої і зібрався йти, але в цей момент прокинувся охоронець гробниці. Тепер Джонсу необхідно якнайшвидше потрапити в кімнату N, у якій знаходиться вихід з піраміди. При цьому з кімнати в кімнату він може попадати тільки за допомогою пристроїв, тому що охоронець, що прокинувся, закрив всі двері у кімнатах піраміди.
Написати програму, що одержує на вході опис розташування пристроїв і їхніх характеристик (періоди часу, через які "спрацьовують" ці модулі), а видає значення оптимального часу і послідовність пристроїв, якими треба скористатися, щоб потрапити з кімнати 1 у кімнату N за цей час.
Аннотація
В даній курсовій роботі потрібно виконати два завдання. В моєму випадку, перше завдання полягає у використанні структури даних «Черга» та деяких алгоритмів, пов’язаних з нею
В другому завданні потрібно потрібнозастосовувавти динамічну структуру даних «Граф», а також ряд інших структур, наприклад «Список». Також в даній програмі потрібно розробити і застосувати певні алгоритми для роботи з цими структурами.
Вступ
В процесі розробки програмного забезпечення доволі часто доводить використовувати різні абстрактні структури даних.
В моєму першому завданні потрібно розробити програму, яка б відображала роботу автостоянки. Для створення даної програми мені потрібно використати структуру даних «Черга». Дана структура працює за принципом «Перший зайшов, перший вийшов»(FIFO). Також я повинен розробити ряд алгоритмів, які б виконували функції додавання і вилучення автомобілів з автостоянки. Програма повинна показувати скільки переміщень здійснив автомобіль до моменту відїзду з стоянки.
В другому завданні потрібно створити програму, яка б маючи опис кількості кімнат, спеціальних пристроїв, та місця розташування цих пристроїв, знаходила найкоротший час, необхідний для переміщення з початкової до кінцевої кімнати, а також відображала оптимальний шлях. Дана програма реалізовується за допомогою абстрактної структури даних «Граф», а також кількох базових алгоритмів для роботи з цією структурою.
Завдання 1
Теоретична частина:
Черга – це структура даних, яка містить в собі певну кількість елементів. Принцип за яким працює черга є «Перший прийшов, перший вийшов» (FIFO). Тобто ми можемо додавати елементи даних тільки в кінець черги, а вилучати лишень з початку.
Опис алгоритму:
Для реалізації програми було створено два класи: CCariCParking. Об’єкти першого класу містять інформацію про автомобілі, які прибувають і відбувають з автостоянки. Об’єкти другого класу містять інформацію і методи для керування роботою стоянки.
Клас CCar містить наступні поля:
int m_nNumberOnParking – зберігає номер місця даного автомобіля на стоянці.
intm_nNumberOfArrival – зберігає номер прибуття автомобіля.
intm_nAmountOfMovings – зберігає кількість переміщень, здійснену даним автомобілем.
Методи класу:
voidGetPlace(intnumOfPlace) – отримує і встановлює номер розташування автомобіля на стоянці.
voidMove()– збільшує кількість переміщень автомобіля на 1.
Клас CParkingмістить наступні поля:
int[] m_nListOfCars – зберігає список розташування машин на стоянці
stringm_sListOfCars – зберігає список розташувань в текстовій змінній
int[] m_nWaitingCars– зберігає список машин, що чекають місця на стоянці
string m_sWaitingCars – зберігає список машин,що чекають місця на стоянці, але в текстовій змінній
Queue<CCar> m_cPlace – черга, яка відображає роботу стоянки
Queue<CCar> m_cWaiting – черга, яка відображає машини, що чекають місця на стоянці.
int m_nNumberOfFreePlaces – зберігає кількість вільних місць на стоянці
int m_nNextPlaceToPark – зберігає номер наступного вільного місця
intm_nNextPlaceToWait – зберігає номер наступного місця в черзі автомобілів, що чекають місця на стоянці.
Методи класу:
void AddCar(CCar newCar) – метод добавляє автомобіль у наступне вільне місце на стоянці. У випадку, якщо вільних місць немає, то добавляє автомобіль в чергу автомобілів, що чекають місця.
CCar TakeCar(int numOfArrival) – вилучає з черги автомобіль, що прибув на стоянку numOfArrival-м по порядку.
string ReturnListOfCars() – метод повертає текстову змінну зі списком розміщення автомобілів на стоянці.
Діаграма класів і зв’язків між їх членами і методами
/
Специфікація програми:
Для додавання автомобіля на стоянку, натискаємо кнопку «Прибуття». У відповідних полях відображається як розміщені автомобілі на автостоянці. Якщо кількість автомобілів перевищує 10, то наступні відображатимуться в черзі, що чекає місця на стоянці.
Для вилучення певного автомобіля, потібрно ввести його номер прибуття у відповідне поле вводу, і натиснути кнопку «Поїхати». Програма виведе нам кількість переміщення, що була здійснена автомобілем від моменту прибуття, а в відповідних полях буде показано, як змінилося розміщення автомобілів на стоянці, і в черзі очікування.
Результати виконання програми:
Прибуття одного автомобіля
/
Прибуття ще пятьох
/
Від’їзд автомобіля, що приїхав на стоянку четвертим
/
Прибуття ще дев’ятьох автомобілів
/
Відїзд тринадцятого автомобіля
/
Відїзд третього автомобіля
/
Відїзд першого автомобіля
/
Вілїзд п’ятнадцятого автомобіля
/
Стоянка після відїзду п’ятнадцятого автомобіля
/
Теоретична частина:
Граф ненаправлений – це сукупність вершин і ребер, зв’язаних між собою, в якому напрям руху від одної до іншої вершини по ребрі, може здійснюватися в обидві сторони.
Кожній вершині графу(що асоціюється з кімнатою піраміди) присвоюється своє унікальне числове значення, яке відповідає часу, необхідному для переміщення до даної вершини з початкової.
Кожному ребру (що асоціюється з пристроєм для переміщення між кімнатами) присвоюється вага (час необхідний для перезарядки пристрою). Ребра зв’язують між собою певні вершини графу.
Алгоритм Дейкстри (Dijkstra’salgorithm) - алгоритм на графах, винайдений нідерландським вченим Е. Дейкстри в 1959 році. Знаходить найкоротший шлях від одної вершини графа до всіх інших. Алгоритм працює тільки для графів без дуг від’ємної довжини. Алгоритм широко застосовується в програмуванні і технологіях.
Неформальне пояснення
Кожній вершин V поставимо мітку - мінімальну відстань від цієї вершини до a. Алгоритм працює покроково - на кожному кроці він «відвідує» алгоритму намагатимемося зменшити цю відстань. Робота алгоритму завершується, коли всі вершини відвідані.
Ініціалізація. Мітка самої вершини a покладається рівною 0, мітки інших вершин - нескінченності. Це відображає те, що відстані від a до інших вершин поки невідомі. Усі вершини графа позначаються як не відвідані.
Крок алгоритму. Якщо всі вершини відвідані, алгоритм завершується. В іншому випадку, з ще не відвіданих вершин вибирається вершина u, що має мінімальну позначку. Ми розглядаємо всілякі маршрути, в яких u є передостаннім пунктом. Вершини, в які ведуть ребра з u, назвемо сусідами цієї вершини. Для кожного сусіда вершини u, крім позначених відвідані, розглянемо нову довжину шляху, що дорівнює сумі значень поточної мітки u і довжини ребра, що з’єднує u з цим сусідом. Якщо отримане значення довжини менше значення мітки сусіда, замінимо значення мітки отриманим значенням довжини. Розглянувши всіх сусідів, відмітимо вершину u з графа і повторимо крок алгоритму.
Опис алгоритму:
Для реалізації програми були створені так класи:
CRoom
CDevice
CPyramid
Обєкти класу CRoom відповідають за кімнати, які є в піраміді Хеопса.
Обєкти класу CDeviceпредставляють пристрої, для переміщення між кімнатами.
Клас CPyramidсимволізує піраміду Хеопса, де відбуваються всі переміщення.
Члени класу CRoom:
int m_nNumberOfRoom – зберігає порядковий номер кімнати
int m_nTimeToGetFromBegin – зберігає час, необхідний щоб добратися до даної кімнати з початкової. При створенні обєкту класу CRoom за замовчуванням встановлюється в 9999, але потім змінюється на правильне значення
bool m_bIsChecked – зберігає стан кімнати (чи кімната вже пройдена)
CRoom m_RPrevious – зберігає вказівник на кімнату, що є попередньою, під час оптимального проходження.
Методів клас не має
Члени класу CDevice:
CRoom m_nFirsModuleRoom – зберігає вказівник на кімнату, в якій знаходиться перший модуль пристрою
CRoom m_nSecondModuleRoom – зберігає вказівник на кімнату, в якій знаходиться другий модуль пристрою
int m_nBatteryTime – зберігає час, скільки ще потрібно до повного заряду пристрою
int m_nTimeToRestart – зберігає час, який потрібно даному пристрою для повної зарядки
Методів клас не має
Члени класу CPyramid:
CRoom[] m_RRooms– масив зберігає всі кімнати, що наявні в піраміді
CDevice[] m_DDevices – масив зберігає всі пристрої що є в піраміді і «звязують» кімнати
int m_nShortestWay – зберігає найкоротший час, необхідний для того, щоб добратися до заданої кімнати від початкової
string m_sShotestPath – зберігає перелік кімнат в які потрібно переміщатися за допомогою пристроїв, для найшвидшого добирання
int m_nTimeOfRunning – зберігає час, який вже пройшов від початку руху по піраміді(початково встановлюється в 0)
CRoom m_RCurrentRoom – зберігає вказівник на поточну кімнату(ту в якій ми знаходимося в момент виконання аналізу шляху)
Методи класу CPyramid:
void BeginWork(int numberOfBeginRoom, int numberOfLastroom) – метод отримує вхідні дані(початкову і кінцеву кімнату), а також керує іншими необхідними для виконання програми методами. Бере значення найкоротшого часу і оптимального шляху до кінцевої програми, і ініціалізує ними відповідні змінні необхідного обєкту CRoom.
CDevice[] GetDevices() – метод знаходить і повертає перелік пристроїв, якими можна скористатися для переміщення в поточній кімнаті.
void CheckNeigbours( CDevice[] devices) – метод отримує перелік пристроїв,якими можна скористатися в даній кімнаті. Встановлює для кожної «звязаної» з поточною кімнати, шлях для добирання. Знаходить і встановлює значення поточної кімнати в кімнату, що є найблищою для поточної в даний момент.
Конструктор класу отримує кількість кімнат і пристроїв, параметри пристроїв і ініціалізує цими даними екземпляр класу CPyramid.
Діаграма класів та зв’язків між членами і методами
/
Специфікація програми:
Вхідні дані задаються в такому вигляді:
у відповідне поле вводимо к-ть кімнат в піраміді
у відповідне поле вводимо к-ть пристроїв
у велике поле вводу заносимо параметри пристроїв ( три числа: час перезарядки даного пристрою, номер кімнати, в якій знаходиться перший модуль пристрою, номер кімнати в якій знаходиться другий модуль пристрою. Числа розділяємо пробілами)
у відповідне поле вводимо номер кімнати з якої розпочати шлях
у відповідне поле вводимо номер кімнати до якої шукатиметься оптимальний шлях.
Якщо дані введено натискаємо кнопку «Знайти». Програма виводить найменший час, необхідний для переміщення в задану кімнату, і послідовність кімнат в які потрібно переміщуватися ( виводить таким чином: «номер_кінцевої_кімнати ( … (номер_початкової_кімнати» ).
Результат виконання програми:
/
/
Для більшої зрозумілості прикладів, наводиться граф, з проекцією
даної піраміди
(При таких вхідних даних:
К-ть кімнат – 7
К-ть пристроїв – 10
Параметри пристроїв:
7 0 2
9 0 3
14 0 1
12 1 4
3 4 3
6 3 6
1 2 6
8 4 5
5 3 5
4 6 5)
/
Висновок : виконуючи завдання цієї курсової роботи ми закріпили знання про динамічні структури даних, навчились розробляти алгоритми на їх основі.
Результатом виконання цієї роботи стали дві програми, перша розроблена на основі динамічної структурі даних – черга, друга на основі динамічної структури – граф.
Список використаної літератури :
Седжвік Р. — Фундаментальні алгоритми на C++. Частина 5. Алгоритми на графах. Переклад з англійської Р.Сенджвік.СПб : ВАТ «ДіаСофтЮП», 2002. – 496с.
Електронний ресурс - wikipedia.org
Додатки:
/**************************************************************************************\
FILE........:Form1.cs
AUTHOR......:Dmytro Pryumak
DESCRIPTION.:This module contains all neccessary functions
for controling the program
COPYRIGHT...:Copyright(c) 2011, Pryumak Corp.
HISTORY.....:DATA COMENT
-------------------------------------
01.05.2011 Created - Dmytro
\**************************************************************************************/
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace KursovaRobota
{
public partial class Form1 : Form
{
// Створення об'єктів для роботи з першою програмою
CParking example = new CParking();
int CarPass;
public Form1()
{
InitializeComponent();
}
// Натискання кнопки додає автомобіль на парковку
private void bt_NewCar_Click(object sender, EventArgs e)
{
CarPass++;
CCar newOne = new CCar(CarPass);
example.AddCar(newOne);
rtb_ListOfCars.Clear();
rtb_ListOfCars.Text = example.ReturnListOfCars();
rtb_WaitingCars.Clear();
rtb_WaitingCars.Text = example.m_sWaitingCars;
}
// Натискання кнопки вилучає автомобіль з заданим номером
private void bt_TakeCar_Click(object sender, EventArgs e)
{
CCar tmp = example.TakeCar(Convert.ToInt32(tb_CarToGo.Text));
MessageBox.Show("Машина що приїхала " +
tmp.NumberOfArrival.ToString() +
" здійснила " + tmp.AmountOfMovings.ToString() + " переміщень");
rtb_ListOfCars.Clear();
rtb_ListOfCars.Text = example.ReturnListOfCars();
rtb_WaitingCars.Clear();
rtb_WaitingCars.Text = example.m_sWaitingCars;
}
// Натискання кнопки знаходить оптимальний шлях і найкоротший шлях до заданої кімнати
private void bt_Start_Click(object sender, EventArgs e)
{
CPyramid example = new CPyramid(Convert.ToInt32(tb_NumberOfRooms.Text),
Convert.ToInt32(tb_NumberOfDevices.Text), rtb_ParamsOfDevices.Text);
example.BeginWork(Convert.ToInt32(tb_BeginingRoom.Text), Convert.ToInt32(tb_LastRoom.Text));
tb_ShortestTime.Text = example.ShortestWay.ToString();
tb_ShortestWay.Text = example.ShotestPath;
}
}
}
/*****************************END OF FILE: Form1.cs ***********************************/
/**************************************************************************************\
FILE........:Program1Classes.cs
AUTHOR......:Dmytro Pryumak
DESCRIPTION.:This module contains realisation of classes, which are used
in the first program
COPYRIGHT...:Copyright(c) 2011, Pryumak Corp.
HISTORY.....:DATA COMENT
-------------------------------------
01.05.2011 Created - Dmytro
\**************************************************************************************/
using System.Collections.Generic;
// Клас, що уособлює сутність "Автомобіль"
class CCar
{
// Члени класу
int m_nNumberOnParking;
int m_nNumberOfArrival;
int m_nAmountOfMovings;
// Члени класу інкапсульовані як Властивості об'єкта
public int AmountOfMovings
{
get { return m_nAmountOfMovings; }
}
public int NumberOfArrival
{
get { return m_nNumberOfArrival; }
set { m_nNumberOfArrival = value; }
}
public int NumberOnParking
{
get { return m_nNumberOnParking; }
set { m_nNumberOnParking = value; }
}
// Конструктори класу (за замовчуванням і з параметром
public CCar()
{
m_nAmountOfMovings = 0;
}
public CCar(int numOfArrival)
{
m_nAmountOfMovings = 0;
m_nNumberOfArrival = numOfArrival;
}
// Метод, який отримує для автомобіля місце на парковці
public void GetPlace(int numOfPlace)
{
m_nNumberOnParking = numOfPlace;
}
// Метод, який збільшує к-ть переміщень автомобіля
public void Move()
{
m_nAmountOfMovings++;
}
}
// Клас, що уособлює сутність "Парковка"
class CParking
{
// Члени класу
int[] m_nListOfCars;
string m_sListOfCars;
int[] m_nWaitingCars;
public string m_sWaitingCars;
Queue<CCar> m_cPlace;
Queue<CCar> m_cWaiting;
int m_nNumberOfFreePlaces;
int m_nNextPlaceToPark;
int m_nNextPlaceToWait;
// Конструктор класу
public CParking()
{
m_nListOfCars = new int[11];
m_cPlace = new Queue<CCar>();
m_cWaiting = new Queue<CCar>();
m_nNumberOfFreePlaces = 10;
m_nNextPlaceToPark = 10;
m_nWaitingCars = new int[11];
m_nNextPlaceToWait = 1;
}
// Метод, що добавляє автомобіль на парковку,
// або якщо немає вільного місця - ставить в чергу очікувань
public void AddCar(CCar newCar)
{
if (m_cPlace.Count < 10)
{
m_cPlace.Enqueue(newCar);
newCar.NumberOnParking = m_nNextPlaceToPark;
m_nListOfCars[m_nNextPlaceToPark] = newCar.NumberOfArrival;
m_nNextPlaceToPark--;
m_nNumberOfFreePlaces--;
}
else
{
m_cWaiting.Enqueue(newCar);
m_sWaitingCars += "Машина № " + newCar.NumberOfArrival.ToString() + "\n";
m_nWaitingCars[m_nNextPlaceToWait] = newCar.NumberOfArrival;
m_nNextPlaceToWait++;
}
}
// Метод, який відправляє заданий автомобіль з парковки
public CCar TakeCar(int numOfArrival)
{
int carsToOut =-1;
for (int i = 1; i <= 10; i++)
if (numOfArrival == m_nWaitingCars[i])
carsToOut = i-1;
if (carsToOut >= 0)
{
for (int i = carsToOut; i <= 10; i++)
{
m_nWaitingCars[i - 1] = m_nWaitingCars[i];
}
Queue<CCar> tmp = new Queue<CCar>();
while(m_cWaiting.Peek().NumberOfArrival!=numOfArrival)
tmp.Enqueue(m_cWaiting.Dequeue());
CCar tmpCar = m_cWaiting.Dequeue();
while (m_cWaiting.Count != 0)
tmp.Enqueue(m_cWaiting.Dequeue());
while (tmp.Count != 0)
m_cWaiting.Enqueue(tmp.Dequeue());
m_sWaitingCars = m_sWaitingCars.Remove(m_sWaitingCars.IndexOf(numOfArrival.ToString())-9,12);
return tmpCar;
}
else
{
for (int i = 1; i <= 10; i++)
if (m_nListOfCars[i] == numOfArrival)
carsToOut = 10 - i;
if (carsToOut == 0)
{
CCar tmp = m_cPlace.Dequeue();
tmp.Move();
m_nNumberOfFreePlaces++;
m_nNextPlaceToPark++;
foreach (CCar car in m_cPlace)
car.Move();
for (int i = 10; i >= 1; i--)
m_nListOfCars[i] = m_nListOfCars[i - 1];
if (m_cWaiting.Count != 0)
{
AddCar(m_cWaiting.Dequeue());
m_sWaitingCars = m_sWaitingCars.Remove(0, m_sWaitingCars.IndexOf('\n') + 1);
}
return tmp;
}
else
{
Queue<CCar> tmp = new Queue<CCar>();
for (int i = carsToOut; i != 0; i--)
{
m_cPlace.Peek().Move();
tmp.Enqueue(m_cPlace.Dequeue());
}
CCar tmpCar = m_cPlace.Dequeue();
tmpCar.Move();
while (m_cPlace.Count != 0)
tmp.Enqueue(m_cPlace.Dequeue());
while (tmp.Count != 0)
{
tmp.Peek().Move();
m_cPlace.Enqueue(tmp.Dequeue());
}
m_nNumberOfFreePlaces++;
m_nNextPlaceToPark++;
for (int i = 10 - carsToOut; i >= 1; i--)
m_nListOfCars[i] = m_nListOfCars[i - 1];
if (m_cWaiting.Count != 0)
{
AddCar(m_cWaiting.Dequeue());
m_sWaitingCars = m_sWaitingCars.Remove(0, m_sWaitingCars.IndexOf('\n') + 1);
}
return tmpCar;
}
}
}
// Метод, що повертає текстову змінну, в якій міститься
// перелік автомобілів на парковці
public string ReturnListOfCars()
{
m_sListOfCars = "";
for (int i = 1; i <= 10; i++)
{
m_sListOfCars += "На місці - " + i.ToString() + " машина № " + m_nListOfCars[i].ToString() + "\n";
}
return m_sListOfCars;
}
}
/*****************************END OF FILE: Program1Classes.cs *************************/
/**************************************************************************************\
FILE........:Program2Classes.cs
AUTHOR......:Dmytro Pryumak
DESCRIPTION.:This module contains realisation of classes, which are used
in the second program
COPYRIGHT...:Copyright(c) 2011, Pryumak Corp.
HISTORY.....:DATA COMENT
-------------------------------------
01.05.2011 Created - Dmytro
\**************************************************************************************/
using System.Collections.Generic;
using System.Collections;
// Клас, що реалізує сутність "Кімната"
class CRoom
{
// Члени класу
int m_nNumberOfRoom;
int m_nTimeToGetFromBegin = 9999;
bool m_bIsChecked;
CRoom m_RPrevious;
// Члени класу, інкапсульовані як властивості об'єкта
public int NumberOfRoom
{
get { return m_nNumberOfRoom; }
set { m_nNumberOfRoom = value; }
}
public bool IsChecked
{
get { return m_bIsChecked; }
set { m_bIsChecked = value; }
}
internal CRoom Previous
{
get { return m_RPrevious; }
set { m_RPrevious = value; }
}
public int TimeToGetFromBegin
{
get { return m_nTimeToGetFromBegin; }
set { m_nTimeToGetFromBegin = value; }
}
}
// Клас, що реалізує сутність "Пристрій"
class CDevice
{
// Члени класу
CRoom m_nFirsModuleRoom;
CRoom m_nSecondModuleRoom;
int m_nBatteryTime;
int m_nTimeToRestart;
// Члени класу інкапсульовані як властивості об'єкта
public int TimeToRestart
{
get { return m_nTimeToRestart; }
set { m_nTimeToRestart = value; }
}
public int BatteryTime
{
get { return m_nBatteryTime; }
set { m_nBatteryTime = value; }
}
public CRoom FirsModuleRoom
{
get { return m_nFirsModuleRoom; }
set { m_nFirsModuleRoom = value; }
}
public CRoom SecondModuleRoom
{
get { return m_nSecondModuleRoom; }
set { m_nSecondModuleRoom = value; }
}
}
// Клас, що реалізує сутність "Піраміда Хеопса"
class CPyramid
{
// Члени класу
CRoom[] m_RRooms;
CDevice[] m_DDevices;
int m_nShortestWay;
string m_sShotestPath;
int m_nTimeOfRunning=0;
CRoom m_RCurrentRoom;
// Деякі члени класу, інкапсульовані як властивості об'єкта
public string ShotestPath
{
get { return m_sShotestPath; }
set { m_sShotestPath = value; }
}
public int ShortestWay
{
get { return m_nShortestWay; }
set { m_nShortestWay = value; }
}
// Конструктор класу
public CPyramid(int numberOfRooms, int numberOfDevices, string parametrsOfDevices)
{
m_RRooms = new CRoom[numberOfRooms];
m_DDevices = new CDevice[numberOfDevices];
for (int i = 0; i < numberOfRooms; i++)
{
m_RRooms[i] = new CRoom();
m_RRooms[i].NumberOfRoom = i;
}
for (int i = 0; i < numberOfDevices; i++)
m_DDevices[i] = new CDevice();
string[] devParam = parametrsOfDevices.Split('\n');
string[] devPar;
for (int i = 0; i < devParam.Length; i++)
{
devPar = devParam[i].Split(' ');
m_DDevices[i].TimeToRestart = System.Convert.ToInt32(devPar[0]);
int firstRoom = System.Convert.ToInt32(devPar[1]);
int secondRoom = System.Convert.ToInt32(devPar[2]);
m_DDevices[i].FirsModuleRoom = m_RRooms[firstRoom];
m_DDevices[i].SecondModuleRoom = m_RRooms[secondRoom];
}
}
// Метод, що розпочинає роботу пошуку оптимального шляху
public void BeginWork(int numberOfBeginRoom, int numberOfLastroom)
{
foreach (CRoom room in m_RRooms)
if (room.NumberOfRoom == numberOfBeginRoom)
m_RCurrentRoom = room;
m_RCurrentRoom.TimeToGetFromBegin = 0;
while (m_RCurrentRoom != null)
CheckNeigbours(GetDevices());
m_nShortestWay = m_RRooms[numberOfLastroom].TimeToGetFromBegin;
CRoom tmp = m_RRooms[numberOfLastroom];
m_sShotestPath = numberOfLastroom.ToString();
while (tmp.Previous != null)
{
m_sShotestPath += "<--" + tmp.Previous.NumberOfRoom.ToString();
tmp = tmp.Previous;
}
}
// Метод, що визначає перелік пристроїв, якими можна скористатися
// в поточній кімнаті
CDevice[] GetDevices()
{
List<CDevice> listOfDevices = new List<CDevice>();
foreach (CDevice device in m_DDevices)
if (device.FirsModuleRoom == m_RCurrentRoom ||
device.SecondModuleRoom == m_RCurrentRoom)
listOfDevices.Add(device);
CDevice[] arrayOfDevices = listOfDevices.ToArray();
if (m_nTimeOfRunning != 0)
foreach (CDevice dev in listOfDevices)
dev.BatteryTime = dev.TimeToRestart -m_nTimeOfRunning % dev.TimeToRestart;
else
foreach (CDevice dev in listOfDevices)
dev.BatteryTime = dev.TimeToRestart;
for(int i = 0;i< arrayOfDevices.Length;i++)
for (int j = 1; j < arrayOfDevices.Length; j++)
{
if (arrayOfDevices[j].BatteryTime < arrayOfDevices[j - 1].BatteryTime)
{
CDevice tmp = arrayOfDevices[j];
arrayOfDevices[j] = arrayOfDevices[j - 1];
arrayOfDevices[j - 1] = tmp;
}
}
return arrayOfDevices;
}
// Метод, що обраховує шлях до всіх доступних кімнат
// а також вибирає в яку наступну кімнату переміститися
void CheckNeigbours( CDevice[] devices)
{
CRoom min = null;
for (int i = 0; i < devices.Length; i++)
if (devices[i].FirsModuleRoom == m_RCurrentRoom)
{
if (devices[i].SecondModuleRoom.TimeToGetFromBegin >
m_RCurrentRoom.TimeToGetFromBegin + devices[i].BatteryTime
&& !devices[i].SecondModuleRoom.IsChecked)
{
devices[i].SecondModuleRoom.TimeToGetFromBegin =
m_RCurrentRoom.TimeToGetFromBegin + devices[i].BatteryTime;
devices[i].SecondModuleRoom.Previous = m_RCurrentRoom;
}
}
else
if (devices[i].FirsModuleRoom.TimeToGetFromBegin >
m_RCurrentRoom.TimeToGetFromBegin + devices[i].BatteryTime
&& !devices[i].FirsModuleRoom.IsChecked)
{
devices[i].FirsModuleRoom.TimeToGetFromBegin =
m_RCurrentRoom.TimeToGetFromBegin + devices[i].BatteryTime;
devices[i].FirsModuleRoom.Previous = m_RCurrentRoom;
}
foreach (CDevice device in devices)
if (device.FirsModuleRoom == m_RCurrentRoom
&& !device.SecondModuleRoom.IsChecked)
min = device.SecondModuleRoom
19.11.2013 20:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора