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

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

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

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

• тестирование программы - представляет собой поиск ошибок в полученной программе;
• отладка программы - устранение найденных ошибок. Согласно статитстике время, затрачиваемое на отладку программы обычно составляет до 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. Важно отметить, что в процессе работы данного алгоритма количество произведенных сравнений не зависит от исходного порядка элементов. В общем случае алгоритм с прямым выбором, как правило, предпочти-

---

Смотрите также файлы

• Договора и их виды как одна из форм организации коммерческой деятельности по работе с контрагентами (на примере конкретной организации)(Понятие и сущность договора в коммерческой деятельности).pdf

• Современные политические режимы (Типы политических режимов. Тоталитарный, авторитарный и демократический режимы).pdf

• Организация работы предприятия быстрого обслуживания..pdf

• Коммерческие риски и способы их уменьшения (на примере конкретной организации)».pdf

• Оценка качества рыбных товаров (ОКП 926000) на примере рыбы соленой.pdf