Современный мир пропитан достижениями науки и техники. Наиболее яркой отраслью развития является область информационных технологий. Еще два десятилетия назад люди не знали о существовании мобильных телефонов с сенсорными экранами, безлимитном интернете и прочих технологиях, которые сегодня являются обыденностью. Всем известно, что для работы любого технического устройства необходимо соответствующее программное обеспечение - некоторый код, определяющий функции этого устройства. Основой программного обеспечения является алгоритм [19].

Само понятие алгоритма считается ключевым не для всей информатики. Фактически термин «алгоритм» расположен на границе информатики и математики. Слово «алгорит» произошло от записи «Algorithmi», что соответствует написанию имени великого математика древних времен аль-Хорезми.

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

Известно, что в процессе своего выполнения программа работает с различными данными. Эти данные хранятся в памяти компьютера и используются по мере необходимости. Вид и структуру данных программист определяет самостоятельно. Наиболее распространенным типом данных являются целые числа. Однако, сами по себе числа используются редко - чаще всего они хранятся группами, которые называются массивами. Массив представляет собой одну переменную, в состав которой входит несколько однотипных элементов. Элементами массива могут выступать не только числа, но и другие типы данных - символы, строки и даже более сложные структуры [5].

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

Объектом исследования в работе выступают алгоритмы и структуры данных.

Предмет исследования - массивы данных.

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

Для достижения поставленной цели необходимо решить ряд задач:

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

1 ОСНОВНЫЕ ПОНЯТИЯ

1.1 Классификация языков программирования

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

У языков программирования есть две важные цели:

предоставление программисту специального аппарата для описания действий, которые должны быть реализованы компьютером;
формирование концепции алгоритма [2].

Наиболее распространенная классификация языков программирования - по близости к аппаратному обеспечению - представлена на рисунке 1.

Рисунок 1 - Классификация языков программирования по близости к аппаратному обеспечению

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

Важно отметить, что языки программирования этой эпохи хорошо оптимизировались в соответствии с аппаратной архитектурой каждого конкретного компьютера, для которого они создавались. Такой поход гарантировал высокие показатели эффективности реализемых вычислений, однако он сопровождался рядом недостатков:

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

Языки данного поколения называются машинно-ориентированными языками. Они представляют собой набор операторов и изобразительных средств, полностью зависимых от особенностей кадого конкретного компьютера (структуры памяти, системы команд и т.п.)

Машинно-ориентированные языки гарантируют:

высокие показатели качества программ - они обладают малым объемом кода и большой скоростью выполнения;
максимально полное использование аппаратных ресурсов компьютера;
предсказуемость объектного кода и запросов выделения памяти.

Таким образом, ранние языки программирования очень сильно зависели от имеющейся среды вычислений, и примерно соответствовали современным машинным кодам или языкам ассемблера [14].

Следующее поколение принято называть языками программирования высокого уровня. Их характерным отличием является повышение эффективности труда разработчиков за счет абстрагирования от деталей конкретного аппаратного обеспечения.

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

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

Важно отметить, что появление языков программирования высокого уровня снизило зависимость программ от аппаратного обеспечения - это было достигнуто за счет использования трансляторов [4].

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

С появлением высокоуровневых языков ключевые слова и функциональные операторы стали более осмысленны по сравнению с машинными кодами, что также благоприятно сказалось на производительности программистов [9].

Обучение новым языкам требовало дополнительных временных затрат, при этом эффективность реализации программ на прежнем аппаратном обеспечении несколько снижалась. Однако это были временные трудности - большинство первых высокоуровневых языков остается популярным и сегодня.Ярким примером этого факта являются FORTRAN, APL и C, реализующие вычислительные алгоритмы. Язык C за время своего развития успел несколько раз переродиться в C++ и C#, однако, его базовые конструкции остаются неизменны.

Стоит отметить закономерность, что чем выше уровень языка, тем меньшая величина трудоемкости программирования на нем. Машинные команды современных компьютеров крайне редко используются в программировании.

Существует несколько видов языков программирования высокого уровня. Так, например, процедурно-ориентированные языки (Ada, ALGOL, BASIC, C, COBOL, FORTRAN, Pascal) построены на использовании пошагового описания алгоритма, что является причиной некоторых трудностей в процессе подготовки некоторых задач к решению.

Непроцедурные языки, которые также называются проблемно-ориентированными, состоят только из описаний и не обладают собственными командами или инструкциями. Примером непроцедурного языка является Пролог (сокращение от «ПРОграммирование ЛОГики»), широко распространенный в сфере искусственного интеллекта [7].

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

Принято выделять несколько стилей:

неструктурный - предполагает использование команды безусловного перехода - goto. Примерами языков данной группы являются FORTRAN и BASIC. Существование данного стиля объясняется особенностями исполнения машиных кодов. Основоположником данного стиля является язык ассемблера, в котором команда безусловного перехода является обязательной. В языках высокого уровня не рекомендуется использование данной команды, так как оно способствует возникновению большого числа ошибок и усложняет процесс редактирования архитектуры программы;
структурный - в основе данного стиля лежит две идеи:
- всякая задача может быть представлена в виде большого числа более мелких подзадач, каждая из которых решается отдельной функцией или процедурой. Такой подход принято называть декомпозицией. В этом случае проектирование программы реализуется по принципу «сверху вниз»: в первую очередь выявляются все модули, необходимые для решения задачи, а только потом ведется процесс разработки. Эта идея с использованием локальных имен переменных, позволяет создавать масштабные проекты большими коллективами программистов;
- алгоритм любой сложности может быть реализован с использованием всего трех управляющих конструкций: следование, ветвление и цикл, что позволяет избавиться от оператора безусловного перехода goto;

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

логический - языки данного стиля предоставляют программисту лишь средства постановки задачи, при этом решение возлагается на компьютер. Примерами данных языков являются Пролог и Симула. На сегодняшний день данное направление языков является наименее развитым, так как утратило собственную актуальность по причине отсутствия реальных результатов;
объектно-ориентированный - основной идеей языков данного направления является отображение объектов, их свойств и связей из реального мира с помощью специальных структур - классов. Каждый класс содержит набор полей (свойств) и методов - процедур или функций для управления объектом соответствующего класса. Примерами объектно-ориентированных языков являются Java и C++;
функциональный - основой данного стиля является понятие "черного ящика", характеризующегося некоторым набором входных данных - P, и выходным результатом - r. При этом поведение программы описывается формлулой 1:

f(P) = r (1)

Все действия в таких языках программирования выполняются с помощью функциональных вызовов. В силу того, что каждая функция возвращает какое-то значение, оно может быть использовано в виде аргумента другой функции. такой подход позволяет строить очень сложные выражения в функциональной форме. Одним из первых языков данной группы является язык «Лисп». Также сюда относятся языки, способные изменять алгоритм собственной работы в зависимости от набора входных данных [16].

1.2 Этапы решения задачи на компьютере

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

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

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

Существует три способа записи алгоритмов:

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

Наиболее распространенным является графический способ – запись алгоритма в виде блок-схемы, которая отображает его структуру, отдельные элементы и взаимосвязи между ними. Блок-схема алгоритма - совокупность специальных блоков, которые соединяются стрелками, определяющими порядок выполнения. Каждый блок может содержать уникальный номер и краткую характеристики выполняемых функций.

Решение задачи на компьютере достигается за счет исполнения программы. Схема процесса подготовки задачи к решению на компьютере изображена на рисунке 2.

Рисунок 2 - Этапы решения задачи на компьютере

Первый этап - постановка задачи - заключается в описании целей задачи и условий ее решения. Бывают случаи, когда поставленная задача требует разработки принципиально новых теорий и подходов, однако, чаще всего ситуация может быть описана в уже существующих понятиях.

Следующий этап - формализация задачи и выбор метода решения. Для того, чтобы решение задачи было возможно реализовать на компьютере, она должна быть записана в соответствующей форме. Для этого необходимо указать перечень исходных данных, определить начальные условия и необходимую точность вычислений. Кроме того, важно отметить все существующие ограничения (например, на время решения). Чаще всего результатом данного этапа является формулирование математической модели задачи.

Третий этап - разработка алгоритма. В результате формализации получается некоторый список формул, которые должны использоваться при решении задачи. Чаще всего поиск решения зависит от каких-либо условий, поэтому однозначно сказать по какому пути необходимо решать задачу нельзя. Это объясняет тот факт, что исходная задача разбивается на несколько элементарных шагов. Такой путь решения задачи –последовательность шагов, необходимых для выполнения, позволяющих перейти из исходного состояния к желаемому новому состоянию, принято называть алгоритмом решения задачи.

Следующий шаг - написание программы и подготовка ее к вводу в компьютер. Основной задачей этого шана является запись полученного алгоритма на каком-либо языке программирования. При выборе языка программирования стоит уделять внимание не только критериям простоте написания программы и сокращения сроков отладки. На практике часто бывают случаи, когда разрабатываются программы, предназначенные для многократного использования. При этом очень важно добиться их максимальной эффективности.

Финальный этап - отладка программы и ее выполнение на компьютере. Данный этап распадается еще на два:

тестирование программы - представляет собой поиск ошибок в полученной программе;
отладка программы - устранение найденных ошибок. Согласно статитстике время, затрачиваемое на отладку программы обычно составляет до 40% всего времени разработки [3].

1.3 Алгоритм и его свойства

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

Каждый алгоритм обладает рядом свойств:

конечность - алгоритм состоит из определенного конечного числа блоков. Количество шагов алгоритма в процессе выполнения программы также должно быть конечно;
понятность - любой шаг алгоритма представляет собой элементарную операцию, понятную исполнителю этого алгоритма;
дискретность - решение задачи разбивается на ряд подзадач, решаемых друг за другом. При этом решение каждой подзадачи выполняется за конечный промежуток времени;
детерминированность (определенность) - всякий шаг алгоритма должен однозначно пониматься исполнителем этого алгоритма. По завершении выполнения каждого шага однозначно известно, какой шаг будет следующим;
результативность - на вход алгоритму поступают некоторые данные. Результат работы алгоритма - обработка этих данных. Если по каким-либо причинам решение задачи не может быть найдено, должно выводиться соответсвующее сообщение;
массовость - алгоритм должен разрабатываться для решения широкого класса задач. Другими словами - он должен находить правильное решение задачи на любых наборах входных параметров;
эффективность - известно, что одна и та же задача может решаться несколькими способами и за разные промежутки времени. Эффективность подразумевает минимальное число блоков в алгоритме, обеспечивающих нахождение решения задачи с заданной точностью [8].

1.4 Выводы

В рамках данной главы приведена классификация языков программирования по нескольким признакам, описаны основные этапы решения задачи на компьютере, а также выделены основные свойства алгоритмов.

2 ЦИКЛИЧЕСКИЕ АЛГОРИТМЫ И МАССИВЫ ДАННЫХ

2.1 Алгоритмы циклической структуры

Цикл представляет собой алгоритмическую конструкцию, предназначенную для реализации выполнения некоторой группы операторов определенное количество раз. Данная группа операторов называется телом цикла. Число обращений к телу цикла определяется значением параметра цикла. Исходное значение этого параметра определяется программистом до обращения к циклу. На каждой итерации цикла его параметр изменяется, и при новой итерации осуществляется проверка некоторого условия соответствия значения параметра цикла определенной постоянной величине. Данная величина является признаком окончания цикла.

Принято выделять три вида циклических алгоритмов:

с предусловием («пока») - проверка окончания выполнения цикла предшествует телу цикла. Схематичное представление данного цикла приведено на рисунке 3. Стоит отметить, что тело данного цикла может ни разу не выполниться - в том случае, когда начальное условие ложно;
с постусловием («до») - тело цикла предшествует проверке условия окончания цикла. Схематичное представление данного цикла приведено на рисунке 4. Характерным свойством данного цикла является тот факт, что он всегда выполняется хотя бы один раз;
с параметром - данный цикл использует некоторую переменную, которая называется счетчиком. Схематичное представление данного цикла приведено на рисунке 5. До начала первой итерации счетчик инициализируется некоторым исходным значением. По завершении каждой итерации значение счетчика изменяется по заданным правилам, после чего новое значение сравнивается с указанным граничным. Если граничное значение не достигнуто, тело цикла выполняется еще раз, иначе - завершается [13].

Рисунок 3 - Схема цикла с предусловием

Рисунок 4 - Схема цикла с постусловием

Рисунок 5 - Схема цикла с параметром

Чаще всего в качестве начальных значений используются ноль или единица. Коэффициент изменения определяется языком программирования. Некоторые языки программирования позволяют испольховать произвольные приращения, определяемые программистом, а некоторые (например, Pascal) используют лишь операции инкремента и декремента.

2.2 Структуры данных

Ранее говорилось, что ключевым элементом программы является алгоритм. Алгоритм определяет процесс обрабтки некоторого набора входных данных.

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

Некоторые языки программирования требуют, чтобы все переменные, аргументы и возвращаемые значения функций и процедур, используемые в программном коде, были объявлены еще до их использования. Примерами таких языков являются АЛГОЛ, C, PASCAL.

В некоторых языках такого требования нет. Переменные в них приобретают типы данных в зависимости от первого присвоенного значения. В таких языках чаще всего отсутствует функция приведения типов данных. Такие языки называются языками со статической типизацией. Однако есть языки, в которых тип переменной может меняться непосредственно в процессе исполнения программы. Такой подход называется динамической типизацией данных [9].

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

Оба подхода обладают своими плюсами и минусами. Использование динамической неявной типизации позволяет расширять возможности использования переменных, за счет чего избавляет разработчиков от ряд проблем, связанных с объявлением переменных и постоянным и контролем соответствия типов. Кроме того, при помощи этого подхода создаются более универсальные программные модули, способные легко интегрироваться друг с другом. Однако испоьлзование динамической типизации возлагает на программиста большую ответственность, так как в процессе выполнения программы могут возникать ситуации, приводящие к попытке перемножению строковых данных или деления на переменную логического типа.

Статическая компиляция позволяет выявлять ошибки, связанные с несоответствием типов данных, еще на этапе компиляции. Очевидно, что чем больше программный код, тем больше ошибок в нем может содержаться.

Базовыми (простыми) типами данных называются объекты, не обладающие внутренней структурой. Примерами таких типов данных являются числа, символы, логические переменные.

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

Самой распространенной структурой данной является массив. Массивом называется проиндексированный набор однотипных элементов. В некоторых языках программирования индекс элементов массива может изменяться лишь в диапазоне от единицы до N (например, BASIC) или от нуля до N–1 (например, C). Данный факт объясняется смещением элемента от адреса начала массива в памяти. Кроме того, некоторые языки повзоляют программисту устанавливать собственные границы изменения индекса для каждого измерения массива [19].

Массивы бывают статические и динамические. При работе со статическими массивами программисты заранее определяют длину массива. Если же это нельзя сделать на начальном этапе, рекомендуется использовать размер с запасом. Размер динамического массива может изменяться во время выполнения программы.

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

В некоторых языках программирования существует особый вид массивов – ассоциативные массивы. Характерной чертой этого типа данных является тот факт, что вместо индекса может использоваться не только целочисленная переменная, но и любой другой тип данных. Другими словами, ассоциативный набор представляет собой некоторый словарь «ключ-значение», поддерживающий ряд операций:

добавление пары элементов;
поиск по ключу (индексу);
удаление по ключу.

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

поиск перебором – в том случае, когда имеется массив данных, заполненный в произвольном порядке, и больше нет ни какой дополнительной информации, единственным решением поиска является полный перебор элементов массива до тех пор, пока нужный элемент не будет найден. Очевидно, что в худшем случае (когда искомый элемент является последним) придется просмотреть все элементы массива, что будет очень затратно на больших объемах данных;
поиск с барьером – предыдущий вид поискка требовал ряда дополнительных операций – постоянного увеличения счетчика, отвечающего за индекс массива, на каждой итерации, а также проверка логического выражения достижения конца массива. От этих операций можно избавиться путем изменения логического выражения. Для этого в массив добавляется еще один элемент – «барьер», позволяющий не выходить за границы массива. Таким образом, если по завершении алгоритма поиска найденный индекс является индексом барьера, искомый элемент будет отсутствовать;
бинарный поиск – для того чтобы упростить процесс поиска, необходимы дополнительные данные. Самый простой способ при этом – упорядочить элементы массива. Бинарный поиск на каждой итерации сокращает размер просматриваемого массива в два раза. Первая операция сравнения выполняется для центрального элемента массива. Если он больше искомого, дальнейший поиск будет вестись на левой половине массива, иначе – на правой. При этом в качестве элемента сравнения всегда выбирается центральный элемент из рассматриваемого участка массива [20].

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

количество произведенных сравнений;
количество перестановок элементов.

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

сохранение значения первого элемента в промежуточной переменной;
запись значения второго элемента в первый элемент;
запись значение промежуточной переменной во второй элемент [1].

Принято выделять три класса алгоритмов сортировки:

с помощью включения – при использовании данных алгоритмов массив делится на две части – упорядоченую и неупорядоченную. На начальном этапе в упорядоченную часть входит только первый элемент массива. Далее, на каждом шаге из неотсортированной части выбирается один элемент и вставляется в отсортированную часть таким образом, чтобы не нарушать свойство упорядоченности. На рисунке 6 представлены две первых итерации данного алгоритма [15].

Рисунок 6 – Первые две итерации алгоритма прямого включения

Здесь упорядоченная и неупорядоченная части отделены вертикальной чертой. Полная сортировка массива приведена на рисунке 7.

Рисунок 7 – Сортировка с помощью прямого включения

Алгоритм прямого включения достигает наибольшей эффективности в том случае, когда в массиве уже имеется некоторая упорядоченная часть. Худшая эффективность наблюдается тогда, когда элеменеты массива отсортированы в обратном порядке. Модификацией данного алгоритма является метод с двоичным включением, построенный на базе двоичного поиска, который используется при вставке элемента в упорядоченную часть. Однако использование двоичного поиска влияет лишь на количество сравнений. С точки зрения компьютера данные алгоритмы не являются удобными в силу того, что включение элемента с дальнейшим сдвигом остальной части массива является очень не экономной операцией;

с помощью выбора – в данном случае исходный массив также разбивается на две части. Однако, сам алгоритм полностью противоположен предыдущему – на каждой итерации ищется один элемент исходной последовательности, обладающий наименьшим или наибольшим значением (в зависимости от цели сортировки), и уже этот элемент помещается в конец готовой последовательности. До начала сортировки упорядоченная последовательность считается пустой. Полная сортировка массива методом прямого выбора приведена на рисунке 8. Важно отметить, что в процессе работы данного алгоритма количество произведенных сравнений не зависит от исходного порядка элементов. В общем случае алгоритм с прямым выбором, как правило, предпочти-

Рисунок 8 – Сортировка с помощью прямого выбора

тельнее алгоритма прямого включения. Однако если элементы в начале упорядочены или почти упорядочены, алгоритм с прямым включением выполнит сортировку быстрее [18];

с помощью обмена – в основе данной группы алгоритмов лежат операции сравнения и перестановки пар соседних элементов до тех пор, пока все элементы массива не будут упорядочены. Наиболее простым алгоритмом данной группы является пузырьковая сортировка, которая получила свое название по принципу «всплывающего пузырька» - на каждой итерации цикла наименьший элемент поднимается на нужную для него позицию. Полная сортировка массива данным методом приведена на рисунке 9.

Рисунок 9 – Пузырьковая сортировка

Очевидно, что в данном примере три последних итерации являются избыточными. Улучшенным алгоритмом сортировки с помощью обмена является шейкерная сортировка, при которой на каждой итерации цикла чередуется направление просмотра массива. Пример сортировки массива данным методом представлен на рисунке 10 [10].

Рисунок 10 – Шейкерная сортировка

2.3 Выводы

В рамках данной главы рассмотрены основные виды циклов, а также описаны элементарные структуры данных – массивы.

3 ПРАКТИЧЕСКАЯ ЧАСТЬ

3.1 Элементарные операции при работе с одномерными массивами

Для выполнения практической части используется язык программирования высокого уровня C# и среда разработки Microsoft Visual Studio 2013.

Для работы с массивом его необходимо объявить. В языке программирования C# объявления массива выглядит следующим образом [12]:

const int N = 10;

int[] array = new int[N];

Здесь целочисленная константа N определяет наибольший размер массива.

Для заполнения массива используется генератор случайных чисел, который объявляется следующим образом:

Random rnd = new Random();

Само заполнение массива реализовано циклом с предусловием:

int i = 0;

while (i < N)

{

array[i] = rnd.Next(100);

i++;

}

Для вывода сгенерированных элементов на экран используется цикл с постусловием:

i = 0;

{

Console.Write(array[i] + " ");

i++;

} while (i < N);

Результат выполнения представленного кода приведен на рисунке 11.

Рисунок 11 – Создание массива

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

Для реализации поиска некоторого элемента x методом полного перебора используется следующий код:

Console.Write("Введите элемент для поиска: ");

int x = Convert.ToInt32(Console.ReadLine());

bool f = false;

for (i = 0; i < N; i++)

{

if (array[i] == x)

{

Console.WriteLine("Позиция: " + (i + 1));

f = true;

break;

}

if (f == false)

Console.WriteLine("Элемент отсутствует!");

В данном случае логическая переменная f используется в качестве признака существования искомого элемента в массиве.

Результат выполнения модифицированной программы представлен на рисунках 12-13.

Рисунок 12 – Пример удачного поиска с использованием полного перебора

Рисунок 13 – Пример неудачного поиска с использованием полного перебора

Для реализации бинарного поиска используется специальная функция:

public static int BinarySearch(int[] array, int l, int r, int x)

{

if (l < r)

{

int found = l + (r - l) / 2;

if (array[found] > x) return BinarySearch(array, l, found - 1, x);

else if (array[found] < x) return BinarySearch(array, found + 1, r, x);

else return found+1;

}

else return -1;

}

Для сравнения результатов представленных алгоритмов по времени их исполнения используется специальная переменная типа Stopwatch. Алгоритм ее использования прост – она запускается до начала работы поиска методом sw.Start() и останавливается после его завершения методом sw.Stop().

Код полученной программы представлен в приложении 1, а результат ее выполнения - на рисунках 14-15.

Рисунок 14 – Пример удачного поиска

Рисунок 15 – Пример удачного поиска

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

3.2 Сортировка массивов

В качестве примеров сортировки массивов рассматриваются алгоритмы, описанные ранее.

Код алгоритма сортировки прямым включение выглядит следующим образом:

static void sort_vkl(int[] array)

{

for (int i = 2; i < array.Length; i++)

{

int tmp = array[i];

int j;

for (j = i - 1; j >= 0 && array[j] > tmp; j--)

array[j + 1] = array[j];

array[j + 1] = tmp;

for (int p = 0; p < array.Length; p++)

Console.Write(array[p] + " ");

Console.WriteLine();

}

Результат работы программы, использующей данный алгоритм, представлен на рисунке 16.

Рисунок 16 – Сортировка методом прямого включения

Код алгоритма сортировки прямым выбором выглядит следующим образом:

static void sort_vyb(int[] array)

{

for (int i = 0; i < array.Length - 1; i++)

{

int min = i;

for (int j = i + 1; j < array.Length; j++)

{

if (array[j] < array[min])

min = j;

}

int temp = array[min];

array[min] = array[i];

array[i] = temp;

}

Результат работы программы, использующей данный алгоритм, представлен на рисунке 17.

Рисунок 17 – Сортировка методом прямого выбора

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

Следующий алгоритм сортировки – пузырьковая. Код данного метода на языке C# записывается следующим орабзом:

static void sort_puz(int[] array)

{

for (int i = 0; i < array.Length - 1; i++)

{

for (int j = i + 1; j < array.Length; j++)

{

if (array[j] < array[i])

{

int temp = array[j];

array[j] = array[i];

array[i] = temp;

}

for (int p = 0; p < array.Length; p++)

Console.Write(array[p] + " ");

Console.WriteLine();

}

Результат работы программы, использующей данный алгоритм, представлен на рисунке 18.

Рисунок 18 – Сортировка методом пузырька

Для сравнения – код шейкерной сортировки:

static void sort_shaker(int[] array)

{

int l = 1;

int r = array.Length - 1;

while (l <= r)

{

for (int i = r; i >= l; i--)

if (array[i - 1] > array[i])

{

int temp = array[i-1];

array[i-1] = array[i];

array[i] = temp;

}

l++;

for (int i = l; i <= r; i++)

if (array[i - 1] > array[i])

{

int temp = array[i - 1];

array[i - 1] = array[i];

array[i] = temp;

}

r--;

}

Результат работы программы, использующей данный алгоритм, представлен на рисунке 19.

Рисунок 19 – Шейкерная сортировка

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

Полный листинг программы с различными функциями сортировки приведен в приложении 2.

3.3 Выводы

В рамках данной главы приводится реализация алгоритмов поиска и сортировки, описанных ранее.

ЗАКЛЮЧЕНИЕ

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

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

машинные;
машинно-ориентированные.

Аналогичным образом языки высокого уровня делятся на две группы:

процедурно-ориентированные;
проблемно-ориентированные.

Отдельное внимание в первой главе уделяется этапам решения задачи на компьютере. При этом принято выделять следующие этапы:

постановка задачи;
форрмализация и выбор метода решения;
разработка алгоритма;
составление программы;
отладка и исполнение.

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

Во второй главе непосредственно рассмотрены массивы данных, а также алгоритмы циклической структуры, без которых невозможна работа с массивами.

Принято выделять три вида циклических алгоритмов:

с предусловием («пока»);
с постусловием («до»);
с параметром.

Массивом называется проиндексированный набор однотипных элементов. В некоторых языках программирования индекс элементов массива может изменяться лишь в диапазоне от единицы до N (например, BASIC) или от нуля до N–1 (например, C).

В рамках практической части рассмотрено решение нескольких задач с массивами на языке программирования высокого уровня C#:

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

Албахари Дж. C# 5.0 и платформа .NET 4.5 / Дж.Албахари, Б. Албахари. – М.: «Вильямс», 2013. – 590 с.
Босуэлл Д. Читаемый код, или Программирование как искусство / Д. Босуэлл, Т. Фаучер. – СПб.: Питер, 2012 – 208 с.
Вайсфельд М. Объектно-ориентированное мышление. – СПб.: Питер, 2014. – 304 с.
Громов Ю.Ю. Технология программирования / Ю.Ю. Громов, О.Г. Иванова, М.П. Беляев, Ю.В. Минин – Тамбов: Изд-во ФГБОУ ВПО «ТГТУ», 2013. – 172 с.
Иванова Г.С. Технология программирования. – Москва: Изд-во МГТУ им. Н.Э. Баумана, 2012. – 241 с.
Каширина Н.В. Сопоставительный анализ подготовки специалистов по информационным технология в вузах России и за рубежом / Н.В. Каширина, М.М. Маран. – Москва: Изд-во журнала «Науковедение», 2015. – 20 с.
Макконнелл С. Совершенный код. Мастер-класс / Пер. с англ. – М.: Издательство «Русская редакция», 2012. – 896 с.
Марченко А.Л. C#. Введение в программирование. – М.: Изд-во МГУ, 2015. - 258 с.
Мирошниченко Е.А. Технологии программирования. – Томск: Изд-во ТПУ, 2013. – 124 с.
Нейгел К. C# 5.0 и платформа .NET 4.5 для профессионалов - Professional C# 5.0 and .NET 4.5. — М.: «Диалектика», 2013 – 457 с.
Рихтер Дж. CLR via C#. Программирование на платформе Microsoft .NET Framework 4.0 на языке C#, 3-е издание. – СПб.: Питер, 2012. – 375 с.
Скит Дж. C# для профессионалов: тонкости программирования, 3-е изд.: Пер. с англ. – М.: ООО «И.Д. Вильямс», 2014. – 608 с.
Стиллмен Э. Изучаем C#. 3-е изд. / Э. Стиллмэн, Дж. Грин. — СПб.: Питер, 2014. — 816 с.
Терехов А.Н. Технология программирования. – Москва: Изд-во УИТ, 2016. – 77 с.
Троелсен Э. Язык программирования C# 5.0 и платформа .NET 4.5, 6-е изд. : Пер. с англ. — М. : «Вильямс», 2013. — 1312 с.
Цветкова М.С. Информатика и ИКТ / М.С. Цветкова, Л.С. Великович. – М.: Издательский центр «Академия», 2012. – 352 с.
Цехоня В.И. Технология программирования / В.И. Цехоня, В.Ф. Гузик. – Таганрог: изд-во ТТИ ЮФУ, 2011. – 144 с.
Шамшев А.Б. Основы языка C#. – Ульяновск: УлГТУ, 2015. – 132 с.
Шаповаленко В.А. Технологии программирования / В.А. Шаповаленко, И.Г. Швайко. – Одесса: Изд-во ОНА им. А.С. Попова, 2011. – 120 с.
Шилдт Г. C# Полное руководство. – М.: «Вильямс», 2015. – 1056 с.