Оглавление

Введение

1. Понятие алгоритма

1.1 Алгоритмы сортировки

1.1.1 Быстрая сортировка (Метод Хоара)

1.1.2 Метод Шелла

1.1.3 Метод сортировки вставками

2. Общая характеристика задачи

2.1 Описание алгоритма решения задачи

Заключение

Список используемой литературы

Введение

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

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

Сам термин «информатика» (informatique) возник в 60-х годах во Франции для определения области исследований, связанных с автоматизацией обработки информации с помощью электронных вычислительных машин (ЭВМ). Этот термин был образован слиянием слов information (информация) и automatique (автоматика) для обозначения информационной автоматики или автоматизированной переработки информации.

Данная курсовая работа состоит из двух частей: теоретической и практической.

В теоретической части рассматривается тема «Алгоритмы сортировки».

В практической части курсовой работы с помощью пакетов прикладных программ (ППП) будут решены и описаны следующие задачи:

1. создание таблиц и заполнение таблиц данными;

2. применение математических формул для выполнения запросов в ППП;

1. Понятие алгоритма

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

Слово «алгоритм» происходит от имени узбекского математика девятого века Аль-Харезми, который сформулировал правило четырёх арифметических действий над многозначными числами. В дальнейшем это слово стало использоваться не только в математике, а фактически любую последовательность действий, приводящих к конечному результату, стали называть алгоритмом, а каждое действие шагом алгоритма. Алгоритм обладает рядом свойств, связанных с необходимостью выполнения определенных требований к процессу вычисления. Это следующие свойства: 1) определённость; 2) массовость; 3) результативность; 4) дискретность. Определённость алгоритма означает, что каждый шаг алгоритма должен быть точен, общепонятен, и исключать возможность различного толкования, другими словами алгоритм должен быть таким, чтобы его мог повторить любой пользователь. Массовость заключается в том, что алгоритм предназначен для решения целого класса задач, которые отличаются только своими входными условиями. Результативность означает, что пошаговый процесс решения задачи в соответствии с алгоритмом должен заканчиваться через определенное конечное число шагов.

Формы представления алгоритма:

1. словесная форма

2. формульно-словесная

3. в виде блок-схемы (графическое изображение алгоритма)

4. в виде программы на алгоритмическом языке программирования.

Виды алгоритмических структур:

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

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

3. Циклический, в которой многократно повторяется некоторый участок алгоритма.

1 поколение алгоритмических языков – конец 1950-х начало 1960-х. Совершенствовались ассемблерные языки. В настоящее время они применяются для создания драйверов оборудования ПК.

2 поколение – 60-е годы. В это время появляются универсальные языки высшего уровня: ФОРТРАН, АЛГОЛ, КОБОЛ, обеспечивающие создание программ для решения задач различного класса.

3 поколение. С начала 1970-х годов начался переход на создание больших программных комплексов. Они в основном применяются для проектирования приложений баз данных и средств визуального программирования.

В середине 1990-х – 4 поколение языков программирования, назначение которых для образования инструкции текст программ на универсальном языке программирования. Система 4 поколения имеет открытую архитектуру и поддерживает значительное число программных продуктов.

Языки программирования:

1. Бейсик отличается встроенными математическими функциями и простыми языковыми конструкциями.

2. Паскаль предназначен для решения вычислительных и информационно-логических задач.

3. Си + + был разработан для облегчения процесса переноса программного обеспечения с одной ЭВМ на другую.

4. Ада ориентирован для применения в системах реального времени и предназначен для разработки программного обеспечения встроенных вычислительных систем.

5. Java (джава) предназначен для создания надёжных, переносимых, распределённых сетевых программных приложений, работающих в архитектуре клиент–сервер, а также удобен для администраторов сети.

6. другим объектно-ориентировочным языком является язык Delphi (дельпхи). Обеспечивает взаимодействие с базами данных, создание различных видов баз, а также работу экономических программ и сети интернет.

1.1 Алгоритмы сортировки

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

Практически каждый алгоритм сортировки можно разбить на три части:

1. сравнение, определяющее упорядоченность пары элементов;

2. перестановку, меняющую местами пару элементов;

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

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

1.1.1 Быстрая сортировка (метод хоара)

Этот метод, называемый также быстрой сортировкой(QuickSort), был Разработан в 1962 г. (его разработал Charles Antony Richard Hoare).

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

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

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

Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного – справа от него. Обычный алгоритм операции:

два индекса – l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно;

вычисляется опорный элемент m;

индекс l последовательно увеличивается до m или до тех пор, пока l й элемент не превысит опорный;

индекс r последовательно уменьшается до m или до тех пор, пока r й элемент не окажется меньше опорного;

если r = l – найдена середина массива – операция разделения закончена, оба индекса указывают на опорный элемент;

если l < r – найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r или l соответственно.

Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.

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

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

1.1.2 Метод Шелла

Этот метод был предложен автором Donald Lewis Shеll в 1959 г. Основная идея этого алгоритма заключается в устранении массового беспорядка в массиве, сравнивая далеко стоящие друг от друга элементы. Интервал между сравниваемыми элементами постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми).

Сортировка Шелла (англ. Shell sort) – алгоритм сортировки, идея которого состоит в сравнении элементов, стоящих не только рядом, но и на расстоянии друг от друга. Иными словами – сортировка вставками с предварительными «грубыми» проходами.

При сортировке Шелла сначала сравниваются и сортируются между собой ключи, отстоящие один от другого на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d = 1 (то есть, обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки вставками или пузырьком (но она не предпочтительна, так как все равно остается медленной) каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, при сортировке Шелла же это число может быть больше).

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:

отсутствие потребности в памяти под стек

отсутствие деградации при неудачных наборах данных – 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 позиций, то есть подсписки A_5,1 = (32,66,40), A_5,2 = (95,35,43), A_5,3 = (16,19,93), A_5,4 = (82,75,68), A_5,5 = (24,54).

В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов.

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

Метод сортировки вставками

Сортировка вставками элементов a₁, a₂, …, a_n относится к наиболее очевидным методам. При таком подходе вводится фиктивный элемент a₀=-¥, а затем каждый элемент, начиная со второго, сравнивается с элементами уже упорядоченной части последовательности и вставляется в нужное место. При вставке элемент a_j временно размещается в переменной w, и просматриваются элементы a_j-1, a_j-2, …, a₁ (уже к этому времени упорядоченные). Они сравниваются с 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. Расположение формул в таблице «Расчет стоимости выполняемых работ»

12. Лист 3 переименовать в лист с названием Форма счета.

13. На рабочем листе Форма счета MS Excel создать форму счета на оплату выполненных работ.

14. Путем создания межтабличных связей заполнить созданную форму полученными данными из таблицы «Расчет стоимости выполняемых работ» (рис. 8).

	ООО «Стройдизайн»
	СЧЕТ №1
	Дата		01.02.2008
	Ф.И.О. клиента		Иванов Сергей Петрович
	№ п/п	Наименование работы	Единица измерения	Объем выполняемых работ	Цена за ед. изм., руб.	Стоимость работ, руб.
	1	Замена батарей	шт.	4	250	1000
	2	Наклейка обоев	кв. м	20	50	1000
	3	Замена труб	м	4	240	960
	4	Настилка паркета	кв. м	15	75	1125
					ИТОГО:	4085
					НДС:	531,05
				СУММА С НДС:		4616,05
	Гл. бухгалтер		Согоян С.В.

Рис. 8. Форма счета на оплату выполненных работ

15. Лист 4 переименовать в лист с названием График.

16. На рабочем листе График MS Excel создать сводную таблицу. Путем создания межтабличных связей автоматически заполнить графы Наименование работы и Стоимость работ, руб. полученными данными из таблицы «Расчет стоимости выполняемых работ» (рис. 9).

17. Результаты вычислений представить графически (рис. 9).

ООО «Стройдизайн» Итоговая стоимость каждого вида работ по полученному заказу на 01. 02. 2008 г. Наименование работы Стоимость работ, руб. Замена батарей 1000 Наклейка обоев 1000 Замена труб 960 Настилка паркета 1125 Итого 4085
	03. 02. 2008 г. Бухгалтер Согоян С.В.

Рис. 9. Сводная таблица и графическое представление результатов вычислений

ООО «Стройдизайн» Итоговая стоимость каждого вида работ по полученному заказу на 01. 02. 2008 г. ='Форма счета'! C9 ='Форма счета'! G9 ='Форма счета'! C10 ='Форма счета'! G10 ='Форма счета'! C11 ='Форма счета'! G11 ='Форма счета'! C12 ='Форма счета'! G12 ='Форма счета'! C13 ='Форма счета'! G13 Итого =СУММ (C7:C10)
			03. 02. 2008 г. Бухгалтер Согоян С.В. Рис. 9.1. Расположение формул в сводной таблице результатов вычислений Заключение Современную жизнь представить без современной техники просто невозможно. Ни одна фирма не обходится без помощи компьютеров. Хранение данных, написание документов, составление графиков, таблиц, расписаний, создание презентаций – во всем в этом нам помогает компьютер, и помогает успешно. В результате выполнения курсовой работы мы на практике познакомились с проектированием таблиц для решений экономических задач. В теоретической части мы изучили алгоритмы сортировки, их виды, предназначение и характеристики. Для молодого специалиста, выпускника института, это весьма важная работа. В работе подробно описывается проектирование таблиц для автоматизации обработки экономических данных. Полученные знания будут способствовать наиболее эффективной работе пользователя с ПК. Список используемой литературы Информатика: Учебник / Под ред. Н.В. Макаровой. – М.: Финансы и статистика, 2005. – 436 с.: ил. Леонтьев В.П. Новейшая энциклопедия персонального компьютера 2005. – М.: ОЛМА-ПРЕСС Образование, 2005. – 800 с.: ил. Информатика. Методические указания по выполнению курсовой работы. – М.: ВЗФЭИ, 2006. – 60 с. Информатика. Лабораторный практикум для студентов 2 курса всех специальностей. – М.: ВЗФЕИ, 2006. – 93 с. Экономическая информатика: Учебное пособие / Под ред. В.В. Евсюкова. – Тула: «Гриф и К», 2003. – 371 с.: ил. http://ru.wikipedia.org 1. Реферат Характеристика молодежного сленга 2. Статья на тему Тайная Вечеря и Трапеза Господня 3. Реферат на тему Рациональное использование воздуха 4. Реферат на тему Реформы ПА Столыпина 5. Реферат на тему King Lear Essay Research Paper The practice 6. Курсовая на тему Подведомственность гражданских дел 7. Реферат Шпора Гистология ЯГМА 8. Реферат Роль минеральных ресурсов в мировой экономики 9. Реферат Фэнтези и субкультура толкинизма 10. Реферат на тему Анализ экономических показателей Японии 1960-1992 гг Компьютерная подготовка в ГУУ 2 курс Bukvasha Правила Контакты