Роздрукувати сторінку
Главная \ Методичні вказівки \ Методичні вказівки \ 2283 Методичні вказівки до курсової з ОПАМ 2013-2014, Університет КРОК

Методичні вказівки до курсової з ОПАМ 2013-2014, Університет КРОК

« Назад

Методичні вказівки до курсової з ОПАМ 2013-2014 

Мета курсової роботи. Систематизувати знання, отримані при вивчанні дисципліни „Основи програмування та алгоритмічні мови”, розробити алгоритм і скласти програму, використавши технологію структурного програмування у середовищі MicrosoftVisual C++.

1. Теоретичні відомості

1.1. Аналіз задачі

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

Необхідно з’ясувати і описати, які дані є вихідними для задачі, які результати мають бути отримані. Описати константи, змінні, масиви та структури для подання даних. Вказати їх типи і діапазони значень.

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

Результатом стає  Розділ 1. Аналіз предметної галузі та постановка задачі. (Тут і далі див. приклад оформлення роботи у Додатку А).

1.2. Розробка алгоритму

Перед розробкою програми необхідно визначити головні співвідношення між ви­хідними даними та результатами через математичні або логічні вирази, тобто скласти математичну модель. Це робиться на основі результатів аналізу задачі. В основу покладаються результати виконаного у попередньому розділі аналізу задачі, зокрема - основні математичні співвідношення.

Далі розробляється ал­горитм рішення задачі. Необхідно представити собі сценарій роботи програми: що треба вводити в програму, що і як виводи­ти на екран, які перетворення даних здійснюються тощо. Для розробки алгоритму використовувати технологію низхідного проектування: спочатку визначити загальний підхід до вирішення задачі, потім виділити окремі блоки, які виконують закінчений процес обробки даних, далі конкретизувати блоки, які були виділені раніше. Цей процес продовжувати до тих пір, поки не визначаться прості операції.

В результаті складаються одна або декілька прокоментованих записів алгоритму. Вони можуть подаватися у вигляді блок-схем, а для верхніх рівнів абстрагування - у вигляді граф-схем, покрокового запису тощо.

Отримані результати подаються у розділі Розділ 2. Опис алгоритму розв’язання задачі.

1.3. Розробка програми

Розробка програми - багатоступеневий про­цес, що повторюється. Основний цикл цього процесу: намітити загальний проект; знайти стандартні структури даних та функції їх обробки, створити власні структури та функції; скласти проект.

Для проектування та складання програми необхідно виконати наступні дії:

- Розробити структуру записів для введення і виведення даних. Створити вхідні файли та заповнити їх даними для подальшого тестування програми.

- Скласти блок-схему для функції main()та інших складних функцій, що розробляються. Виконати специфікацію функцій.

- Для кожної функції закодувати на мові С++ подання даних: необхідні константи, змінні, масиви,  структури тощо. Виходячи з подання даних закодувати розроблений алгоритми виконання функції. Процес кодування слід виконувати покроково, з проміжним виконанням і налагодженням. Першою кодується функція main()і порожні заглушки для решти функцій. Потім, крок за кроком, заглушки наповнюються командами, що реалізують логіку обробки даних. Для спрощення налагодження програми спочатку кодується введення-виведення даних.

- Виконати тестування програми і оцінити достовірність отриманих результатів. 

Виконана робота описується у розділі Розділ 3. Опис програми.

1.4. Виконання схем алгоритмів та ієрархії класів

Схеми повинні дати наочну уяву послідовності дій, що запрограмовані. Розробляються такі схеми: схема алгоритму, яка відображає процес знаходження рішення задачі, структурна схема програми або схема взаємозв'язку функцій і процедур програми, яка відображає послідовність викликів про­цедур і функцій. Обов'язково додається специфікація функцій і процедур, де наводиться формат оголошення функцій і проце­дур з поясненням змісту параметрів.

 

2. Зміст пояснювальної записки 

Титульний лист

Заповнюється за зразком, приведеним у додатку. Підписується студентом та керівником.

Лист завдання

Видається керівником або заповнюється студентом за зразком, приведеним у додатку.

Календарний план

Друкується на зворотному боці  завдання за зразком, приведеним у додатку. Підписується студентом та керівником.

Зміст

Формується автоматично засобами текстового процесору. Містить заголовки 1-го та другого рівнів, починаючи зі вступу і включно з додатками.

Вступ

Коротко описує мету роботи і її структуру з вказуванням використаних засобів і отриманих результатів по кожному розділу.

Розділ І. Аналіз предметної галузі та постановка задачі

1.1. Опис основних понять і залежностей. 

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

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

У цьому підрозділі слід розмістити такі відомості:

- умова задачі : формулювання задачі, умови, за яких програма припиняє свою роботу

- вхідні дані;

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

1.3.  Аналіз задачі на можливість розв'язання.

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

Розділ ІІ. Опис алгоритму розв’язання задачі

2.1. Математична модель

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

2.2. Ідея та схема алгоритму

В підрозділі описується погляд на алгоритм на верхньому рівні абстрагування. Можлива текстова або графова форма подання алгоритму верхнього рівня абстракції. Описуються загальні дії - введення та виведення даних, основні кроки обчислень. На верхньому рівні дії описуються в термінах предметної галузі, зрозумілих для замовника. Кожна така дія може бути достатньо складною, через те вводяться наступні рівні абстракції. На них поняття конкретизуються через інші терміни, прив’язані до введених означень констант, змінних, масивів та структур. В результаті створюється перелік прокоментованих структурних одиниць - елементарних дій. З них складається схема алгоритму.

Розділ ІІІ. Опис програми

3.1. Опис структури файлів

Приводиться перелік файлів, що містять данні для виконання програми та результати. Для кожного файлу описується його призначення та тип.

Описуються структури записів у кожному файлі.

3.2. Структура програми

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

3.3. Специфікація функцій програми

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

3.4. Оцінка достовірності результатів.

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

Висновки

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

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

Додатки

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

 

(Приклад основної частини роботи)

Зміст

(Сформувати зміст (автоматично!) )

Вступ

(Вставити текст вступу )

РОЗДІЛ  І.
АНАЛІЗ ПРЕДМЕТНОЇ ГАЛУЗІ ТА ПОСТАНОВКА ЗАДАЧІ

1.1. Опис основних понять і залежностей 

Задача продажи билетов решается во всех автоматизированных системах резервирования и реализации билетов. Эта задача характерна не только для поездов, но и для самолетов, автобусов, а также кинотеатров и других объектов. Общим является то, что такой объект содержит некоторое количество мест, каждое из которых может предоставляться клиенту на некоторое время. Факт предоставления места регистрируется системой и подтверждается выданным документом - билетом.

В зависимости от предметной области, каждая система продажи билетов имеет свои особенности. Так, в кинотеатрах количество мест не изменяется и каждое проданное место считается занятым в течение всего сеанса. В автобусе то же самое, но место может заниматься на часть времени – от одной остановки до другой. В самолете накладывается дополнительное ограничение на равномерность распределения веса пассажиров по салону. А для поездов появляется новая возможность добавления или удаления вагонов по мере продажи билетов [[1]].

Первые автоматизированные системы продажи билетов на поезд появились на территории СССР еще в 70-80 гг. прошлого столетия. Тогда их функциональные возможности были весьма ограниченными: система  «Экспресс-1» с 1972 года обслуживала предварительные кассы Киевского вокзала, с 1974 – весь Московский железнодорожный узел. Это поколение исполняло функцию продажи билетов только от Москвы со сроком резервирования от 10 дней до отправления поезда. [[2]] .

Сегодня аналогичные системы работают в on-line режиме, имеют доступ к внутренним и зарубежным маршрутам, обслуживают множество касс, позволяют заказывать и самостоятельно распечатывать билеты прямо дома.

Перечень основных понятий и функций таких систем можно составить на основе анализа следующего прототипа:

Автоматизированная система самообслуживания «е-Квиток» [[3]].

Предназначена для предоставления возможности заказа и оплаты в сети Интернет:

•  бронирования мест (с последующим выкупом проездных документов в билетной кассе),

•  проездных (перевозных) документов (с последующей печатью и получением проездных (перевозных) документов в билетной кассе).

•  электронных проездных (перевозных) документов (с предоставлением посадочных документов)

С помощью АСС «е-Квиток» Вы также можете получить справочную информацию, а именно:

•  Наличие свободных мест и стоимость проезда.

•  Отправление поездов со станции.

•  Схема поезда (типы вагонов в поезде).

•  Маршрут поезда.

•  Календарь курсирования поезда. 

Аналогичные услуги предоставляет сайт TICKETSUA, первая страница которого представлена на рис. 1.1. 

Рис. 1.1. Первая страница сайт TICKETSUA

Сервис дает возможность пассажирам осуществлять интернет-заказ железно­дорож­ных билетов на поезда Украинской Железной Дороги.

В результате успешной оплаты Вы получаете цифровой код. После предъявления кода Вы без очереди и доплаты можете получить билет в любой автоматизированной кассе «Украинской железной дороги». Граничный срок получения билетов – 15 минут до отправления поезда. Исключением являются поезда 165, 166, граничный срок получения билетов на которые - 1,5 часа до отправления поезда.

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

1.2.1. Умова задачі

Програма має обробляти дані про наявність вільних місць в поїзді по всьому маршруту його слідування. Для цього вона користується даними з файлу: зчитує відомості про місто у вагоні, визначає, чи воно вільно на даному перегоні і коригує файл через внесення відміток про продаж місць.  

Програма виконується в діалоговому режимі як консольне застосування. Тобто по запиту оператора вона має виконувати наступні дії:

– виводити на екран і у текстовий файл звіт про вільні і зайняті місця у вказаному вагоні та по всьому поїзду вздовж всього маршруту;

– шукати перше вільне місце у вказаному вагоні на заданій ділянці маршруту;

– відмічати у файлі факт продажу квітка на знайдене вільне місце;

1.2.2. Вхідні дані

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

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

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

- Файл з даними про місця у поїзді. В нього вводяться зміни при продажі квитків.

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

- Повідомлення на консоль оператора у відповідь на його запити та команди.

1.3.  Аналіз задачі на можливість розв'язання

Из анализа прототипов, рассмотренных в п. 1.1. и постановки задачи следует, что в курсовой работе могут быть реализованы такие функций программы:

  • Формирование общего списка мест в поезде с отметкой, на каком участке маршрута следования место занято.

  • Предоставление справки о свободном месте в указанном вагоне на заданном участке маршрута и о свободных местах во всем поезде на пути его следования.

  • Фиксация занятости места при продаже билета на заданный участок маршрута.

Минимальное решение может обслуживать один поезд с несколькими вагонами одного класса, по нескольку места в вагоне. Маршрут состоит из нескольких станций, идентифицируемых номерами - Станция-1,   Станция-2 и т.д. Данные могут храниться на внешнем носителе. Очередной запуск программы должен обеспечивать продолжение работы с сохраненными данными.

Режимы работы:

1) Формирование нового поезда (все места свободны). Оператор вводит количество вагонов в поезде, количество мест в вагоне, количество станций по пути следования. При формировании нового поезда информация о старом поезде стирается.

2) Справка об очередном свободном месте в вагоне N на участке от станции А до станции В. Если номер вагона не указан, то поиск ведется от начала состава.

3) Продажа билета на очередное свободное место на данном участке маршрута.

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

Программа разрабатывается на языке С++ как консольное приложение. 

Рекомендуемое решение. В отличие от минимального решения должно обеспечиваться формирование различных вариантов поездов и различных маршрутов следования.

Поезд может составляться из вагонов 1-го, 2-го и 3-го классов. В зависимости от класса меняется количество мест в вагоне.

Информация о вариантах составов хранится в текстовом файле. Оператору предоставляется перечень возможных составов, например: 1-экспресс, 2-скорый, 3-пассажирский, 4-электричка.

Информация о вариантах маршрутов также хранится в текстовом файле. Оператору предоставляется перечень возможных маршрутов, например: 1-Киев-Харьков, 2-Киев-Одесса, 3-Львов-Харьков. Для каждого маршрута задается последовательность названий станций, через которые следуют поезда по этому маршруту.

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

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

Оператор может, не выходя из программы, просматривать список формируемых поездов и выбирать требуемый для просмотра сведений или продажи билета.

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

Программа разрабатывается на языке С++ как консольное или оконное приложение.

РОЗДІЛ  ІІ.
ОПИС  АЛГОРИТМУ РОЗВ’ЯЗАННЯ ЗАДАЧІ

2.1. Математична модель

Для выбора структур данных и алгоритмов построим математическую модель задачи на основе представления данных о поезде в виде множества мест [[4]].

Представим поезд как множество мест М.  Каждое место характеризуется номером вагона и номером места в вагоне, т.е. М={m n,j }, где  n - номер вагона, а  j - номер места в вагоне. Такое представление поезда показано на рис. 2.1. 

Рис. 2.1. Абстрактное представление поезда

Маршрут представим как множество перегонов между соседними станциями P. Каждый перегон характеризуется номером станции, от которой он начинается, т.е.  P={p k }, где  k - номер станции. Для удобства, все места в поезде пронумеруем подряд. Такое представление поезда с учетом маршрута показано на рис. 2.2.

Обозначим через s i,j i-й перегон, по которому пассажир может проследовать, занимая j-е место. Тогда множество S ={s i,j } всех возможных перегонов, через которые можно проследовать, занимая все возможные места в поезде, можно получить как Декартово произведение этих множеств: = М ´ P (см. рис. 2.2). 

Рис. 2.2. Абстрактное представление поезда на маршруте 

Для решения поставленных задач программа должна выбирать из множества S такое подмножество, которое соответствует одному проданному билету или одному свободному месту на некотором участке пути.  Это можно реализовать с помощью операций над множествами – пересечения, объединения и т.п.

Конкретный билет q на место t  от станции А до станции В характеризуется непрерывной последовательностью перегонов p q,k Î P , таких, что первый перегон начинается от станции отправления (k=A), а последний перегон предшествует станции назначения (k=В-1). Назовем такое подмножество P q,t . P q,t ={s i, t } | A<=i<B.  Так, на рис. 2.2 пунктирной рамкой выделено подмножество P n,t = {s i, 2 } | 1<=i<3, которое соответствует некоторому билету n, проданному на 2-е место от станции 1 до станции 3. 

Поскольку одно и то же место на одном и том же перегоне не может быть занято дважды, P  q1,t Ç P  q2,t = Æ при q1¹q2 .  Отсюда следует простой алгоритм продажи билета, описанный ниже.

2.2. Ідея та схема алгоритму

Множество Z t всех занятых перегонов для места t  вычисляется по формуле 
 Z t = È  P  q1,t по всем проданным билетам qИзначально Z t = Æ.

Тогда для продажи билета q на участок А-В достаточно сформировать  подмножество P q ={p i } | A<=i<B, и для каждого места проверить  пересечение P q Ç Z t = Æ. Если такое место не найдено, то свободных мест нет, а если найдено, то на него можно продавать билет. Тогда факт продажи фиксируется выполнением такой операции:
P q,t P  q ; Z = Z t È  P  q .

Для представления множеств в языке программирования С++ можно использовать различные структуры данных: массивы, списки, файлы. Если остановиться на массивах, то Декартово произведение двух множеств можно задать в виде двумерного массива. Поэтому в данном случае множество S можно представить с помощью массива int Train[MaxPos][MaxStan],  где  MaxStan -  максимальное количество станций в маршруте, а MaxPos=MaxVag*MaxPosVag - максимальное количество мест в поезде (MaxVag- количество вагонов,MaxPosVag- количество мест в вагоне).

 Изначально значения всех элементов равно 0, все места свободны. При продаже билета номер t на место m  выполняется присваивание Train[m][i]=для всех i, таких, что A <= i < В

В случае представления данных в виде рассмотренного выше двумерного массива используем  следующую идею алгоритма. Рассматривается  минимальное решение задачи, показанное в п. 1.3.

Для представления алгоритма воспользуемся формульно-словесным способом. В [ [5], с.21 ] под этим понимается «задание инструкций с использованием математических символов и выражений в сочетании со словесными пояснениями».

1) Формирование нового поезда: обнулить все элементы массива Train.

2) Справка об очередном свободном месте в вагоне N на участке от станции А до станции В:

a) Если N>0, то вычислить номер M1, с которого начинаются места в вагоне  N и номер M2, которым заканчиваются места в вагоне  N. Иначе M1=0; M2=m-1.

b) В цикле для всех M1<=j<= M2 найти такое значение j, для которого все Train[j][i]=0 при A <= i < В.

c) Если j<= M2, то сообщить о том, что место j на участке A-В свободно и может быть продано, иначе задать j=m и сообщить об отсутствии мест в данном вагоне. Сохранить значения j,A для выполнения следующего шага.

3) Продажа билета на очередное свободное место на данном участке маршрута:

a) Если j<m (на предыдущем шаге найдено свободное место), то для всех A <= i < В выполнить Train[j][i]=0.

4) Вывод в текстовый файл общего списка мест в поезде с отметкой, на каком участке маршрута следования место занято.

a) Создать новый текстовый файл с именем «Free.txt». Вывести в него строку «Список свободных мест на <текущая дата и время> ».

b) Для очередной строки массива Train[j][i], 0<=j<m выполнить следующее:

b1) Вывести в файл новую строку «Вагон <j/MaxPosVag +1>, место № <j% MaxPosVag + 1>».

b2) Выполнить поиск очередной подстроки, в которых значения элементов одинаковы.

b3) Если очередная подстрока не найдена, то перейти к п. b), иначе запомнить значение элемента в t1, индекс первого элемента подстроки в n1,  индекс последнего элемента подстроки в  n2.

b4) Если t1=0, то вывести в файл продолжение строки: «на участке < n1+1>-< n2+2> свободно; »  иначе вывести в файл продолжение строки: «на участке < n1+1>-< n2+2> занято, билет № < t1>; » .

b4) Перейти к п. b2).

c) Закрыть текстовый файл.

d) Открыть текстовый файл на чтение, вывести порциями на экран и снова закрыть.

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

РОЗДІЛ ІІІ.
ОПИС ПРОГРАМИ

3.1. Опис структури файлів

Для минимального решения потребуется два файла: двоичный файл с именем «train1.dat» для хранения данных о местах в поезде и текстовый файл с именем «Free.txt» для отчета о занятости мест.

Структура записей файла «train1.dat» проектируется в соответствии с выбранной концепцией представления данных о поезде в виде множества. Для простоты, элементы множества будут кодироваться номером проданного билета.

В начале файла расположим информацию о структуре поезда и маршруте следования (см. табл. 3.1.).

Поскольку файл двоичный, далее в нем можно расположить таблицу, соответствующую множеству S, изображенному на рис. 2.2. Номера билетов располагаются в записях этого файла в соответствии с номером занятого места (от начала вагона) и номером перегона (на котором это место занято) .  Значение 0 проставляется для свободного места.

Для кодирования выберем тип данных unsigned short int, так как он обеспечивает диапазон представления чисел 0 - 65535, что более, чем достаточно для номера билета.

В результате получим следующую структуру файла (табл. 3.1).

Таблица 3.1.

Структура файла  ftrain.

 элемента

Тип данных

Содержание данных

Размер в байтах

0

short

Количество вагонов MaxVag

2

1

short

Количество мест в вагонеMaxPosVag

2

2

short

Количество станций по маршруту следования MaxStan

2

3

short

№ билета, в соответствии с которым занято 1-е место на 1-м перегоне

2

4

short

№ билета, в соответствии с которым занято 1-е место на 2-м перегоне

2

short

2

i+2

short

№ билета, в соответствии с которым занято 1-е место на i-м перегоне

2

short

2

(m-1)* MaxStan + i+2

short

№ билета, в соответствии с которым занято m-е место на i-м перегоне

2

short

2

Структура текстового файла с именем «Free.txt» для вывода отчета о состоянии мест показана в табл. 3.2. Она разработана в соответствии с описанием алгоритма формирования отчета (см выше, п. 2.2).

Таблица 3.2.

Структура файла freport.

№  строки

Содержание данных

0

Список свободных мест на <текушая дата и время>

1

Вагон 1, место № 1 на участке 1-<n1> [свободно|занято, билет № < t1>];  на участке n1+1-<k1> [свободно|занято, билет № < t2>];  …

 

i

Вагон 1, место № <i> на участке 1-<…> [свободно|занято, билет № < …>];  на участке <…>-<…> [свободно|занято, билет № < …>];  …

(j-1)* MaxPosVag +i

Вагон <j>, место № <i> на участке 1-<…> [свободно|занято, билет № < …>];  на участке <…>-<…> [свободно|занято, билет № < …>];  …

Заметим, что в таком текстовом файле длина строки в значительной мере зависит от количества перегонов и продолжительности поездки на один билет. В худшем случае, когда на каждом перегоне место занимает новый пассажир, размер одной строки будет составлять ориентировочно (MaxStan-1)*40 + 20 символов. Так, для количества станций 21 это составит  820 символов, что для современных текстовых редакторов не является существенным (обычное ограничение - 32000 символов в строке).

3.2. Структура програми 

При разработке структуры программы воспользуемся методами, описанными в [[6], п. 6.1]. Организуем ее в виде главного цикла, в котором в диалоге с оператором будет происходить выбор режима работы и выполнения очередной последовательности действий в соответствии с выбранным режимом.

Работой программы будет управлять переменная состояния NS. Ей присваивается номер блока,  которому следует передать управление на текущем витке цикла. Общая схема работы программы показана на рис. 3.1. 

Рис. 3.1. Общая схема работы программы продажи билетов 

Функция Dialog(NS), вводит команды оператора и соответствующие данные с клавиатуры и проверяет их корректность. Другие функции обеспечивают обработку данных и вывод результатов на экран и в файлы. При возникновении какой-либо ситуации, ее код через значение переменной NS возвращается в функцию Dialog, чтобы оператор мог принять решение о дальнейших действиях.

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

Открытие и закрытие файла базы данных train1.dat происходит внутри функций Init, NextFree,  SellFree и Report , а между их вызовами файл закрыт. Такое решение позволит, при необходимости, работать с файлом ftrain одновременно из нескольких приложений. При просмотре сведений о свободных местах это не представит проблемы, если функции NextFree иReport будут открывать этот файл только в режиме чтения.

Функция SellFree должна открывать файл ftrain в монопольном режиме модификации, чтобы исключить одновременную продажу билетов несколькими кассирами.

Заметим, что возможно такое осложнение при продаже билета: Если два кассира с помощью функции NextFreeвыберут одно и то же свободное место, то пока один из них будет в диалоге переходить к режиму продажи, вызов функции SellFreeиз другого приложения может отдать это место другому пассажиру. Поэтому предусмотрим в функции SellFreeповторную проверку, свободно ли данное место на данном участке. Если оно окажется занятым, изменения в файл вносится не будут, функция вернет в переменную NS код возникшей ситуации, и функция Dialog сообщит об этом кассиру.

Текстовая переменная NameTrain с именем этого файла объявлена в функции  main() и передается в другие функции в качестве первого аргумента. Это облегчит в дальнейшем масштабирование программы на одновременную работу с несколькими поездами.

Переменные, характеризующие поезд и маршрут ( MaxVag, MaxPosVag, MaxStan и др.) должны быть доступны во всех функциях. Поэтому они объявлены как глобальные, вне функции main(). В дальнейшем, при масштабировании программы на работу с составами различной структуры, имеет смысл объединить их в одну структуру, и передавать в функции через один аргумент.

Кроме указанных выше, в программе будут использованы и другие функции, как из стандартных библиотек, так и вспомогательные, разработанные для обеспечения доступа к структурам данных. В частности, для работы с файлом ftrain будут запрограммированы функции:

intPosInTrain(n,k) - вычисляет номер места от начала поезда в соответствии с номером вагона n и номером места в вагоне k.

intPosBilet(m,i) - вычисляет позицию элемента в файле ftrain, соответствующую месту m на перегоне i.

intBilet(m,i) - извлекает из открытого файла ftrain номер билета, проданного на место m на перегоне i.

intSeekNextPart(a,b,t) - универсальная функция поиска в открытом файле ftrain.

Предполагается, что аргументы a и bизначально охватывают отрезок файлаftrain, относящийся к одному месту в поезде.

Функция последовательно просматривает элементы от номера a до номера b включительно и передвигает указатели a и b на начало и конец первого из таких участков, в котором:

- при t=0 – все перегоны свободны,

- при t>0 – все перегоны заняты по билету с номером t,

- при t<0 – все перегоны не заняты или заняты по одному билету, все равно с каким номером. Номер билета (при свободном участке - 0) возвращается через аргумент t.

Результатом функции будет 1 при успешном поиске и 0 при неуспешном.

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

- в перебрать все вагоны, начиная с 1.

- для каждого вагона n перебрать все места, начиная с 1.

- для каждого места k в вагоне n с помощью функции m=PosInTrain(n,k) вычислить номер m этого места от начала поезда,

- затем по номеру m с помощью функции a=PosBilet(m,1) определить для этого места позицию в файле  ftrain, которая соответствует первому перегону по пути следования поезда. Соответственно, позиция последнего перегона для этого места b=а+MaxStan-2.

- установить указатель b1 на а-1,

- в циклеустанавливать указателиa1 на b1+1, b1 наb, после чеговызывать функциюSeekNextPart(a1,b1,0),

- при успешном вызове запоминать участок a1-:-b1.

- цикл продолжать, покаa1 не совпадет сb, или функция не вернет значение 0.

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

- когда все места в вагоне просмотрены, перейти к следующему вагону.

- когда все вагоны просмотрены, завершить поиск.

3.3. Специфікація функцій програми

Функция int Dialog(int NS)

В этой функции сосредоточены все действия по вводу выводу данных на консоль оператора. Аргумент NS является параметром, управляющим очередным шагом сеанса диалога. Остальные данные, требуемые для работы, эта функция получает через внешние (глобальные) переменные.

В соответствии со значением NSфункция либо выводит результаты выполнения предыдущей команды оператора, либо запрашивает ввод данных для выполнения следующей команды. Особыми являются значения 0 и -1. При NS=0 выводится сообщение о завершении работы, а при NS=-1 предлагается выбрать один из пунктов меню с последующим вводом требуемых данных.

Результат и побочные эффекты функции зависят от данных, введенных оператором (см. табл. 3.3).

Таблица 3.3.

Зависимость действий и результатов функции Dialog от аргумента NS.

Значение NS

Действие функции

Значение результата

Побочные эффекты

0

Выводится сообщение о завершении сеанса.

0

Отсутствуют

-1

Выбор режима работы.

На консоль выводится пронумерованное меню вида:

2-поиск свободного места

3-продажа билета

4-отчет о заполнении поезда

1-формирование нового состава

0-конец сеанса.

Оператору предлагается ввести номер пункта меню. Далее, в соответствии с выбранным пунктом:

 

 

п.1 - предлагается ввести количество вагонов, мест в вагоне и станций по пути следования.

При вводе значений, выпадающих из допустимого диапазона, выводится предупреждение и ввод игнорируется.  

1 при вводе правильных данных,

-1 при вводе пустой строки или при неправильных данных 

Изменяются внешние переменные MaxVag,MaxPosVag,MaxStan

п.2 - предлагается ввести номера вагона, станции отправления и прибытия;

При вводе значений, выпадающих из допустимого диапазона, выводится предупреждение и ввод игнорируется.  

2 при вводе правильных данных,

-1 при вводе пустой строки или при неправильных данных 

Изменяются внешние переменные N,A,B

п.3 - выводится номер вагона, номер станции отправления и прибытия. Предлагается подтвердить продажу билета нажатием Enter или отказаться нажатием Esc

3 при подтверждении и -1 при отказе

Отсутствуют

п.4

4

Отсутствуют

п.0

0

Отсутствуют

10

Сообщение о неудаче при формировании нового поезда

-1

Отсутствуют

11

Сообщение об успешном формировании нового поезда

-1

Отсутствуют

20

Сообщение об отсутствии свободных мест

-1

Отсутствуют

21

Сообщение о найденном свободном месте

-1

Отсутствуют

30

Сообщение о невозможности продажи билета

-1

Отсутствуют

31

Сообщение о том, что билет продан

-1

Отсутствуют

40

Сообщение о невозможности формирования отчета

-1

Отсутствуют

41

Для каждого свободного места во внешнем массиве report1 выводится  номер места, начала и концы участков маршрута, на которых это место свободно. После вывода описания очередного места вывод прекращается и оператор должен нажать на пробел для продолжения списка или на Esc для прекращения вывода.

-1

Отсутствуют

Функция int Init (NameTrain, MVag, MPV, MS)

(Вставить описание функции аналогично предыдущему)

Функция int NextFree(NameTrain,N,A,B)

(Вставить описание функции аналогично предыдущему)

Функция int SellFree(NameTrain,j,A,B)

(Вставить описание функции аналогично предыдущему)

Функция int Report(NameTrain)

(Вставить описание функции аналогично предыдущему)

3.4. Оцінка достовірності результатів 

(Вставить описание результатов испытания программы на различных тестовых данных. Показать, что все функции выполняются правильно. Особо рассмотреть граничные случаи: все места свободны, все места заняты, имеются и продаются билеты только на один перегон, имеются и продаются билеты на весь путь следования поезда, есть свободные места, но они не могут удовлетворить требуемому маршруту, хотя и находятся внутри него). 

Висновки

(Вставить текст выводов)

Література



[1]. В Украине вводится новая система продажи билетов на поезд [Интернет-ресурс] / К.: РИА Новости.13:02 | 06/ 10/ 2011. - http://rian.com.ua/economy/20111006­/78877608.html

[2]. Юбилей "Экспресса" [Интернет-ресурс] /  http://www.neystadt.org/leonid/express/­express.htm

[3]. е-Квиток. Тестовая версия:  Правила пользования [Интернет-ресурс] /  http://test.e-kvytok.ua/rus/terms/

[4] Бардачов, Ю. М. Дискретна математика [Текст] : підручник / За ред. Ходакова В.Є. - К. : Вища школа, 2002. - 287 с.

[5]. Колдаев В.Д. Основы алгоритмизации и программирования [Текст]  : Учебное пособие / Под ред. проф. Л.Г.Гагариной. - М.: ИД «ФОРУМ»: ИНФРА-М, 2006. -  416 с.

[6]. Ковалюк, Т. В.  Основи програмування [Текст] : підручник / Т.В. Ковалюк. - К. : Видавнича група BHV, 2005. - 384 с.

7. Прата Стивен Язык программирования С++. Лекции и упражнения. Учебник: Пер. с англ./Стивен Прата - СПб.: ООО «ДиаСофтЮП», 2005. - 1104 с.

Додатки

 Додаток А

Текст програми 

(Далі подати текст програми мовою С++ з коментарями. Шрифт Courier New, розмір 10, через 1 інтервал) 

З повагою ІЦ "KURSOVIKS"!