Реализация и тестирование алгоритма бинарного поиска
В данной лабораторной работе нужно реализовать алгоритм бинарного поиска (поиска делением пополам).
Алгоритм в качестве входных данных получает массив отсортированных по возрастанию целых чисел int[] и число, которое необходимо найти. В ответ возвращает индекс наденного элемента массива, либо -1, если число отсутствует в массиве.
Стартовый шаблон программы:
using System;
namespace ConsoleApplication
{
class Program
{
public static int BinarySearch(int[] array, int value)
{
//код поиска значения value в массиве array
}
static void Main(string[] args)
{
TestNegativeNumbers();
TestNonExistentElement();
Console.ReadKey();
}
private static void TestNegativeNumbers()
{
//Тестирование поиска в отрицательных числах
int[] negativeNumbers = new[] {-5, -4, -3, -2};
if (BinarySearch(negativeNumbers, -3)!= 2)
Console.WriteLine("! Поиск не нашёл число -3 среди чисел {-5, -4, -3, -2}");
else
Console.WriteLine("Поиск среди отрицательных чисел работает корректно");
}
private static void TestNonExistentElement()
{
//Тестирование поиска отсутствующего элемента
int[] negativeNumbers = new[] {-5, -4, -3, -2};
if (BinarySearch(negativeNumbers, -1) >= 0)
Console.WriteLine("! Поиск нашёл число -1 среди чисел {-5, -4, -3, -2}");
else
Console.WriteLine("Поиск отсутствующего элемента вернул корректный результат работает корректно");
}
}
}
В программе нужно реализовать проверки:
1. Поиск одного элемента в массиве из 5 элементов
2. Поиск среди отрицательных чисел (реализован в шаблоне)
3. Поиск отсутствующего в массиве элемента (реализован в шаблоне)
4. Поиск элемента, повторяющегося несколько раз
5. Поиск в пустом массиве (содержащем 0 элементов)
6. Поиск в массиве из 100001 элементов
При разработке тестирующий функций помните, что исходный массив, передаваемый функции должен быть отсортирован.
Реализация и тестирование алгоритма быстрой сортировки
В данной лабораторной работе нужно разработать алгоритм быстрой сортировки https://ru.wikipedia.org/wiki/Быстрая_сортировка
Прототип функции:
public static void QuickSort(int[] array)
Размер массива можно получить, обратившись к array.Length.
Для генерации случайных чисел воспользуйтесь классом Random
var rnd = new Random();
rnd.Next(); // возвращает случайное число от 0 до int.MaxValue
rnd.Next(0, 5); // возвращает случайное число от 0 до 4 включительно
Нужно реализовать следующие проверки:
1. Сортировка массива из трёх элементов. После сортировки второй элемент больше первого, третий больше второго
2. Сортировка массива из 100 одинаковых числе работает корректно
3. Сортировка массива из 1000 случайных элементов. Проверить что 10 случайных пар элементов массива после сортировки упорядочены (их пары больший тот, чей индекс больше)
4. Сортировка пустого массива работает корректно
5. Сортировка массива из 1 500 000 000 элементов работает корректно (если на вашем компьютере 8+ Гб памяти)
Реализация и тестирование хэш-таблицы
В данной лабораторной работе необходимо реализовать Хэш-таблицу (https://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0).
Хэш-таблица – это ассоциативный контейнер, позволяющий быстро находить объекты по т.н. ключу.
Структура данных должна иметь следующую структуру публичных методов:
class HashTable
{
/// <summary>
/// Конструктор контейнера
/// </summary>
/// <param name="size">Размер хэ-таблицы</param>
public HashTable(int size)
{
}
/// <summary>
/// Метод складывающий пару ключь-значение в таблицу
/// </summary>
/// <param name="key"></param>
/// <param name="value"></param>
public void PutPair(object key, object value)
{
}
/// <summary>
/// Поиск значения по ключу
/// </summary>
/// <param name="key">Ключь</param>
/// <returns>Значение, null если ключ отсутствует</returns>
public object GetValueByKey(object key)
{
}
}
На время разработки можете использовать системный контейнер Dictionary<Key,Value>, однако после завершения разработки тестов от него нужно избавиться. Системный контейнер не обязательно получает размер в параметре конструктора: он поддерживает динамическое расширение. Вашей структуре не обязательно поддерживать эту возможность: можно полагаться на то, что в неё не будет добавлено больше чем size элементов.
Тесты:
1. Добавление трёх элементов, поиск трёх элементов
2. Добавление одного и того же ключа дважды с разными значениями сохраняет последнее добавленное значение
3. Добавление 10000 элементов в структуру и поиск одного из них
4. Добавление 10000 элементов в структуру и поиск 1000 недобавленных ключей, поиск которых должен вернуть null
Реализация и тестирование очереди с min-статистикой
В данной лабораторной работе нужно реализовать структуру данных со средующей структурой публичных методов:
class QueueWithMinStats
{
/// <summary>
/// Добавить в очередь значение
/// </summary>
/// <param name="value">значение</param>
public void Enqueue(int value)
{
}
/// <summary>
/// Получить значение из очереди
/// </summary>
/// <returns>значение</returns>
public int Dequeue()
{
}
/// <summary>
/// Текущий минимум среди элементов в очереди
/// </summary>
public int CurrentMiminum
{
get
{
}
}
}
Про очередь можно прочитать тут: https://ru.wikipedia.org/wiki/FIFO
Структура поддерживает добавление целого числа в очередь, извлечение целого числа из очереди и получение текущего минимума среди элементов в очереди. В случае отсутствия элементов в очереди при запросе минимума допускается выбрать одно из двух поведений:
1. Вернуть int.MaxValue
2. Выбросить исключение QueueIsEmptyException (определить класс исключения рядом)
Тесты:
1. Добавление тысячи элементов, затем извлечение тысячи элементов, с проверкой минимума на каждом шаге
2. Добавление одного элемента и извлечение этого же элемента тысячу раз с проверкой минимума на каждом шаге.
Разработка классов модели данных для приложения "Сбор данных"
Цель: создание приложения сбора данных. В этой лабораторной работе нужно описать предметную область в виде набора классов данных. В следующих лабораторных работах необходимо реализовать заполнение этих классов и сохранение их в файл.
Вам нужно создать приложение, которое позволит пользователю хранить данные выбранной вами предметной области в файле.
Ваше приложение содержит главную форму, на которой располагаются средства управления и кнопки "Сохранить в файл" и "Загрузить из файла".
Данные сохраняются в формате XML при помощи механизма XML-сериализации.
Рекомендации по выбору предметной области:
Допустим, вы выбрали предметную область "Заполнение штрафа инспектором ГИБДД". Тогда на вашей форме должен быть TextBox для ввода ФИО инспектора, ФИО нарушителя, описания нарушения и места нарушения.
Также должен быть TextBox с маской для ввода номера автомобиля. DateEdit для ввода даты. ListBox для ввода свидетелей и понятых (количество не известно заранее).
Ваша программа должна предусматривать возможность сохранить все эти данные в файл и считать их из файла.
Допустим, вы выбрали предметную область "Карта осмотра пациента врачём".
Тогда ваша программа будет собирать информацию о ФИО, СНИЛС, номере полиса и месте осмотра.
Также у вас будет лист с перечислением диагнозов и назначенного по поводу диагноза лечения (и то и другое строка).
Количество диагнозов заранее неизвестно.
Требование к выбранной предметной области:
0. В выбранной предметной области должна быть частица смысла из реального мира. Не надо собирать информацию о сепуляции сепулькариев.
1. Должны быть представлены разные типы данных: строки, целые числа, дробные числа, даты, перечисления, списки. Но смысл важнее. Если в вашей предметной области нет дат и дробных чисел - так тому и быть.
2. Списки должны быть в каждой предметной области. Даже если в этом нет смысла.
Собираемые вами данные должны иметь динамически расширяемый набор чего-либо.
Инспектор ГИБДД должен получить возможность ввести миллион разных свидетелей.
Врач может ввести всю МКБ ВОЗ (классификацию болезней), при желании - по нескольку раз.
3. Использование примеров в качестве предметной области не допускается.
Разработка программы "Сбор данных" для заполнения объектов модели данных
Описано выше
Разработка функции сохранения в файл и загрузки из файла в приложении "Сбор данных"
Для сохранения в файл нужно воспользоваться классами XmlSerializer, OpenFileDialog, SaveFileDialog.
Разработка Web-страницы отображения данных файлов программы "Сбор данных" с применением технологии ASP.NET MVC 5
В этой лабораторной работе нужно разработать web-сайт, основанный на технологии ASP.NET MVC, который будет сохранять и отображать данные приложения «сбор данных».
Для выполнения функций, сайт должен содержать страницу загрузки файла с данными, страницу списка загруженных данных и страницу.
Разработка базы данных программы "Сбор данных" с применением EntityFramework
База данных, поддерживающая хранения данных сайта для предыдущей лабораторной работы.
Разработка функции вывода печатных форм в приложении "Сбор данных"
Страница скачивания Excel-представления веб-сайта «Сбор данных». Для это применяется компонент EPPLus. Печатную форму можно скачать с сайта обратившись по ссылке к методу Download. Примерное содержимое метода Download
public ActionResult Download(int resoureId)
{
var ctx = new ApplicationDbContext();
var g = ctx.YourTableName.Find(groupid);
ExcelPackage pkg;
using (var stream = System.IO.File.OpenRead(HostingEnvironment.ApplicationPhysicalPath + "template.xlsx"))
{
pkg = new ExcelPackage(stream);
stream.Dispose();
}
var worksheet = pkg.Workbook.Worksheets[1];
worksheet.Name = g.Name;
worksheet.Cells[1, 2].Value = g.Name;
// Заполнение файла Excel вышими данными
var ms = new MemoryStream();
pkg.SaveAs(ms);
return File(ms.ToArray(), "application/ooxml", (g.Name??"Без Названия").Replace(" ","")+".xlsx");
}