Разработка алгоритма программы в виде блок-схемы

Уфимский государственный авиационный технический университет

Кафедра _________ «Вычислительная техника и зашита информации»_____________

Разработка прикладного алгоритма

Подп. и дата
Подп. и дата
Взаим. инв. №
Инв.№ подл.
Инв.№ дубл.

на языке программирования С++___

___________________________________

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту по ____МП и ПА_____

130.7.074.105.407

(обозначение документа)

Группа ЗИ -239	Фамилия И.О.	Подпись	Дата	Оценка
Студент	Зиннуров Р.Р
Консультант	Селиванова М.В
Принял	Селиванова М.В

Уфа – 2011

Уфимский государственный авиационный технический университет

Кафедра ___ВТиЗИ___________________ факультет ____ИРТ______________________

Задание

на курсовое проектирование по дисциплине ___Методы программирования и прикладные алгоритмы________________________________________________________________________

на тему Разработка прикладного алгоритма и его реализация на языке С++___________

выдано 8 октября 2011г. студенту второго курса____________________________________

________________________________________________________________ЗИ-239 группы

________________________________Зиннурову Рамилю Радисовичу_____________________

__________________________________________________________________________________

(Фамилия И.О)

Срок выполнения ___5 декабря__ 2011г.

Руководитель проекта _к.т.н.,доц. Селиванова М.В.

Технические условия

Использование среды программирования Visual C++ для разработки программ на языке программирования C++___________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

Содержание проекта

Постановка задачи и описание исходных данных;__________________________________

Разработка математического обеспечения и алгоритма программы;__________________

Краткое описание функций среды программирования;_____________________________

Описание работы программы с листингом созданных функций;_____________________

Получение результатов и выводы.________________________________________________

Оформление проекта

Пояснительная записка__________________________________________________________

Разработанная программа_______________________________________________________

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

1. Либерти Д. Освой самостоятельно С++ за 21 день 4-е издание: пер. с англ. – М.: Издательский дом «Вильямс», 2001. – 832 с.: ил. - Парал. тит. англ.

2. Селиванова М.В. Методические указания к курсовой работе по дисциплине «Методы программирования и прикладные алгоритмы»/ Уфимск. гос. авиац. тех. ун-т. Сост. Селиванова М.В. – Уфа, 2008. – 31 с.

3. Кнут Д. Искусство программирования. Т.3 Сортировка и поиск. М.: Вильямс, 2000. – 832 с.

4. Культин Н. «С/С++ в задачах и примерах» - СПб.:БХВ-Петербург, 2002. – 288 с.

5. А. Мешков, Ю. Тихомиров «Visual C++ и MFC» - СПб.:БХВ-Петербург. 2002 – 1017с.

Зав. кафедрой _В.И.Васильев__ Руководитель проекта _М.В. Селиванова

Содержание

1. Постановка задачи и описание исходных данных…………………………5

2. Математическое обеспечение……………………………………………….6

3. Функция изменения времени вычисления от объема исходных данных...6

4. О-сложность алгоритма……………………………………………………...6

5. Разработка алгоритма программы в виде блок-схемы…………………….7

6. Описание функций среды программирования Visual Studio 6……………10

7. Описание работы программы……………………………………………….16

8. Вывод…………………………………………………………………………18

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

10. Приложение А………………………………………………………………21

11. Приложение Б……………………………………………………………….23

12. Приложение В………………………………………………………………25

Постановка задачи и описание исходных данных

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

Математическое обеспечение

Суть метода:

Cоздаётся фиктивная запись в конце файла (A [ N+1]) равная искомому элементу. Последовательно перебираются все элементы массива, если на каком-то шаге цикла обнаруживается, что искомый элемент найден, то происходит выход из цикла, и переход к условию i < N+1. Если условие выполняется, то искомый элемент присутствует в массиве, иначе элемента нет.

Алгоритм Quick Sequential Search реализуется следующим образом:

Q1. [Инициализация] Устанавливаем i ← 1 и K_N+1 ← K.

Q2. [Сравнение] Если K=K_i, то переходим к шагу Q4.

Q3. [Продвижение.] Увеличить i на 1и перейти к шагу Q2.

Q4. [Конец файла?] Если i ≤ N, алгоритм заканчивается успешно; в противном случае алгоритм заканчивается неудачно (i = N+1).

Функция изменения времени вычисления от объема исходных данных

Очевидно, что время выполнения алгоритма Q зависит от двух факторов:

C- количество сравнений ключей;

S=1 при успешном окончании поиска, 0 – при неудачном.

Используя значения C и S, получим, что значение времени работы равно

(4С - 4S + 10)u. Так как при поиске будет всегда успешно найден K=K_i получим С=i, S=1; таким образом, полное время составляет (4i+6)u

О-сложность алгоритма

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

for (int n=0; pInt[n]!= m_search; n++), то О-сложность данного алгоритма линейная О(n)

Разработка алгоритма программы в виде блок-схемы

Рисунок 1 – Блок схема создания массива чисел и запись их в файл

Рисунок 2 – Блок схема считывания из файла данных

Рисунок 3 – Блок схема поиска элемента в массиве

Дата добавления: 2015-10-29