Проектирование таблиц для автоматизации обработки экономических данных (стр. 2 из 3)
Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:
отсутствие потребности в памяти под стек
отсутствие деградации при неудачных наборах данных – qsort легко деградирует до O (n²), что хуже, чем худшее гарантированное время для сортировки Шелла.
Пример
Пусть дан список A = (32,95,16,82,24,66,35,19,75,54,40,43,93,68) и выполняется его сортировка методом Шелла, а в качестве значений d выбраны 5,3,1.
На первом шаге сортируются подсписки A, составленные из всех элементов A, различающихся на 5 позиций, то есть подсписки A5,1 = (32,66,40), A5,2 = (95,35,43), A5,3 = (16,19,93), A5,4 = (82,75,68), A5,5 = (24,54).
В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов.
Процесс завершается обычной сортировкой вставками получившегося списка.
Метод сортировки вставками
Сортировка вставками элементов a1, a2, …, an относится к наиболее очевидным методам. При таком подходе вводится фиктивный элемент a0=-¥, а затем каждый элемент, начиная со второго, сравнивается с элементами уже упорядоченной части последовательности и вставляется в нужное место. При вставке элемент aj временно размещается в переменной w, и просматриваются элементы aj-1, aj-2, …, a1 (уже к этому времени упорядоченные). Они сравниваются с w и сдвигаются, если обнаруживается, что они больше чем w.
Сложность алгоритма определяется числом проверок условия w<a[i] в цикле. В худшем случае потребуется n (n‑1)/2 таких сравнений, то есть сложность сортировки вставками – квадратичная.
Сортировка вставками – простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен, чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:
прост в реализации
эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим
эффективен на наборах данных, которые уже частично отсортированы
это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы)
может сортировать список по мере его получения
не требует временной памяти, даже под стек
На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора.
Псевдокод:
Вход: массив A, состоящий из элементов A[0], A[1],…, A [n‑1]
for i = 1, 2,…, n‑1:
key:= A[i]
j:= i – 1
while j >= 0 and A[j] > key:
A [j + 1]:= A[j]
j:= j – 1
A [j + 1]:= key
2. Общая характеристика задачи
Для решения данной экономической задачи была выбрана среда табличного процессора MS Excel. Microsoft Office Excel является средством для создания электронных таблиц, которые обладают возможностями для проведения простых расчетов, как с использованием арифметических действий, так и с помощью встроенных функций; для построения разных типов диаграмм; для оформления полученных таблиц и т.д. Так же MS Excel программа, не требующая знаний программирования и проста в использовании для поиска результата нашей задачи.
Рассмотрим следующую задачу.
Фирма ООО «Стройдизайн» осуществляет деятельность, связанную с выполнением работ по ремонту помещений. Прайс-лист на выполняемые работы приведен на рис. 1. Данные о заказанных работах указаны на рис. 2.
1. Построить таблицы по приведенным ниже данным.
2. Выполнить расчет стоимости выполняемых работ по полученному заказу, данные расчета занести в таблицу (рис. 2).
3. Организовать межтабличные связи для автоматического формирования счета, выставляемого клиенту для оплаты выполняемых работ.
4. Сформировать и заполнить счет на оплату (рис. 3).
5. Результаты расчета стоимости каждого вида работ по полученному заказу представить в графическом виде.
| Прайс-лист | ||
| Наименование работы | Единица измерения | Цена за ед. изм., руб. |
| Замена батарей | шт. | 250 |
| Замена ванны | шт. | 210 |
| Замена труб | м | 240 |
| Наклейка обоев | кв. м | 50 |
| Настилка паркета | кв. м | 75 |
| Побелка потолка | кв. м | 15 |
Рис. 1. Прайс-лист на выполняемые работы
| Расчет стоимости выполняемых работ | ||||
| Наименование работы | Единица измерения | Объем выполняемых работ | Цена за ед. изм., руб. | Стоимость работ, руб. |
| Замена батарей | шт. | 4 | ||
| Наклейка обоев | кв. м | 20 | ||
| Замена труб | м | 4 | ||
| Настилка паркета | кв. м | 15 | ||
Рис. 2. Данные о поступившем заказе
| ООО «Стройдизайн» | |||||
| СЧЕТ №1 | |||||
| Дата | ___.___.20___ | ||||
| Ф.И.О. клиента | _____________________________________ | ||||
| № п/п | Наименование работы | Единица измерения | Объем выполняемых работ | Цена за ед. изм., руб. | Стоимость работ, руб. |
| 1 | Замена батарей | шт. | |||
| 2 | Наклейка обоев | кв. м | |||
| 3 | Замена труб | м | |||
| 4 | Настилка паркета | кв. м | |||
| ИТОГО: | |||||
| НДС: | |||||
| СУММА С НДС: | |||||
| Гл. бухгалтер | ____________________ | ||||
Рис. 3. Форма счета на оплату выполненных работ
2.1 Описание алгоритма решения задачи
1. Запустить табличный процессор MS Excel.
2. Создать книгу с именем «Стройдизайн».
3. Лист 1 переименовать в лист с названием Работа.
4. На рабочем листе Работа MS Excel создать таблицу прайс-листа на выполняемые работы.
5. Заполнить таблицу прайс-листа исходными данными (рис. 4).
Рис. 4. Расположение таблицы «Прайс-лист» на рабочем листе Работа MS Excel
6. Разработать структуру шаблона таблицы «Расчет стоимости выполняемых работ» (рис. 5).
| Колонка электронной таблицы | Наименование (реквизит) | Тип данных | Формат данных – длина |
| A | Наименование работы | текстовый | 15 |
| B | Единица измерения | текстовый | 15 |
| C | Объем выполняемых работ | числовой | 2 |
| D | Цена за ед. изм., руб. | числовой | 4 |
| E | Стоимость работ, руб. | числовой | 5 |
Рис. 5. Структура шаблона таблицы «Расчет стоимости выполняемых работ»
7. Лист 2 переименовать в лист с названием Данные о заказе.
8. На рабочем листе Данные о заказе MS Excel создать таблицу, в которой будут содержаться данные о поступившем заказе.
9. Заполнить таблицу «Расчет стоимости выполняемых работ» исходными данными (рис. 6).
Рис. 6. Расположение таблицы «Расчет стоимости выполняемых работ» на рабочем листе Данные о заказе MS Excel
10. Заполнить графу Цена за ед. изм., руб. таблицы «Расчет стоимости выполняемых работ», находящейся на листе Данные о заказе следующим образом:
Занести в ячейку D4 формулу:
=Работа! С3
В ячейку D5 занести:
=Работа! С6
Аналогично сделать и в ячейках D6, D7.
11. Заполнить графу Стоимость работ, руб. таблицы «Расчет стоимости выполняемых работ», находящейся на листе Данные о заказе следующим образом:
Занести в ячейку E4 формулу:
=C4*D4
Размножить введенную в ячейку E4 формулу для остальных ячеек данной графы (с E5 по E7) (рис. 7).
| Расчет стоимости выполняемых работ | |||||||||
| Наименование работы | Единица измерения | Объем выполняемых работ | Цена за ед. изм., руб. | Стоимость работ, руб. | |||||
| Замена батарей | шт. | 4 | 250 | 1000 | |||||
| Наклейка обоев | кв. м | 20 | 50 | 1000 | |||||
| Замена труб | м | 4 | 240 | 960 | |||||
| Настилка паркета | кв. м | 15 | 75 | 1125 | |||||
| Рис. 7. Данные о поступившем заказе на 01.02.2008 г. | |||||||||
| Наименование работы | Единица измерения | Объем выполняемых работ | Цена за ед. изм., руб. | Стоимость работ, руб. | |||||
| Замена батарей | шт. | 4 | =Работа! C3 | =C4*D4 | |||||
| Наклейка обоев | кв. м | 20 | =Работа! C6 | =C5*D5 | |||||
| Замена труб | м | 4 | =Работа! C5 | =C6*D6 | |||||
| Настилка паркета | кв. м | 15 | =Работа! C7 | =C7*D7 | |||||
Рис. 7.1. Расположение формул в таблице «Расчет стоимости выполняемых работ»