Разработка Windows-приложения для бинарного поиска в массиве

Введение__________________________________________________________________________________________

1. Теоретическая часть________________________________________________________________________________

2. Описание программного продукта.

2.1. Общие сведения.

2.2. Функциональное назначение.

2.3. Описание логической структуры и реализации.

2.4. Используемые технические средства.

2.5. Вызов и загрузка.

2.6. Входные и выходные данные.

2.7. Описание тестовых прогонов.

2.8. Инструкция по использованию программы.___________ Заключение_______________________________________________________________________

Аннотация

Тема работы: Разработка Windows-приложения для бинарного поиска в массиве.

Цель работы: создание графического приложения на языке программирования высокого уровня C# для реализации алгоритма бинарного поиска в массиве.

Объем работы: 33 страницы.

Количество рисунков: 15.

Количество таблиц: 3.

Количество приложений:

1.Оглавление  

Введение   5

1. Теоретическая часть   7

1.1. Основы C#   7

1.2. Поиск в массиве   12

2. Описание программного продукта   17

2.1. Общие сведения   17

2.2. Функциональное назначение  17

2.3. Описание логической структуры и реализации   17

2.4. Требования к техническому обеспечению   21

2.5. Вызов программы   21

2.6. Входные и выходные данные   21

2.7. Описание тестовых прогонов   21

2.8. Инструкция по использованию программы   23

Заключение   26

Список использованных источников   28

Приложение  30

Введение

В современном мире информационные технологии и компьютеры занимают очень важное место в повседневной деятельности и развитии каждого человека. Практически любая профессия сегодня, так или иначе, связана с использованием вычислительных устройств и новейших технологий. Однако мало кто задумывается о том, что для возможности полноценного выполнения поставленных задач компьютеру требуется программное обеспечение - некоторое приложение, целью которого является обработка данных по определенным алгоритмам. Для разработки программных приложений используются специальные языки - языки программирования, одним из примеров которых является C# [2].На сегодняшний день можно выделить целый ряд причин, по которым программисты предпочитают использовать язык C# в качестве основного языка - его конструкции удобны, понятны и логичны. Кроме того, этот язык обладает поддержкой компании Microsoft, которая также разработала среду программирования - Visual Studio. Эта среда предоставляет широкий выбор средств диагностики и редактирования программного кода, что упрощает процесс создания программ, делая его эффективным и быстрым. Также стоит упомянуть и о библиотеке базовых классов, которые идут в комплекте с платформой .NET. Задача этих классов - реализация большинства рутинных операций, с которыми сталкивается рядовой программист в своей деятельности. Таким образом, использование базовых средств платформы и языка позволяет быстро и легко создавать программы практически любой сложности [1].Но не стоит забывать и о недостатках. В первую очередь сюда относится перечень минимальных требований к программному и аппаратному обеспечению компьютера, так как платформа .NET требует большого количества ресурсов. Во-вторых, грамотное составление программного кода требует от программиста определенной теоретической базы. Однако, не смотря на это, достоинства языка C# существенно превосходят его недостатки, поэтому большое количество профессионалов при выборе языка программирования останавливаются именно на языке C# [8].Тема данной курсовой работы - «Разработка Windows-приложения для бинарного поиска в массиве».Актуальность рассматриваемой темы объясняется популярностью алгоритмов поиска в современном программировании..При написании работы в качестве опорных источников были использованы следующие: Г. Шилдт – «C# 4.0: полное руководство» и А. Шамшев – «Основы языка C#».1. Теоретическая часть1.1. Основы C#Язык программирования C# является одним из представителей множества объектно-ориентированных языков программирования, разработанных в период 1998-2001 гг. компанией Microsoft под руководством А. Хейлсберга. Изначально цель данного языка заключалась в разработке прикладных программ для платформы Microsoft .NET Framework [10].Свое название язык берет от музыкальной нотации, где символ диез обозначает повышение на полутон звука, соответствующего ноте. В случае программирования данный подход аналогичен названию языка C++, где «++» обозначает операцию инкремента переменной. Также название является игрой с цепочкой преобразований C → C++ → C++++(C#), так как символ «#» может быть представлен из четырех символов «+».По причине существующих технических ограничений на отображение и того факта, что знак диез отсутствует на классической клавиатуре, для отображения названия используется знак номера «#» - это соглашение зафиксировано в спецификации ECMA-334 [6].C# является языком C-подобного синтаксиса. Наиболее близкими к нему являются языки C++ и Java. C# характеризуется статической типизацией и поддерживает объектно-ориентированные особенности, делегаты, перегрузку операторов (сюда же относятся операторы приведения типа), а также атрибуты, свойства, обобщенные методы и типы, анонимные функции с поддержкой замыканий, события, итераторы, исключительные ситуации, комментарии в формате XML и т.д.Основой языка C# стали лучшие черты языков-предшественников, таких как Modula, Pascal, C++, Smalltalk и, особенно Java. В C# нет моделей, которые считаются проблематичными в процессе разработки программных систем. Так, например, данный язык не предоставляет возможность множественного наследования классов, которая доступна в C++ и Java. Эта особенность избавляет разработчика от избыточных ошибок еще на этапе проектирования будущей структуры программы [7].Одной из задач языка C# была задача создания прикладного языка общеязыковой исполняющей среды (Common Language Runtime, CLR - исполняющая среда для байт-кода, в которой компилируются программы, написанные на языках программирования, совместимых с платформой .NET) [3].Среда CLR поддерживает функциональное развитие языка C#. Кроме того, именно она предоставляет разработчику множество возможностей, которые отсутствуют в классических языках программирования. Ярким примером такой возможности является технология сборки мусора, которая полностью отсутствует в C#, так как она реализуется средой CLR.Развитие информационных технологий способствовало развитию языка программирования C#. Компания Microsoft постоянно обновляет список доступных технологий, компонентов и библиотек. Кроме того, развитие глобальной сети Интернет позволило создавать web-приложения на языке C#, опираясь на технологии ADO+, SOAP, COM+ и BiztalkFramework.Разработчики языка C# хотели создать универсальный язык, позволяющий успешно сочетать в себе выразительность и простоту существующих объектно-ориентированных языков с мощными возможностями C++, из которого были взяты все основные языковые конструкции. Так, например, в языке C# можно встретить такие типы, как перечисления и структуры, отсутствующие в Java. Еще одним предшественником в области синтаксиса C# является язык VisualBasic, из которого взяты понятия свойств классов.Одним из недостатков C# являются операции, критичные по продолжительности исполнения. Этот факт объясняется тем, что в С# нет некоторых ключевых моментов, необходимых для создания высокопроизводительных приложений. Так, например, в нем отсутствуют подставляемые деструкторы и функции, исполнение которых гарантировано в определенных местах программного кода [11].Таким образом, к характерным особенностями языка C# относятся:полный набор основных типов данных, доступных в C++;поддержка технологии объектно-ориентированного программирования, в том числе наследование интерфейсов, перегрузка операторов и виртуальных функций;наличие стандартной библиотеки шаблонных классов .NET, а также возможность легкого использования Windows API;автоматическое освобождение динамической памяти;автоматическая генерация XML-документов;возможность добавления меток в виде атрибутов не только классам, но и методам. Эта особенность является полезной в случаях документирования, что позволяет воздействовать на процесс компиляции (например, пользуясь данной особенностью, можно особым образом помечать методы, которые необходимо компилировать исключительно в режиме отладки);поддержка событий и свойств в стиле Visual Basic;реализация прямого доступа к памяти и использование указателей (хотя C# разработан таким образом, что позволяет обходиться без этих особенностей);быстрое и легкое изменение ключей компиляции, с помощью которых формируются библиотеки компонентов .NET или исполняемые файлы, используемые впоследствии другим программным кодом аналогично элементам управления ActiveX (компоненты СОМ);создание динамических web-страниц ASP.NET [9]..NET Framework дает программисту определенный базовый набор различных функций. Каждая функция принадлежит какому-то конкретному классу. Классы группируются по пространствам имен. Эти пространства обладают вложенной структурой и могут быть представлены в виде иерархии Для навигации между пространствами в C# используется ключевое слово «using».Прикладные программные продукты используют собственные пространства имен, определяемые разработчиком. Наиболее популярным и масштабным пространством имен является системное пространство (System). При компиляции программного модуля транслятор по полному имени функции (если используется оператор using – то по восстановленному) находит ее код, который и используется в процессе выполнения сборки. В языке программирования C# система типов характеризуется типами двух категорий. В свою очередь, каждая категория содержит подкатегории: типы-значения и типы-ссылки.На рисунке 1.1 изображена схема типов языка C#.Рисунок 1.1 – Схема типов языка C#Также стоит отметить, что язык C# позволяет программисту создавать собственные типы данных.Простыми (элементарными) типами называются такие типы данных, имена и основные свойства которых заранее известны компилятору. Для работы с такими типами данных компилятору не требуется дополнительная информация.К простым типам относятся:целые числа (int);числа с плавающей точкой (float);decimal;логический тип (bool).При создании объекта простого типа обязательно происходит его первоначальная инициализация - в него помещается некоторое базовое значение данного типа. Реализация этой операции относится к специальным конструкторам, которые недоступны для модификации.Наряду с простыми типами, существуют еще и производные - типы, требующие предварительного объявления.Основные отличия ссылочных типов от типов-значений представлены в таблице 1.1.Таблица 1.1 – Отличия типов-значений и ссылочных типовТип-значениеСсылочный типСодержимоеЗначениеСсылкаХранениеВ стекеВ динамической памятиЗначение по умолчанию0, false, ‘\0’nullОсобенности копированияКопируется значениеКопируется ссылкаОбъявление любого класса или структуры в языке C# основано на объявлении предопределенного класса Object (наследование от класса Object). В результате этого разработчик получает возможность вызова от имени объектов-представителей любой структуры или класса методов-наследников класса Object. В частности, метода ToString, который предназначен для получения строкового (значение типа string) представления объекта.Также в C# существует важное ограничение на использование объектов размерных типов - так, необходимым условием использования этих объектов является их явная инициализация.1.2. Поиск в массивеОдной из наиболее распространенных операций при работе с массивами является операция поиска элемента по его значению. Существует несколько различных подходов для решения данной задачи:поиск перебором – в том случае, когда имеется массив данных, заполненный в произвольном порядке, и больше нет ни какой дополнительной информации, единственным решением поиска является полный перебор элементов массива до тех пор, пока нужный элемент не будет найден. Очевидно, что в худшем случае (когда искомый элемент является последним) придется просмотреть все элементы массива, что будет очень затратно на больших объемах данных;поиск с барьером – предыдущий вид поиска требовал ряда дополнительных операций – постоянного увеличения счетчика, отвечающего за индекс массива, на каждой итерации, а также проверка логического выражения достижения конца массива. От этих операций можно избавиться путем изменения логического выражения. Для этого в массив добавляется еще один элемент – «барьер», позволяющий не выходить за границы массива. Таким образом, если по завершении алгоритма поиска найденный индекс является индексом барьера, искомый элемент будет отсутствовать;бинарный поиск – для того чтобы упростить процесс поиска, необходимы дополнительные данные. Самый простой способ при этом – упорядочить элементы массива. Бинарный поиск на каждой итерации сокращает размер просматриваемого массива в два раза. Первая операция сравнения выполняется для центрального элемента массива. Если он больше искомого, дальнейший поиск будет вестись на левой половине массива, иначе – на правой. При этом в качестве элемента сравнения всегда выбирается центральный элемент из рассматриваемого участка массива.Очевидно, что поиск элемента в заранее отсортированном массиве будет максимально быстрым. Для реализации сортировки также существует несколько алгоритмов, эффективность которых оценивается двумя критериями:количество произведенных сравнений;количество перестановок элементов.Важно отметить, что для перестановки элементов необходимо использование дополнительной переменной. При этом алгоритм перестановки будет состоять из трех шагов:сохранение значения первого элемента в промежуточной переменной;запись значения второго элемента в первый элемент;запись значение промежуточной переменной во второй элемент [4].Принято выделять три класса алгоритмов сортировки:с помощью включения – при использовании данных алгоритмов массив делится на две части – упорядоченную и неупорядоченную. На начальном этапе в упорядоченную часть входит только первый элемент массива. Далее, на каждом шаге из неотсортированной части выбирается один элемент и вставляется в отсортированную часть таким образом, чтобы не нарушать свойство упорядоченности. На рисунке 1.2 представлены две первых итерации данного алгоритма [12].Рисунок 1.2 – Первые две итерации алгоритма прямого включенияЗдесь упорядоченная и неупорядоченная части отделены вертикальной чертой. Полная сортировка массива приведена на рисунке 1.3.Рисунок 1.3 – Сортировка с помощью прямого включенияАлгоритм прямого включения достигает наибольшей эффективности в том случае, когда в массиве уже имеется некоторая упорядоченная часть. Худшая эффективность наблюдается тогда, когда элементы массива отсортированы в обратном порядке. Модификацией данного алгоритма является метод с двоичным включением, построенный на базе двоичного поиска, который используется при вставке элемента в упорядоченную часть. Однако использование двоичного поиска влияет лишь на количество сравнений. С точки зрения компьютера данные алгоритмы не являются удобными в силу того, что включение элемента с дальнейшим сдвигом остальной части массива является очень не экономной операцией;с помощью выбора – в данном случае исходный массив также разбивается на две части. Однако, сам алгоритм полностью противоположен предыдущему – на каждой итерации ищется один элемент исходной последовательности, обладающий наименьшим или наибольшим значением (в зависимости от цели сортировки), и уже этот элемент помещается в конец готовой последовательности. До начала сортировки упорядоченная последовательность считается пустой. Полная сортировка массива методом прямого выбора приведена на рисунке 1.4. Рисунок 1.4 – Сортировка с помощью прямого выбораВажно отметить, что в процессе работы данного алгоритма количество произведенных сравнений не зависит от исходного порядка элементов. В общем случае алгоритм с прямым выбором, как правило, предпочтительнее алгоритма прямого включения. Однако если элементы вначале упорядочены или почти упорядочены, алгоритм с прямым включением выполнит сортировку быстрее;с помощью обмена – в основе данной группы алгоритмов лежат операции сравнения и перестановки пар соседних элементов до тех пор, пока все элементы массива не будут упорядочены. Наиболее простым алгоритмом данной группы является пузырьковая сортировка, которая получила свое название по принципу «всплывающего пузырька» - на каждой итерации цикла наименьший элемент поднимается на нужную для него позицию. Полная сортировка массива данным методом приведена на рисунке 1.5.Рисунок 1.5 – Пузырьковая сортировкаОчевидно, что в данном примере три последних итерации являются избыточными. Улучшенным алгоритмом сортировки с помощью обмена является шейкерная сортировка, при которой на каждой итерации цикла чередуется направление просмотра массива. Пример сортировки массива данным методом представлен на рисунке 1.6 [5].Рисунок 1.6 – Шейкерная сортировка2. Описание программного продукта2.1. Общие сведенияОбозначение программы: WindowsFormApp.Наименование программы: Бинарный поиск в массиве.Программное обеспечение, необходимое для функционирования программы: операционная система семейства Microsoft Windows.Язык программирования: C#.Среда разработки: Microsoft Visual Studio.2.2. Функциональное назначениеПрограмма предназначена для реализации процедуры бинарного поиска в массиве случайных чисел.Функциональные ограничения на применение:в программе используются только целые числа;размер исходного массива не превышает 100 элементов.2.3. Описание логической структуры и реализацииНа рисунке 2.1 представлена общая схема алгоритма работы программы, включающего в себя следующие шаги:ввод размерности массива;генерация элементов массива;вывод элементов массива;ввод значения для поиска;сортировка элементов массива;бинарный поиск элемента в массиве;вывод результатов.Рисунок 2.1 - Блок-схема алгоритма работы программыВ результате анализа представленного алгоритма в разрабатываемой программе выделен один класс, реализующий графическую форму и операции сортировки и бинарного поиска в массиве.На рисунке 2.2 представлена разработанная графическая форма программы в режиме конструктора.К элементам данной формы относятся:panel1 - панель для генерации элементов;panel2 - панель для поиска элементов;richTextBox - элемент вывода информации.Рисунок 2.2 - Графическая форма программыВ таблице 2.1 представлена спецификация разработанного класса.Таблица 2.1 - Спецификация класса Form1АтрибутСпособ доступаНазначениеint nprivateРазмерность массиваint[] masprivateМассивВ таблице 2.2 представлена спецификация функций модуля Form1.Таблица 2.2 - Спецификация функций модуля Form1Прототип функцииНазначениеНазначение формальных параметровpublic Form1()Конструктор формыprivate void button1_Click (object sender, EventArgs e)Обработчик нажатия кнопки генерации массиваprivate void button2_Click (object sender, EventArgs e)Обработчик нажатия кнопки поиска элемента в массивеprivate void sort()Пузырьковая сортировка массиваprivate bool binarySearch (int left, int right, int x)Бинарный поиск элемента в массивеleft - левая граница;right - правая граница;x - элемент для поискаРеализация основных функций:private void button1_Click(object sender, EventArgs e) //функция генерации // массива { n = (int)numericUpDown1.Value; mas = new int[n]; Random rnd = new Random(); rtb.Clear(); rtb.AppendText("Исходный массив:\n"); for (int i=0; i mas[mid]) //поиск в правой половине return binarySearch(mid, right, x); //поиск в правой половине else return binarySearch(left, mid, x); //поиск в левой половине return false; }Полный код программы представлен в Приложении.2.4. Требования к техническому обеспечениюДля успешной эксплуатации программного продукта необходим компьютер со следующими минимальными техническими характеристиками:центральный процессор - Intel Core i3;оперативная память - 128 Мб;жесткий диск - 128 Мб;наличие мыши, клавиатуры.2.5. Вызов программыДля запуска программы необходимо кликнуть два раза левой кнопкой мыши по исполняемому файлу программы WindowsFormsApp.exe.2.6. Входные и выходные данныеВ качестве входных данных используются:размерность массива - целое число в диапазоне от 2 до 100;значения для поиска - целое число без каких-либо ограничений на значение.В качестве выходных данных используются:сгенерированные значения массива в диапазоне от -100 до 100;значения отсортированного по возрастанию массива;границы поиска на каждом шаге бинарного поиска;результаты поиска.2.7. Описание тестовых прогонов1. При нажатии кнопки «Сгенерировать» должен отобразиться созданный массив (см. рисунок 2.4).Рисунок 2.4 - Генерация массива2. При попытке поиска незаполненного значения должно выводиться сообщение о соответствующей ошибке (рисунок 2.5).Рисунок 2.5 - Ошибка необходимости ввода данных3. При нажатии кнопки «Искать» должен отображаться отсортированный массив, затем границы отрезков поиска и результаты поиска (рисунки 2.6-2.7).Рисунок 2.6 - Результат успешного поискаРисунок 2.7 - Результат неуспешного поиска2.8. Инструкция по использованию программыДля запуска программы используется исполняемый файл WindowsFormsApp.exe.После запуска программы на экране появляется окно, представленное на рисунке 2.8.Первый шаг работы с программой - задать количество элементов массива при помощи компонента NumericUpDown. Элемент позволяет вводить числа от 2 до 100.После того, как размер задан, необходимо нажать кнопку «Сгенерировать». Результат генерации представлен на рисунке 2.9.Рисунок 2.8 - Окно программы после запускаРисунок 2.9 - Результат генерации массиваОдновременно с генерацией массива на форме появляется панель для поиска элементов. Для ввода значения используется компонент TextBox.После того, как значение введено, необходимо нажать кнопку «Искать». Результат поиска будет отображен в блоке вывода информации справа (рисунок 2.10).Рисунок 2.10 - Результат поискаЗаключениеВ рамках выполнения данной работы была рассмотрена тема «Разработка Windows-приложения для бинарного поиска в массиве».Первый раздел работы - теоретический. В нем представлено краткое описание языка программирования C#. C# является языком C-подобного синтаксиса. Наиболее близкими к нему являются языки C++ и Java. C# характеризуется статической типизацией и поддерживает объектно-ориентированные особенности, делегаты, перегрузку операторов (сюда же относятся операторы приведения типа), а также атрибуты, свойства, обобщенные методы и типы, анонимные функции с поддержкой замыканий, события, итераторы, исключительные ситуации, комментарии в формате XML и т.д.Основой языка C# стали лучшие черты языков-предшественников, таких как Modula, Pascal, C++, Smalltalk и, особенно Java. В C# нет моделей, которые считаются проблематичными в процессе разработки программных систем. Так, например, данный язык не предоставляет возможность множественного наследования классов, которая доступна в C++ и Java. Эта особенность избавляет разработчика от избыточных ошибок еще на этапе проектирования будущей структуры программы.Отдельное внимание в рамках первого раздела уделено алгоритмам поиска и сортировки элементов в массивах данных. Бинарный поиск на каждой итерации сокращает размер просматриваемого массива в два раза. Первая операция сравнения выполняется для центрального элемента массива. Если он больше искомого, дальнейший поиск будет вестись на левой половине массива, иначе – на правой. При этом в качестве элемента сравнения всегда выбирается центральный элемент из рассматриваемого участка массива.Второй раздел работы - практический. В нем представлены общие сведения о программе, ее функциональное назначение, обобщенная блок-схема алгоритма, а также свойства и методы разработанного класса.Полученный программный продукт успешно протестирован.Список использованных источниковАлбахари Дж. C# 5.0 и платформа .NET 4.5 / Дж.Албахари, Б. Албахари. – М.: «Вильямс», 2014. – 590 с.Босуэлл Д. Читаемый код, или Программирование как искусство / Д. Босуэлл, Т. Фаучер. – СПб.: Питер, 2015 – 208 с.Вайсфельд М. Объектно-ориентированное мышление. – СПб.: Питер, 2014. – 304 с.Макконнелл С. Совершенный код. Мастер-класс / Пер. с англ. – М.: Издательство «Русская редакция», 2014. – 896 с.Нейгел К. C# 5.0 и платформа .NET 4.5 для профессионалов - Professional C# 5.0 and .NET 4.5. — М.: «Диалектика», 2016 – 457 с. Рихтер Дж. CLR via C#. Программирование на платформе Microsoft .NET Framework 4.0 на языке C#, 3-е издание. – СПб.: Питер, 2016. – 375 с. Скит Дж. C# для профессионалов: тонкости программирования, 3-е изд.: Пер. с англ. – М.: ООО «И.Д. Вильямс», 2014. – 608 с. Стиллмен Э. Изучаем C#. 3-е изд. / Э. Стиллмэн, Дж. Грин. — СПб.: Питер, 2014. — 816 с.Троелсен Э. Язык программирования C# 5.0 и платформа .NET 4.5, 6-е изд. : Пер. с англ. — М. : «Вильямс», 2014. — 1312 с. Шамшев А.Б. Основы языка C#. – Ульяновск: УлГТУ, 2015. – 132 с. Шаповаленко В.А. Технологии программирования / В.А. Шаповаленко, И.Г. Швайко. – Одесса: Изд-во ОНА им. А.С. Попова, 2016. – 120 с. Шилдт Г. C# Полное руководство. – М.: «Вильямс», 2015. – 1056 с.ПриложениеИсходный код программыusing System;using System.Windows.Forms;namespace WindowsFormsApp{ public partial class Form1 : Form { int n; int[] mas; public Form1() { InitializeComponent(); } private void button1_Click(object sender, EventArgs e) { n = (int)numericUpDown1.Value; mas = new int[n]; Random rnd = new Random(); rtb.Clear(); rtb.AppendText("Исходный массив:\n"); for (int i=0; i mas[mid]) //поиск в правой половине return binarySearch(mid, right, x); //поиск в правой половине else return binarySearch(left, mid, x); //поиск в левой половине return false; } private void button2_Click(object sender, EventArgs e) { if (textBox1.Text == "") MessageBox.Show("Введите значение для поиска!"); else { sort(); rtb.AppendText("Массив после сортировки:\n"); for (int i=0; i