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

Содержание

Введение

1. Описание и анализ поставленной задачи

2. Анализ и выбор структур данных

3. Анализ методов решения задачи

4. Разработка и описание алгоритма решения задачи

5. Реализация и тестирование программного средства

6. Проектирование и описание пользовательского интерфейса

7. Описание результатов

Заключение

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

Приложение А. Код программ



Введение

Под очередью понимается упорядоченный набор элементов, которые могут как удаляться с одного её конца, так и помещаться в другой конец этого набора [1, 169].

Также следует отметить, что очередь можно рассматривать как список, организованный по принципу первый размещён - первый удалён. Для очереди определены три примитивные операции: операция “вставка” - помещает элемент в конец очереди; операция “удаление” - убирает элемент из начала очереди и присваивает начало следующему элементу; третья операция - “проверка на пустоту” -возвращает значение true или false в зависимости от того, является ли данная очередь пустой или нет. Операция “вставка” может быть выполнена практически в любом случае, так как кроме объёма памяти компьютера и условий поставленной задачи на количество элементов, которые может содержать очередь, никаких ограничений не накладывается. Операция “удаление” применима только к непустой очереди. Результатом попытки удалить элемент из пустой очереди является возникновение исключительной ситуации - потеря значимости. Операция “проверка на пустоту” выполнима всегда [1, 170].

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

Для достижения поставленной цели необходимо решить следующие задачи:

1) описать и проанализировать поставленную задачу;

2) произвести анализ и выбор структур данных;

3) проанализировать методы решения задачи;

4) разработать и описать алгоритм решения задачи;

5) реализовать и протестировать программное средство;

..спроектировать и описать пользовательский интерфейс;

6) описать результат.



1. Описание и анализ поставленной задачи

Программа, реализующая очередь типа FIFO, будет представлена нами как система из двух операций: покупки(s) и продажи(r) товара. Для покупки вводятся такие дополнительные параметры, как цена и количество товара в партии. Для продажи - количество проданного товара. При продаже товара идёт наценка в 20% от изначальной стоимости. Если заданного параметра (проданного товара) в таком количестве нет, то на экран выводится количество недостающих товаров. Данные о проданных товарах выводятся на экран. Завершение моделирования работы фирмы производится по желанию пользователя. Программа должна быть написана на языке программирования высокого уровня С++.

2. Анализ и выбор структуры данных

Очередь может быть реализована в программе несколькими способами. В первом случае, очередь задается с помощью обычного массива, в котором будут располагаться элементы очереди. Также нам понадобятся две дополнительные переменные start и ends. start будет указывать на первый элемент очереди, а ends- на последний элемент. Изначально start=1, а ends=0. Очередь считается пустой, если ends < start. Количество элементов в очереди в любоймомент времениравновыражениюstart<=ends+1.Однако, использование массива для представления очереди порождает возможность его переполнения, если очередь содержит больше элементов, чем было зарезервировано в массиве [1,170].

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

Эту проблему можно решить через использование связных списков [3, 240-243]. Применение связных списков позволит нам сократить количество выполняемых операций с очередью. Для этого нам достаточно просто переназначить элемент головы списка на следующий элемент очереди и после этого удалить прошлую “голову”. Единственным ограничением такой реализации очереди будет являться объём доступной памяти компьютера.

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

данных. Поскольку в моделируемой очереди элементы удаляются с одной стороны (начало), то можно использовать односвязный список.

3. Анализ методов решения задачи

Исходя из условий поставленной задачи, нами будет раскрыт метод очереди типа FIFO.

FIFO -- выражение, описывающее принцип технической обработки очереди или обслуживания конфликтных требований путём упорядочения процесса по принципу: «первым пришёл -- первым обслужен» (Рисунок 1) [2,121-122].



Рисунок 1 - FIFO планировщик процессов

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

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

Работу со связными списками можно реализовать рекурсивно и итеративно.

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

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

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

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

4. Разработка и описание алгоритма решения задачи

Рисунок 2 - Блок-схема алгоритма программы

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

Так как мы используем односвязные списки, добавление элемента в конец очереди будет проходить по следующей схеме (Рисунок 3). Вначале создаётся будущий элемент списка. Далее в него поступают такие переменные как количество товара и его цена. После этого идёт настройка связей с очередью: последний элемент очереди начинает ссылаться на новый, уже созданный.

Рисунок 3 - добавление элемента в очередь

Удаление элемента из очереди представлено на Рисунке 4. Сначала происходит разрушение связей: “голова” очереди перестаёт ссылаться на первый элемент, первый элемент перестаёт ссылаться на второй элемент, а “голова”, в свою очередь, начинает ссылаться на второй элемент. После этого отсоединённый первый элемент удаляется из памяти.

Рисунок 4 - удаление элемента из очереди

При построении программы моделирования работы торговой фирмы, нами видится необходимость присутствия в ней рекурсивной функции, которая предполагает последовательное удаление уже пустых партий из очереди [3, 249-250]. Данная модель рекурсивной функции представлена на блок-схеме (Рисунок 5).

Рисунок 5 - Рекурсивный алгоритм удаления элементов из очереди

Для наглядного представления работы рекурсии мы можем обратиться к таблицам 1-2. В первой рассматривается ситуация, в которой количество имеющегося товара может удовлетворить спрос. Во второй таблице симулируется аналогичная ситуация с условием недостатка товара.

Таблица 1 - рекурсивная обработка запроса при условии наличия всего необходимого товара

Уровень рекурсии	Требуется товара	Товара в голове очереди	Уменьшение запроса	Остаток запроса
0	200	30	200-30	170
1	170	25	170-25	145
2	145	100	145-100	45
3	45	45	45-45	0

Таблица 2 - рекурсивная обработка запроса при условии отсутствия необходимого товара

Уровень рекурсии	Требуется товара	Товара в голове очереди	Уменьшение запроса	Остаток запроса
0	210	30	210-30	180
1	180	25	180-25	155
2	155	100	155-100	55
3	55	45	55-45	10
4	10	Очередь закончилась	Очередь закончилась	10

5. Реализация и тестирование программного средства

Рисунок 6 - тест программы №1

Для создания программы моделирования работы торговой фирмы использовалась среда программирования Microsoft Visual Studio. Код программы представлен в приложении A. Тестирование программы было произведено с просмотром 2 случаев. В первом мы используем очередь с одним элементом, при этом задаем разные объемы операций: продажа части партии, продажа целой партии и продажа в условиях дефицита товара в очереди (Рисунок 6).

Во втором случае мы используем очередь, содержащую более одного элемента. В данном тесте мы демонстрируем работу очереди по принципу FIFO (Рисунок 4). При продаже более одной партии работа программы строится по следующему плану.

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

Рисунок 7 - тест программы №2



6. Проектирование и описание пользовательского интерфейса

Пользовательский интерфейс (user interface или сокращенно UI) - это интерфейс, с помощью которого человек может управлять программным обеспечением или аппаратным оснащением.

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

7. Описание результатов

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

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



Заключение

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

Ссылаясь на результаты тестов, можно утверждать, что описанная программа, представленная в приложении А, полностью удовлетворяет условия поставленной задачи.

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

В процессе написания курсовой работы нами была реализована поставленная цель.



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

1. Структуры данных для персональных ЭВМ: Пер. с англ.-М.: Мир, 1989. - 568 с., ил.

2. C/C++. Программирование на языке высокого уровня / Т. А. Павловская.

-- СПб.: Питер, 2003. --461 с: ил.

3. Программирование на языке Паскаль: Пер. с англ. --М.: Мир, --384 с., ил.



Приложение А. Код программы

#include <iostream> #include <conio.h> using namespace std;

struct tovar//структура для партии

{

int prise;//цена за товар

int kolvo;//количество товара в партии

tovar* next;//ссылка на следующий элемент очереди

};

struct head//структура для ссылки на 1 элемент очереди

{

tovar* head;

};

void inithead(head* Node)//обнуление головы

{

Node->head = NULL;

}

void schet(head* Node)//подсчёт товара на складе

{

int tovara = 0;

tovar* shet = new tovar(); shet = Node->head;

while (shet)//пока shet есть идёт подсчёт

{

tovara += shet->kolvo;//прибавка к выводимому числу shet = shet->next;//переход на следующий элемент

}

cout <<"Товара на складе : " <<tovara <<endl;//вывод количества товара на экран

}

void addtovar(int prise, int kolvo, head* Node)//добавление товара в очередь

{

if (Node->head)//проверяем первый ли это элемент

{//если не первый

tovar* tail = new tovar(); tail = Node->head;

while (tail->next)//переходим к последнему элементу очереди

{

tail = tail->next;

}

tovar* newtovar = new tovar();//создаём новый товар и заполняем его newtovar->prise = prise;

newtovar->kolvo = kolvo; newtovar->next = NULL;

tail->next = newtovar;//настраиваем связи

}

else//если он первый

{

tovar* newtovar = new tovar();//создаём новый товар и заполняем его newtovar->prise = prise;

newtovar->kolvo = kolvo; newtovar->next = NULL;

Node->head = newtovar;//присваиваем адрес головы к новому элементу

}

}

void printList(int f, head* Node)//вывод проданного товара

{

tovar* tov = Node->head;

if (f > tov->kolvo)//если количество запрошенного товара превышает количество находящиеся в первом элементе, то тогда выводиться количество товара в первом элементе

cout << "Продано " << tov->kolvo << " штук по цене " << tov->prise * 1.2 << " на сумму " << tov->prise * 1.2 * tov->kolvo << endl;

else

cout << "Продано " << f << " штук по цене " << tov->prise * 1.2 << " на сумму "

<< tov->prise * 1.2 * f << endl;//если количество запрошенного товара не превышает количество 1 элемента тогда подаётся переменная f

}

void DeleteList(int f, head* Node)//удаление элемента из начала очереди

{

tovar* spisok = Node->head;

if (spisok) {//если есть элементы в очереди

if (f >= spisok->kolvo)//проверка является ли запрошенное число больше количества имеющегося в первом элементе

{

printList(f, Node);//вывод проданного товара if (spisok->next)//если элемент в списке не 1

элементе очереди

f = f - spisok->kolvo;//уменьшение требуемого товара на количество в 1

tovar* newHead = spisok->next;//подготовка к смене головы очереди delete spisok;//удаление 1 элемента

Node->head = newHead;//присвоение новой головы

if (f != 0)//проверяем не весь ли требуемый товар продан

DeleteList(f, Node);//если требования не выполнены то функция входит

в рекурсию с изменённой переменной

}

else//если элемент в списке не один

{

if (f != spisok->kolvo)//проверка не равно ли требуемое количество количеству товара в 1 элементы очереди

которой

int x = f - spisok->kolvo;//вычисляем оставшиеся количество товара

inithead(Node);//обнуление головы

delete spisok;//удаление 1 элемента в списке

DeleteList(x, Node);//переход в рекурсию с дальнейшим выводом

недостающих элементов

}

else//если в первом элементе ровно столько же элементов сколько требуется

{

inithead(Node);//обнуляем голову

delete spisok;//удаляем первый элемент очереди

}

}

}

else//если в первом элементе больше товара чем требуется

{

printList(f, Node);//вывод проданного товара tovar* tov = Node->head;

tov->kolvo = tov->kolvo - f;//уменьшение количество доступного товара в 1 элементе очереди

}

}

else//если нет элементов в очереди

cout << f << " единиц товара отсутствует на складе" << endl;

};

void delall(head* Node)//очищение памяти

tovar* head = Node->head;

if (Node->head)//если есть элементы в очереди

{

while (head->next)//пока есть следующий элемент

{

tovar* newHead = head->next;//подготовка к смене головы очереди delete head;//удаление 1 элемента очереди

head = newHead;//присвоение новой головы

}

delete head;//удаляем первый элемент

}

}

int main()

{

setlocale(LC_ALL, "Russian");//подключаем для работы на русском языке head organ;//создаём структуру головы

inithead(&organ);//обнуляем голову

int f, d, g = 1;//создаём элементы для дальнейшей работы char a;//подготовка к основному циклу программы

cout << "Фирма начала работу введите желаемое действие S продажа товара R покупка" << endl;//

while (g != 0)//пока не введётся что-то кроме 's','S' или 'r','R'

{

a = _getch();//поучение сигнала с клавиатуры и присвоение значения переменной switch (tolower(a))//обработка случая с вводом с 'r','s' и другого значения поступающая переменная проходит перевод из заглавных букв в строчные

{

case('r'): {//если введён 'r'

cout << "введите количество купленного товара и цену" << endl; cout << "Количество товара: ";

cin >> f;//ввод количества товара в партии cout << "Цена товара: ";

cin >> d; //ввод цены за единицу товара

addtovar(d, f, &organ);//добавление в конец очереди товара schet(&organ);//вывод количества товара на складе

cout << "Фирма продолжает работу введите желаемое действие S продажа товара R продажа" << endl;

continue;//продолжаем цикл

}

case('s'): {//если введён 's'

cout << "введите количество запрашиваемого товара" << endl; cout << "Товара запрошено: ";

cin >> f;//ввод количество продаваемого товара

DeleteList(f, &organ);//удаление нужного количества товара из очереди schet(&organ);//вывод количества товара на складе

cout << "Фирма продолжает работу введите желаемое действие S продажа товара R продажа" << endl;//

continue;//продолжаем цикл

}

default:g = 0;//изменение переменной и завершение цикла break;

}

}

cout << "Фирма закончила работу"; delall(&organ);//освобождение памяти return 0;

}

Размещено на Allbest.ru

...