ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ "САНКТ-

ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М. А. БОНЧ-БРУЕВИЧА"

Факультет инфокоммуникационных сетей и систем Кафедра программной инженерии и вычислительной техники

ПРАКТИЧЕСКАЯ РАБОТА

по дисциплине «Алгоритмические основы программной инженерии» на тему «Интерполяция данных методом Лагранжа с предварительной их

сортировкой методом Хоара»

Выполнил: студент 1 курса дневного отделения группы ИКПИ-81 Коваленко Л. А.

Санкт-Петербург 2019

СОДЕРЖАНИЕ
ВВЕДЕНИЕ............................................................................................................	3
ОБЩЕЕ ОПИСАНИЕ...........................................................................................	3
РАЗРАБОТКА........................................................................................................	4
АНАЛИЗ ТРЕБОВАНИЙ.................................................................................	4
ПРОЕКТИРОВАНИЕ .......................................................................................	9
UML: USE CASE DIAGRAM.....................................................................	13
UML: SEQUENCE DIAGRAM...................................................................	14
UML: CLASS DIAGRAM ...........................................................................	15
РЕАЛИЗАЦИЯ................................................................................................	16
ИСХОДНЫЕ ФАЙЛЫ MAIN ....................................................................	17
ИСХОДНЫЕ ФАЙЛЫ DPIPE....................................................................	40
СЛОЖНОСТЬ АЛГОРИТМОВ.................................................................	47
ТЕСТИРОВАНИЕ...........................................................................................	50
ЗАКЛЮЧЕНИЕ...................................................................................................	61

2

ВВЕДЕНИЕ Наименование. Программа интерполирования данных методом Лагранжа с

предварительной их сортировкой методом Хоара.

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

ОБЩЕЕ ОПИСАНИЕ

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

•Добавление данных (с консоли или файла).

•Удаление данных.

•Сохранение имеющихся данных в файл.

•Отображение имеющихся данных в консоли.

•Очистка контейнеров.

•Итеративная сортировка контейнеров по X координате методом Хоара.

•Удаление дубликатов по X координате.

•Интерполяция данных контейнера (в файл или консоль) методом Лагранжа.

•Рисование графика интерполяции с использованием именованных каналов для передачи данных между родительским и дочерним процессами.

•Контроль ввода числовых данных пользователем.

•Контроль безошибочного открытия файла.

•Контроль считывания данных из файла.

•Контроль числовых данных на допустимые значения.

Также в отдельных случаях обеспечивается возможность выбора

пользователем механизма ядра — только потока (Thread), мьютекса (Mutex),

семафора (Semaphore), события (Event), ожидающего таймера (Waitable Timer) —

для решения поставленной задачи.

3

РАЗРАБОТКА АНАЛИЗ ТРЕБОВАНИЙ

Функциональные требования. ( , )

• Наличие двух контейнеров, содержащих координаты точек .

•Наличие целочисленной константы MAX_POINTS, описывающей максимально возможное количество точек. Равна 10.000.000.

•Меню пользователя.

	ID	Название пункта	Отображение в	Условие отображения
			программе	пункта
	0	Выход из программы	"0. Safe exit"
	1	Добавить данные из	"1. Add data from file"
		файла		Всегда отображается
	2	Добавить данные с	"2. Add data from
		консоли	console"
	3	Сохранить имеющиеся	"3. Save existing data to
		данные в файл	file"
	4	Показать имеющиеся	"4. Show existing data"
		данные (консоль)		Отображается при
				наличии данных в
	5	Удалить некоторые	"5. Delete some data"
				программе
		данные
	6	Очистить все данные	"6. Clear all data"
	7	Сортировать данные и	"7. Sort data and remove
		удалить дубликаты	duplicates"
	8	Интерполировать	"8. Interpolate by point"	Отображается после
		данные по точке
				сортировки данных (и
				удаления дубликатов
	9	Интерполировать	"9. Interpolate by
				соответственно)
		данные по отрезку	segment"
	10	Статус памяти	"!. Memory Status"	Всегда отображается
		(информация, график)

4

• Функция добавления данных из файла (ID: 1). o Ввод имени файла пользователем.

o Открытие файла в двоичном режиме.

oЕсли файл не удалось открыть, то оповещение пользователя и возврат к меню.

oЕсли открытие файла успешно, то ввод данных из файла:

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

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

Контроль текущего количества точек. (Если текущее количество точек равно максимально допустимому количеству, то функция завершается.)

• Функция добавления данных с консоли (ID: 2). ( , ) o Приглашение пользователя к вводу координат точек .

oКонтроль ввода числовых данных. (Если ввод не является корректным, то возврат к меню, иначе добавление данных в контейнеры и

продолжение ввода.)

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

• Функция сохранения имеющихся данных в файл (ID: 3). o Ввод имени файла пользователем.

o Открытие файла в двоичном режиме.

oЕсли файл не удалось открыть, то оповещение пользователя и возврат к меню.

o Если открытие файла успешно, то запись данных контейнеров в файл.

5

• Функцияотображенияданныхконтейнеровввидетекстовойтаблицы(ID: 4).

Пример.

X	Y
1.000000e+000	1.000000e+000
2.000000e+000	2.000000e+000
3.000000e+000	3.000000e+000

• Функция удаления некоторых записей контейнеров (ID: 5).

o Отображение данных в виде текстовой таблицы с нумерацией строк.

N	X	Y
1	1.000000e+000	1.000000e+000
2	2.000000e+000	2.000000e+000
3	3.000000e+000	3.000000e+000

oПриглашение пользователя к вводу номера строки для удаления.

oЕсли пользователь вводит 0, то возврат к меню.

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

•Функция очистки всех данных контейнеров (ID: 6).

•Функция сортировки и функция удаления дубликатов (ID: 7).

oИтеративная функция сортировки Хоара. Выбор пользователя: в

основном или во вторичном потоке.

o Функция удаления дубликатов X координат (с удалением соответствующих Y координат). Выбор пользователя: в основном или во вторичном потоке. Если встречены две одинаковые X координаты с разными Y координатами, то обе записи (точки) удаляются, если же с одинаковыми Y координатами, то только одна из записей остается.

• Функция интерполяции по точке (ID: 8).

o Ввод степени полинома интерполяции.

6

oПоследовательный ввод координаты X точки пользователем и вывод результата интерполяции Y. (Если ввод неверный, то возврат к меню).

•Функция интерполяции по отрезку (ID: 9).

oВыбор пользователя: вывод результатов в консоль или файл.

oВыбор пользователя: объект ядра (только вторичный поток, мьютекс, семафор, событие, ожидающий таймер с пользовательским значением задержки).

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

			x
	Начальная	Число точек	Конечная
	координата		координата
		разбиения

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

•Функция отображения информации о статусе памяти в виде текста и графика

(ID: 10).

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

7

Требования к надежности.

• Защита от неисправимых программой ошибок. Сообщения для пользователя.

ID	Ошибка				Описание
	[#N# pair] -> #C#		Double:			±3.3621 10 .
1	coordinate is too small	#C# координата слишком мала по экспоненте.2
			Float:	±2.22507 10					.
		Long double:						−4932.
				±1.17549 10				−308
	(exponent). Not recorded.	#N# —					−38
			порядковый номер пары элементов в
						файле.
		#C# — название координаты (X или Y).
	[#N# pair] -> #C#		Double:			±1.18973 10 .
2	coordinate is too big	#C# координата слишком велика по экспоненте.3
			Float:		±1.79769 10 .
		Long double:						4932.
					±3.40282 10			308
	(exponent). Not recorded.	#N# —						38
			порядковый номер пары элементов в
						файле.
		#C# — название координаты (X или Y).

•Гарантия сохранности данных при сбоях в работе программы.

•Защита от некорректных действий пользователя, включая неверный ввод числовых данных с клавиатуры.

2Некорректный ввод игнорируется. Операция считывания продолжается.

3Некорректный ввод игнорируется. Операция считывания продолжается.

8