Алгоритмы и структуры данных

МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ

В качестве контрольной работы студентам предлагается решить задачи по дисциплине «Алгоритмы и структуры данных».

Задачи должны быть решены на одном из языков программирования: C#, Java (Kotlin) или C++.

Перед выполнением задания студент должен изучить материалы по темам «Введение в алгоритмы и структуры данных. Рекурсия», «Алгоритмы сортировки», «Элементарные структуры данных».

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

Постановка задачи копируется из условий. Ход решения является описательным пунктом – здесь описывается логика решения задачи на естественном языке.Код программы обязательно должен содержать комментарии. Пример работы программы должен содержать скриншоты программы при выполнении.

В пункте «Тестирование» должны быть представлены наборы тестовых данных (не менее 10-ти наборов, соответствующие условиям задачи). Хотя бы один из тестовых наборов должен отражать крайние значения (например, если максимально введенное число 1000000). Также, по каждому тестовому набору должны быть представлены время выполнения программы и затраченная память. Рекомендуется, оформить данный пункт в виде таблицы, содержащий следующие поля: номер, входные данные, выходные данные (полученные программой), корректность (да/нет), время выполнения (в миллисекундах), память (в Мб). Для измерения времени и памяти необходимо использовать возможности выбранного языка (например, в C# для измерения времени используется StopWatch).

Для измерения времени выполнения метода на языке C# следует использовать следующую конструкцию:

Stopwatch stopWatch = new Stopwatch();

stopWatch.Start();

// здесь пишется тестируемый метод

stopWatch.Stop();

Console.WriteLine("RunTime: " + stopWatch.Elapsed);

Для измерения объема затраченной дополнительной памяти в методе на языке C# можно использовать следующую конструкцию:

long before = GC.GetTotalMemory(false);     

// здесь пишется тестируемый метод

long after = GC.GetTotalMemory(false);

long consumedInMegabytes = (after - before) / (1024 * 1024);

Console.WriteLine(“Memory is {0} Mb.”, consumedInMegabytes);

При выполнении заданий необходимо обязательно делать такие измерения.

Подготовленный отчет оформляется по требованиям УрГЭУ к оформлению и сдается преподавателю.

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