Методичні вказівки до курсової з ОПАМ 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. Оцінка достовірності результатів. У цьому підрозділі розробник подає приклад виконання програми на тестових даних і виконує аналіз достовірності отриманих результатів. Якщо результат можна перевірити аналітично, то подають аналітичні розрахунки, які мають співпадати з отриманими в результаті роботи програми. Якщо задача обробляє інформаційні потоки даних і не здійснює розрахунків, то достовірність перевіряють, аналізуючи характер перетворення вхідних даних у вихідні результати. Висновки У цьому підрозділі слід визначити, чи задача була розв'язану чи отримані результаті достовірні, що розробник не зміг зробити, як можна використовувати розроблену програму, чи слід продовжувати роботу над задачею з метою отримання нових результатів, чи заслуговує програма на впровадження в навчальний процес, чи є вона реальною тощо. Список використаної літератури Додатки В додатках наводиться друкований текст програми з відповідними коментарями. Обов'язково слід коментувати усі ідентифікатори (назви процедур і функцій, ідентифікатори змінних, констант, параметрів), що зустрічаються в програмі.
(Приклад основної частини роботи) Зміст(Сформувати зміст (автоматично!) ) Вступ(Вставити текст вступу ) РОЗДІЛ І.
|
№ элемента |
Тип данных |
Содержание данных |
Размер в байтах |
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"!