СВОЙСТВА И ЭТАПЫ ПОСТРОЕНИЯ АЛГОРИТМА

СВОЙСТВА И ЭТАПЫ ПОСТРОЕНИЯ АЛГОРИТМА Алгоритм представляет собой строгую систему правил, определенную последовательность  действий над некоторыми объектами. Следуя такой системе правил, как инструкции,  различные исполнители будут действовать одинаково и получать одинаковые результаты. Или Алгоритмом решения задачи называется путь решения задачи, определенная  последовательность действий, которую необходимо выполнить для достижения  результата. Основные свойства алгоритмов следующие: 1. Результативность. Алгоритм имеет некоторое число входных величин ­ аргументов.  Цель выполнения алгоритма ­ получение конкретного результата, имеющего вполне  определенное отношение к исходным данным. 2. Определенность. Каждый шаг алгоритма для решения должен быть четко и  недвусмысленно определен, не должен допускать произвольной трактовки. 3. Массовость. Можно применять один и тот же алгоритм для решения множества  однотипных задач, различающихся данными. 4. Дискретность. Алгоритм представлен в виде конечной последовательности шагов:  решение задачи алгоритм сводит к решению отдельных более простых задач. 5. Эффективность. Алгоритм может быть выполнен не просто за конечное, а за разумно конечное время. 6. Конечность. Действуя в соответствии с алгоритмом, за конечное число шагов  обязательно получается решение задачи. Строится бесконечный, сходящийся к  искомому решению процесс. Он обрывается на некотором шаге, и полученное  значение принимается за приближенное решение рассматриваемой задачи. Точность  приближения зависит от числа шагов. 7. Компактность. Это свойство предполагает лаконичность изложения алгоритма. Как  только компактность потеряна, алгоритм в значительной мере теряет право на  существование. Этапы построения алгоритма  Постановка задачи  Построение модели  Разработка алгоритма  Проверка правильности алгоритма  Реализация алгоритма  Анализ алгоритма и его сложности  Проверка программы  Постановка задачи Прежде чем понять задачу, необходимо ее точно сформулировать. Обычно процесс точной  формулировки задачи сводится к постановке правильных вопросов. Перечислим некоторые полезные вопросы: Понятна ли терминология? Что дано? Что следует найти? Как определить решение? Каких данных не хватает и все ли они необходимы? Являются ли какие­то имеющиеся данные бесполезными? Какие сделать допущения? Если задачу необходимо решить математически, то ее постановка должна быть  формализована, т. е. выражена в терминах понятий, обладающих точно определенными  свойствами и находящихся между собой в строго определенных отношениях. Если сказано, что задача поставлена, то предполагается, что известны не только  характеристики существующей ситуации, но и требования к решению задачи.  Формализация постановки задачи позволяет наметить путь, который ведет от постановки решения задачи к ее решению, т. е. провести логический анализ формальной постановки  задачи в результате выявления свойств и отношений между понятиями. Построение модели Если задача четко поставлена, для нее необходимо сформулировать математическую  модель. Выбор модели существенно влияет на остальные этапы в процессе решения.  Математическая формулировка и выбранный метод вычисления являются основой для  определения последовательности действий, приводящих к получению искомого результата. Большинство задач необходимо рассматривать индивидуально. Тем не менее существуют  полезные руководящие принципы:  выбор модели ­ дело искусства;  изучение удачных моделей ­ наилучший способ приобрести опыт в моделировании. Приступая к разработке модели, следует задать, по крайней мере, два вопроса:  Какие известные математические структуры более всего подходят для решения  задачи, если в постановке задачи не указаны те, которые следует использовать?  Существуют ли решенные аналогичные задачи? Сначала рассмотрим необходимость описания математически того, что мы знаем и что  необходимо найти. На выбор соответствующей структуры будут влиять такие факторы,  как удобство представления, простота вычислений, ограниченность наших знаний, а также:  Вся ли важная информация для решения задачи хорошо описана математически?  Существует ли математическая величина, соотносимая с результатом?  Выявлены ли полезные соотношения между характеристиками модели?  Удобно ли работать с моделью? Разработка алгоритма Наиболее распространенными методами разработки алгоритмов можно назвать метод  частных целей и эвристический алгоритм. Для разработки алгоритма методом частных целей необходимо ответить на следующие  вопросы  Можно ли решить хотя бы часть задачи, игнорируя некоторые условия?  Можно ли решить задачу для частных случаев?  Есть ли что­то, что мы не достаточно поняли?  Встречались ли мы с похожей задачей? Можно ли видоизменять ее для решения  задачи? При разработке эвристического алгоритма необходимо помнить, что такой алгоритм  обычно помогает найти хорошие, но не обязательно оптимальные решения. Нередко  эвристический алгоритм имеет быструю и простую реализацию. Современные методы программирования, основанные на структурном подходе,  предусматривают использование специальных приемов, например применение пошаговой  детализации. На первом этапе разработки алгоритм рассматривается в общем виде, как  некоторая совокупность действий для преобразования исходной информации, все  последующие этапы ­ это выявление все более частных особенностей. При записи действий на любом этапе можно учитывать, что исполнителем алгоритма будет компьютер, который умеет совершать только вполне определенные действия, а именно  присваивание, ветвление, циклическое повторение. Поэтому любая детализация должна  приводить к таким конструкциям. Можно привести аналогию между разработкой алгоритма решения задачи на компьютере и  планировкой нового города. Исходными данными могут быть «желаемые параметры»  города ­ географические, экономические, социальные и т. п., а результат ­ реально  построенный город. Разделим процесс строительства на три этапа: 1. Изыскания 2. Подготовка 3. Стройка Теперь этапы можно разрабатывать, доводить до частных действий по отдельности.          Изыскания 1. ЕСЛИ место стройки не N­ская область, то перейти к п. 6, иначе перейти к п. 2 2. Найти площадку для строительства на берегу реки X 3. Исследовать грунт 4. Разработать проект 5. Перейти к этапу ПОДГОТОВКА 6. Перенести строительство на другой срок Подготовка 7. ЕСЛИ все строители имеют жилье, то перейти к этапу СТРОЙКА 8. Построить палатку 9. Построить времянку Стройка 10.И так далее. Таким образом, процесс разработки алгоритма направлен на получение в итоге  последовательности алгоритмических конструкций. Величины в алгоритмах В алгоритмах для величин вводятся специальные символические обозначения. Эти  обозначения аналогичны обозначениям в обычной математике и представляют собой имена  величин или их идентификаторы. Вместо конкретных величин записываются имена  величин, которые при исполнении алгоритма заменяются конкретными для данной задачи  числовыми значениями. Величины могут быть арифметическими, логическими, символьными. Величины, которые  не изменяются в процессе выполнения алгоритма, называются константами. При написании алгоритмов используются понятия простых и индексных переменных  (переменная с индексом). Простая переменная ­ это переменная, значение которой  изменяется в процессе выполнения алгоритма. Переменная с индексом ­ это элемент некоторой заданной последовательности значений, называемой массивом. В формулах, используемых при написании алгоритмов, знак «=» является символом  присваивания, который означает, что вычисленное значение выражения, стоящего справа от этого символа, присваивается переменной, стоящей слева от символа присваивания. Например, выражение а = а + 0.005 означает, что значение а увеличивается на  величину 0.005 и полученный результат присваивается переменной а. При этом старое  значение теряется. Способы записи алгоритмов Любой способ записи алгоритма подразумевает, что всякий описываемый с его помощью  предмет задается как конкретный представитель часто бесконечного класса объектов,  которые можно описывать данным способом. Средства, используемые для записи алгоритмов, в значительной мере определяются тем,  кто будет исполнителем. Если исполнителем будет человек, запись может быть не полностью формализована, на  первое место выдвигаются понятность и наглядность. В данном случае для записи могут  быть использованы схемы алгоритмов или словесная запись. Для записи алгоритмов, предназначенных для исполнителей ­ автоматов, необходима  формализация. Поэтому в таких случаях применяют формальные специальные языки.  Преимущество формального способа записи состоит в том, что он дает возможность  изучать алгоритмы как математические объекты; при этом формальное описание  алгоритма служит основой, позволяющей нам интеллектуально охватить этот алгоритм. Наконец, такой способ записи позволяет описать алгоритм настолько точно, что если будет задан такой алгоритм и заданы значения аргументов (вход), то не будет никаких сомнений  относительно того, каким должен быть результат (выход). Словесная запись алгоритма Команды алгоритма нумеруют, чтобы иметь возможность на них ссылаться. В качестве  примера можно привести словесную запись классического алгоритма Евклида для  нахождения наименьшего общего делителя двух натуральных чисел: 1. Обозревая два числа А и В, переходи к следующему пункту. 2. Сравни обозреваемые числа ((А равно В), А меньше, больше В) и переходи к  следующему пункту. 3. Если А и В равны, то прекрати вычисление: каждое из чисел дает искомый результат. Если числа не равны, то переходи к следующему пункту. 4. Если первое число меньше второго, то переставь их местами и переходи к  следующему пункту. 5. Вычитай второе число из первого, обозревай два числа: вычитаемое и остаток;  переходи к п. 2. Команды такого алгоритма выполняются в естественной последовательности. Форма  команд не формализована. Схемы алгоритмов Такое представление алгоритма более наглядно. Алгоритм представляется  последовательностью графических символов, выполняющих определенные функции, и  связей между ними. Конфигурацию, перечень и размеры условных изображений, а также  правила построения схем алгоритмов устанавливает ГОСТ 19.701­90 «Схемы алгоритмов,  программ, данных и систем». Основные символы, используемые для описания алгоритмов, приведены в таблице 1.1. Таблица 1.1. Таблица описания символов Символ Наименование символа Начало ­ конец алгоритма. Прерывание процесса обработки  информации Данные. Ввод ­ вывод данных. Носитель не определен Процесс. Обработка данных любого вида. Выполнение  определенной операции или группы операций, приводящее к  изменению значения, формы или размещения информации Решение. Функция переключательного типа. Имеет один вход и ряд  альтернативных выходов, только один из которых может быть  активизирован после вычисления условий, определенных внутри  этого символа Подготовка. Модификация команды или группы команд с целью  воздействия на некоторую последующую функцию (инициализация  программы, модификация индекса и др.) Документ. Отображает итоговые данные в удобочитаемой форме. Вывод информации результата на принтер Алгоритм начинается и заканчивается символами «Начало» и «Конец». Для записи внутри  символов команд используется естественный язык с элементами математической  символики. Каждый графический символ схемы имеет один вход и один выход.  Исключение составляет символ «Решение», который имеет один вход и ряд  альтернативных выходов, один из них может быть активизирован после вычисления  условий,] определенных внутри символа. Соответствующие результаты вычисления могут  быть записаны по соседству с линиями, отображающими эти пути. Структуры алгоритмов Существует несколько типов алгоритмов: линейные, разветвляющие, циклические. Линейный алгоритм Имеет простую линейную структуру, в которой все шаги выполняются друг за другом один раз в порядке их следования. Например: Дано X.  Вычислить  Z = У1/2  и  Z1 = 1 /Z ,                         если Y = X2 + 5. Словесное описание линейного алгоритма имеет следующий вид: 1. Ввести X 2. Вычислить Y = X2 + 5 3. Вычислить Z = Y1/2 4. Вычислить Z1 = 1/Z 5. Вывести Z1, Z 6. Конец. Рис. 1.1. Графическое изображение линейного алгоритма Разветвляющийся алгоритм Разветвляющийся алгоритм ­ последовательность выполнения шагов алгоритма изменяется  в зависимости от некоторых условий. Осуществляется выбор одного из двух/нескольких  возможных вариантов. Словесно эта конструкция записывается так: ЕСЛИ условие справедливо, ТО выполнить действия 1, ИНАЧЕ выполнить действия 2. Разветвляющийся алгоритм содержит блок проверки некоторого условия, и в зависимости  от результата проверки выполняется та или иная последовательность шагов (действий). Если есть «действия 1» и «действия 2», то говорят о полной альтернативе(рис.1.2). Рис. 1.2. Полная альтернатива Если же в качестве «действия 2» имеет место формулировка «перейти к п. N», то такая  форма записи называется неполной альтернативой (рис. 1.3). Рис. 1.3. Неполная альтернатива Например, составить алгоритм для вычисления функции:      (X+1,Y>0,) Z =       (X+Y, Y<0.) Словесное описание разветвленного алгоритма имеет следующий вид: 1. Ввести X 2. Если Y > 0, то Z = X + 1 3. Если Y <0  Вывести Z = X + Y 4. Конец. Рис. 1.4. Графическое изображение разветвленного алгоритма Условие ­ это логическое выражение, которое может принимать два значения ­«да», если  условие верно, и «нет», если условие не выполняется. На рис. 1.5 приведена схема  алгоритма Евклида (вычисление НОД), словесная запись которого была приведена выше. Рис. 1.5. Схема алгоритма Евклида ­ определение наибольшего общего делителя Циклический алгоритм Для обозначения многократно повторяющихся действий используются специальные  циклические структуры. Такая структура содержит условие, которое необходимо для  определения количества повторений для некоторой последовательности действий. Основной блок цикла ­ тело цикла ­ производит требуемые вычисления. Вспомогательные  блоки цикла организуют циклический процесс: устанавливают начальное значение и новые  значения данных, проверяют условие окончания циклического процесса. Рис. 1.6. Цикл с предусловием. Тело цикла может не выполняться ни одного раза  Циклический алгоритм позволяет компактно описать большое число одинаковых  вычислений над разными данными для получения необходимого результата. Различают  циклические структуры с предварительным условием (рис. 1.6) ­ циклы с предусловием и  циклические структуры с последующим условием (рис. 1.7) ­циклы с постусловием.  Рис. 1.7. Цикл с постусловием. Тело цикла выполнится хотя бы один раз Для организации любого цикла необходимо следующее: 1. Задать перед началом цикла начальные значения параметров цикла. 2. Изменять параметры цикла перед каждым новым повторением цикла. 3. Проверять условие повторения или окончания цикла. 4. Переходить к началу цикла, если он не закончен, или выходить из цикла. По способу определения числа повторений различают также циклы с неизвестным числом  повторений и циклы с явно заданным числом повторений. Примером цикла с неизвестным  числом повторений является итерационный цикл. Выход из итерационного цикла  осуществляется не после того, как цикл повторится заданное число раз, а при выполнении  условия более общего характера, связанного с проверкой значения монотонно  изменяющейся в цикле величины. Часто эта величина характеризует точность, достигнутую на очередном шаге итерационного процесса, реализуемого алгоритмом. Исполнение (тестирование) алгоритма Чтобы убедиться в правильности алгоритма, необходимо проводить его тестирование, не  дожидаясь рационального окончательного алгоритма. В этом случае для регистрации  исполнения алгоритма указываются шаги алгоритма, аргументы, промежуточные величины, результаты на данном шаге и проверяемые условия. Шаги исполнения дают возможность показать, сколько шагов исполнено на данный момент, за какое число шагов весь алгоритм будет исполнен. Нумерация шагов алгоритма упрощает ориентацию в описании алгоритма и в процессе его исполнения. При этом в каждый момент видно, какой элемент (команда) алгоритма выполняется. Это помогает устранить ошибки. ПЕРЕМЕННЫЕ С ИНДЕКСАМИ. МАССИВЫ. ТАБЛИЦЫ Многие задачи, которые решаются с использованием компьютера, связаны с обработкой  больших объемов информации, представляющей совокупность данных, объединенных  единым математическим содержанием или близких между собой по смыслу. Примером  являются координаты, задающие положение точки в пространстве, коэффициенты системы линейных уравнений, значение некоторой функции в произвольных точках, коэффициенты  многочлена и т. д. Такие данные удобно представлять в виде линейных или прямоугольных  таблиц. В математике табличные величины называются векторами или матрицами. В алгоритме и  программе для представления табличных данных используется понятиемассив. Элемент  массива ­ переменная с индексом. Переменная с индексом позволяет представить большое  количество величин с одним общим именем. Каждая отдельная величина определяется  индексом/индексами в скобках после наименования переменной. Полная система таких величин называется массивом, а каждая отдельная величина ­  элементом массива. Переменная с индексами может иметь один, два или три индекса, и  тогда она представляет соответственно одно­, дву­ или трехмерный массив. Термин  «одномерный» определяет количество индексов (один), а не количество переменных.  Число индексов определяет размерность массива. Первый элемент одномерного массива ­ это элемент с номером 1, второй ­ элемент с  номером 2, и т. д. до тех пор, пока не будут пронумерованы все элементы. В обычных  математических обозначениях возможна запись X1, Х2, ..., Х9, Х10. При программировании  запись более формализована: Х(1), Х(2), ..., Х(9), Х(10). Двумерный массив представлен в виде матрицы из горизонтальных строк и вертикальных  столбцов. При этом первый из двух индексов определяет номер строки (он изменяется от 1 до М, где М ­ полное количество строк), второй номер столбца (изменяющийся от 1 до N,  где N ­ полное число столбцов) в обычной математической записи может быть представлен  как А1,1  А1,2  А1,3  А2,1  А2,2  А2,3 При формализации задания он будет записан как А(1,1), А(1,2), А(1,3), А(2,1), А(2,2),  А(2,3). Индексы отделяются запятыми. Таким образом, массив характеризуется именем, размерностью и размером. Имя массива  образуется по общему правилу образования имен, т. е. представляет собой идентификатор. Однако оно не должно совпадать с именем ни одной простой переменной, используемой в  этом же алгоритме. Примеры циклических алгоритмов Алгоритмы вычисления суммы являются стандартными циклическими алгоритмами. Перед первым выполнением цикла необходимо задать начальное значение суммы (количество,  разность, произведение и т. д.). Вычислить  сумму Другими словами, необходимо вычислить сумму произведения вводимых чисел. Словесное описание циклического алгоритма имеет следующий вид: 1. Начальное значение суммы равно 0 2. Начинаем с первого элемента : i=1 3. Ввести Xi ,Yi 4. Вычисляем сумму: Сумма = Сумма + Xi x Yi 5. Продолжаем суммировать ­ переходим к следующему элементу: i = i+1 6. Если i <= n, то перейти к п. 3, иначе перейти к п. 7 7. Вывести значение «Сумма» Рис. 1.9. Графическое изображение циклического алгоритма 8. Конец Перед первым выполнением цикла необходимо задать начальное значение «Сумма» = 0 и  затем nраз вычислять «Сумма» при различных значениях Xi и Yi, где i принимает  последовательно значения 1,. . ., n и используется цикл с постусловием. В схеме алгоритма  заменим слово «сумма» буквой S. Вычислить факториал М! = 1х2хЗх (М ­ 1)х М Факториал вычисляется как произведение от 1 до М, аналогично предыдущему  вычислению суммы. Начальное значение переменной «ФАКТ»=1, если это значение задать  равным нулю, то и результат будет нулевым. Рис. 1.10. Схема алгоритма для вычисления факториала Словесное описание алгоритма для данной задачи имеет следующий вид: 1. Ввести М 2. Факт = 1 3. k=1 4. Факт = Факт * k 5. k = k+ 1 6. Если k<= M, то перейти к п. 4, иначе перейти к п. 7 7. Вывести «Факт» 8. Конец В схеме алгоритма используется цикл с параметром для k (символ «подготовка»), где k  изменяется от 1 до М. Вычислить сумму положительных чисел в таблице Таb1(5,5) Возможны случаи, когда циклические вычисления надо производить в зависимости от  дополнительных условий. В этом случае алгоритм кроме циклической структуры содержит также разветвляющую структуру и дополнительные блоки сравнения. По условию задачи имеем таблицу, в которой 5 строк и 5 столбцов. Всего 5 х 5 = 25  элементов. Положительным является число, величина которого больше 0. Необходимо  выполнить сравнение «Если Tab1(i, j) > 0» для 25 вводимых чисел. Иначе ­ сравнение для 5  строк по 5 столбцов. Имеем два вложенных цикла. Первым будет цикл по строкам ­ по i,  вложенным по отношению к нему является цикл по столбцам ­ по j Словесное описание алгоритма вычисления суммы положительных элементов в таблице  имеет следующий вид. 1. СумП = 0 2. Номер строки i = 1 3. Номер столбца j = 1 4. Ввести элемент таблицы Tab1(i, j) 5. Если Tab1(i, j) > 0, то СумП = СумП + Tab1(i, j) 6. Следующий элемент столбца j = j + 1 7. Все элементы столбца просмотрены?     Если j < =5, то перейти к п. 4 8. Следующий элемент строки i = i + 1 9. Все элементы строки просмотрены?     Если I < =5, то перейти к п. 3 10. Вывести «СумП» 11. Конец Рис. 1.11. Схема алгоритма вычисления суммы положительных элементов в таблице Изменение величины «СумП» происходит в зависимости от условия положительности  введенного Tab1(i, j) на каждом шаге данного алгоритма. Величина суммы изменяется, если условие истинно, на величину элемента таблицы Tab1(i, j). Алгоритмы поиска Алгоритмы информационного поиска и сортировки образуют отдельные классы  алгоритмов, которые имеют ярко выраженную специфику: внешне тривиальные задачи  «найти» или «упорядочить» допускают разнообразные решения. Подобные алгоритмы  следует разрабатывать с использованием пошаговой детализации. Задача поиска заключается в отыскании в заданной последовательности эле¬мента или  нескольких элементов с заданными свойствами. Поиск может быть следующим. A. Поиск минимального элемента последовательности.    B. Поиск номера минимального элемента последовательности.    C. Поиск максимального элемента и его номера в заданной  последовательности.    D. Поиск номера элемента последовательности с заданным значением. оиск минимального и максимального элемента заданной последовательности Для поиска минимального элемента (задача А) необходимо определить эталон  ­переменную, которой заранее присваивается значение какого­то элемента. Поиск  проводится путем сравнения всех элементов. Предположим, что эталонная переменная  определена. Сравнить с ней первый элемент. Если он меньше эталона, изменить эталон,  присвоив ему значение первого элемента, и перейти к сравнению со вторым элементом.  Таким образом можно сравнить все элементы последовательности. При пошаговой  детализации алгоритма А следует отметить, что все действия выполняются одинаково для  всех элементов последовательности:    a. Сравнить эталон с очередным элементом последовательности.    b. Перейти к следующему элементу. c. Если не все элементы последовательности просмотрены, то повторить с п. а. В результате анализа определяем следующее: Необходимо задать номер того элемента, с которого начинается сравнение, и определить ­  назначить эталон. Текущий номер элемента не должен превышать общую длину последовательности. Переход к следующему элементу заключается в увеличении на единицу индекса. Обозначим исследуемую последовательность x1, x2,. .., xN. Для задачи В (определение номера минимального элемента) алгоритм имеет аналогичную  структуру. Процесс отыскания максимума и его номера (алгоритм С) можно совместить в  одном цикле. Переменной Nom (номер) присвоить начальное значение 1. Полученный выше алгоритм  можно преобразовать в алгоритм определения номера максимального элемента. Для этого  в алгоритме (рис. 1.12) максимальный элемент заданной последовательности будет иметь  имя max. Рис. 1.12. Схема поиска номера максимального элемента Если необходимо найти максимальный элемент и его номер в последовательности с  совпадающими значениями, то необходимо уточнить, какой первый или последний из  одинаковых элементов считать искомым. Структура алгоритма остается неизменной.  Отличие только в сравнении эталонной переменной с текущим элементом массива. Если необходимо найти первый по порядку следования минимальный элемент и его номер,  то предыдущий алгоритм остается практически без изменения. Поиск номера элемента последовательности с заданным значением Рассмотрим задачу D. Пусть задана последовательность {Xi} = Х1, Х2, ..., XN, где i  изменяется от 1 до N. По условию в последовательности {Xi} все элементы имеют разные  значения. Необходимо определить номер элемента, значение которого равно значению  некоторой заданной переменной Р. Причем в заданной последовательности может не  оказаться элемента со значением Р. Первая ситуация ­ упорядоченная последовательность. Основной алгоритм поиска имеет следующий вид:    a. Сравнить очередной элемент с переменной Р.    b. Перейти к следующему элементу.    c. Если не все элементы просмотрены, то повторить с п. а. Алгоритм должен однозначно реагировать на ситуацию, если искомого значения в  последовательности нет. Введем переменную k с начальным значением, равным 0.  Результат k ­ номер найденного элемента. Если элемент со значением Р не найден, то результат k остается нулевым (рис. 1.13). Если  последовательность упорядочена, т. е. значения элементов последовательности возрастают  или убывают с увеличением порядковых номеров (индексов) элементов, то к ней можно  применить другой алгоритм поиска. В процессе поиска можно сдвинуть друг к другу  границы промежутка, в котором после каждого сравнения сдвигается либо верхняя, либо  нижняя граница. Алгоритм, в котором последовательно уменьшается промежуток  исследуемых данных в два раза, называется алгоритмом дихотомии ­ деление отрезка  пополам. Пусть значение наименьшего элемента исходной последовательности равно А, а значение  наибольшего элемента ­ В. Если разделить рассматриваемый интервал [А, В] пополам, то  получится некоторое значение С. Сравнить С с заданным значением Р. Повторять эти  действия до тех пор, пока А и В не совпадут. Проверить условие Х[А] = Р. По результатам  проверки должен быть сформирован результат. Рис. 1.13. Схема алгоритма поиска заданного элемента Словесный алгоритм поиска имеет следующий вид:    a. Вычислить С.    b. Сравнить Х[С] с переменной Р.    c. Определить А и В.    d. Если А и В не совпадают, то повторить с п. а. e. Проверить совпадение выделенного значения с поисковой Р. Рис. 1.14. Схема алгоритма дихотомического поиска Необходимо задать начальные значения А и В. Схема алгоритма дихотомического поиска в упорядоченном массиве представлена на рис. 1.14. Сортировка Сортировка стала важной частью вычислительной математики, так как она отнимает  значительную часть времени работы компьютера (25%). Сортировка относится к  алгоритмам обработки таблиц (массивов) любого типа. Смысл любой сортировки заключается в перестановке элементов таблицы в определенном  заданном порядке. Отсортировать числовую таблицу ­ это значит переставить элементы в  ней так, чтобы они расположились в порядке убывания (возрастания) значений с  возрастанием нового номера элемента: Номер элемента Исходный числовой массив Упорядочение по возрастанию Упорядочение по убыванию 1 7 1 49 2 12 3 12 3 1 7 7 4 49 12 3 5 3 49 1 Сортировка символьной (или текстовой) информации заключается в упорядочении  значений (текстовых строк) по алфавиту: Номер элемента Исходный символьный массив Упорядочение по алфавиту 1 мул вол 2 кот кот 3 як лев 4 лев мул 5 вол як Метод сортировки является устойчивым, если относительный порядок элементов с  равными значениями не меняется после упорядочения. Сортировку можно рассматривать и как самостоятельную задачу (например, для получения упорядоченного по алфавиту  списка сотрудников какого­либо учреждения), и как вспомогательную ­ для облегчения  последующего поиска элементов в упорядоченной таблице. Анализ известных алгоритмов  сортировки очень полезен, так как в них используется практически все универсальные приемы конструирования алгоритмов. В пособии представлены алгоритмы упорядочения  последовательности A1,A , ..., AN, по возрастанию. Переход к упорядочению по убыванию  аналогичен. Простой выбор Основной смысл сортировки простым выбором заключается в следующем. Найти в таблице элемент с наименьшим значением и поменять его местами с первым элементом. Далее те же действия выполнить с остальными N ­ 1 элементами таблицы, затем с N­ 2 элементами и т.  д., пока не останется один элемент ­ последний, наибольший. Допустим, что два первых элемента являются упорядоченными. Теперь необходимо  отыскать минимальный элемент среди остальных. Если несколько элементов  последовательности оказываются равными, то следует найти первый среди минимальных  элементов. Таким образом будет достигнута устойчивость сортировки. Найденный элемент из двух первых и третий по списку элемент следует поменять местами. Для получения результата необходимо N ­ 1 раз найти минимальное значение в массиве,  длина которого будет уменьшаться с каждым шагом на 1 (рис. 1.15). Рис 1.15.   Схема алгоритма сортировки простым выбором   Словесный алгоритм сортировки простым выбором будет следующим: 1. Начинаем сортировку с первого элемента i =1. 2. Найти минимальный элемент и его номер в массиве А 1 , А 2 ,...,A N . 3. Поменять местами A i и минимальный элемент A k . 4. Перейти к следующему элементу i = i + 1. 5. Если рассмотрены не все N ­ 1 элементы, то повторить с п. 2. Используем разработанный выше алгоритм поиска минимума и присвоим минимальной  величине имя x.  Для перестановки переменных в сортируемом массиве используется операция  «переприсвоения» вида A k = Ai ; Ai = х, где k ­ номер минимального элемента (одного из  двух) на данном этапе. Простой обмен Любой метод сортировки так или иначе связан с обменом ­ с перестановкой двух  элементов в памяти. Для обменной сортировки это основная характеристика процесса.  Идея сортировки простым обменом заключается в многократных попарных сравнениях  рядом стоящих элементов таблицы и перестановке этих элементов в заданном порядке. Например, задана таблица Номер элемента    1   2   3   4   5  Значение элемента   7   49   1   12   3  Необходимо организовать ее просмотр от конца к началу или от начала к концу. Сравнить  значения элементов 4 и 5 и поменять их местами, так как они расположены не по  возрастанию. Далее сравнить элементы 3 и 4. Они остаются на своих местах, и т. д. В результате минимальный элемент переместится в таблице на первое место и новая  таблица после первого «прохода» примет вид: Номер элемента    1   2   3   4   5  Значение элемента   1   7   49   3   12  Все дальнейшие просмотры уже не включают просмотр первого элемента. Каждый  последующий просмотр будет «устанавливать» очередной минимальный элемент в левую  часть таблицы. Упорядочение таблицы происходит за N ­ 1 просмотр. Если представить, что элементы таблицы ­ это пузырьки в сосуде с водой, каждый с весом,  равным ему по значению, то каждый проход с обменом снизу вверх по таблице приводит к  «всплыванию пузырька» на соответствующий его весу уровень. Благодаря такой аналогии  сортировка простым обменом получила названиепузырьковой сортировки . Составим алгоритм для решения этой задачи. Основная часть алгоритма ­ цикл, который  должен выполниться за N ­ 1 раз. Выбор границ 1 и (N ­ 1) или 2 и N влияет только на задание индексов сравниваемых элементов. Пусть это будет ­2 и N. Словесный алгоритм будет следующим: a. i=2 b. Сравнить попарно элементы А n , А n­1 , ..., А i , A i­1 . c. i = i + 1 d. Если i ≤ N, то повторить с п. b. Для попарного сравнения элементов можно использовать для схемы алгоритмов  графический цикл с параметром (символ «Подготовка»), зависящий от i, так как при  каждом новом проходе по таблице длина ее будет уменьшаться. Рис 1.16.   Схема алгоритма простого обмена или пузырьковой сортировки   Рассмотрим «попарное сравнение» более подробно. a. j=N b. Сравнить А j и А j­1 и при необходимости поменять местами c. j=j­1 d. Если j > i, то повторить с п. b. Сравнение в п. b можно записать, используя операцию переприсвоения: Если A j > A j­1 , To X = A j­1 ; A j­1 = A j ;A j = x. На рис. 1.16 представлена схема алгоритма пузырьковой сортировки, для которой  использован цикл с постусловием. Простые вставки Пусть в заданной последовательности A 1 , А 2 , ..., A n первые i­1 элементы уже  отсортированы. Необходимо найти в этой части последовательности место для i­гo  элемента и сравнить его по порядку со всеми элементами, стоящими левее, до тех пор,  пока не окажется, что некоторый А k € A i . Затем для части последовательности A k+1 ,  A k+2 ,..., A i+1 выполнить сдвиг на один элемент вправо, чтобы освободить место элемента  A k+2 для элемента A i . В результате исходная последовательность будет отсортирована. Если провести сравнение элемента со всеми другими элементами, стоящими слева, то  может оказаться, что не найдется такого A k , что A k € A i . Это возможно при условии, если  А i меньше тех элементов, которые находятся слева. Необходимо закончить просмотр,  выполнить сдвиг элементов A 1 , A 2 , ..., А i и элемент А i поставить на первое место. Как и в предыдущих случаях, основой алгоритма вставок является цикл, который должен  определить, для какого элемента последовательности следует найти место в левой  упорядоченной части.  Обобщенный алгоритм вставок следующий : 1. i = 2; 2. Найти место A k для A i упорядоченной последовательности; 3. Выполнить сдвиг элементов A k+1 , A k+2 , ..., A i+1 вправо; 4. Поставить элемент A i на нужное место (A k = X, если X определено); 5. i =i+1; 6. Если i ≤ N, то повторить с п. 2. При выполнении п. 2 получается номер k ­ индекс элемента, за которым справа должен  следовать Аi. Чтобы найти место для Аi, необходимо сравнить его последовательно со всеми левыми соседями до элемента  А k € A i . Если такого элемента нет, то следует остановиться на первом элементе. Алгоритм будет иметь следующий вид:  1. j = i­ 1 2. Сравнить элементы А i < А j ; 3. j=j­ 1; 4. Если j > 0, то повторить с п. 2; В данном случае необходимо следующее:   запомнить значение А i , иначе при сдвиге оно может быть потеряно; зафиксировать номер i­1 ­ с этого элемента начинается сравнение;  поставить на первое место A i , если оно меньше A 1 , А 2 , ..., A i­1 . Результат выполненных действий: x = Ai; j = i ­ 1; k = 1. После сравнения Аi и Aj необходимо сделать вывод о целесообразности продолжения  сравнения, иначе цикл закончен ­ необходимый элемент найден. Закончить цикл можно, используя j = 0. Если Аi € Aj, то k = j + 1; j = 0; иначе j = j ­ 1. При детализации выполняется сдвиг последовательности вправо. В этом случае  последовательность необходимо просматривать из конца в начало и последовательно  сдвигать элементы: 1. j = 1; 2. Ai = Аi­1; 3. j = j ­ 1; 4. Если j > k, то повторить с п. 2. Окончательный алгоритм сортировки простыми вставками изображен на рис. 1.17. Рис 1.17.   Схема алгоритма сортировки простыми вставками   Заключение Невозможно назвать алгоритм сортировки универсально наилучшим в любой ситуации.  Эффективность алгоритма будет зависеть от множества факторов:   сколько элементов участвует в сортировке;   все ли элементы могут быть помещены в доступную область или в доступный  интервал;   в какой степени элементы уже отсортированы;   какой диапазон и распределение значений сортируемых элементов;   записаны ли элементы в файл или массив;   предполагается ли, что элементы будут периодически исключаться или допол  няться;  можно ли сравнивать элементы параллельно. С отсортированными данными легче работать. Когда элементы отсортированы, как в  телефонном справочнике, их проще найти, обновить, исключить, легче найти, какие  элементы пропущены. В данном пособии представлены алгоритмы для работы с одномерными массивами. Любую  двумерную таблицу можно легко представить в виде одномерной таблицы путем пересчета  индексов. Например, двумерную таблицу 5x5 можно представить в виде одномерной  таблицы, в которой 25 элементов. Либо можно воспользоваться предложенными  алгоритмами с добавлением дополнительных вложенных циклов для столбцов.