Типовые структуры алгоритмов.

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

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

Пример: Вычислить высоты треугольника со сторонами А, В, С по формулам:

; ;

, где: - полупериметр треугольника.

Рис. 2.1. Блок-схема алгоритма линейной структуры.

Разветвленная структура используется в том случае, когда в зависимости от значений промежуточного результата выбирается та или иная последовательность действий. То есть в зависимости от выполнения некоторого логического условия вычисление должно идти по одной или другой ветви программы. На блок-схеме условие записывается внутри ромба из которого выходят две стрелки, при выполнении условия путь к следующей команде указывает линия с надписью «Да»; если условие не выполняется, по путь к следующей команде указывает стрелка с надписью «Нет».

Пример: Вычислить значения функции , где: и - заданные параметры.

На первый взгляд можно составить линейную структуру. Но при равенстве знаменателя нулю функция не определена. Необходимо предусмотреть этот случай и в качестве результата в этом случае выдать информацию о том, что знаменатель функции равен нулю. Таким образом, в блок - схеме должно быть две ветви: 1 ветвь - знаменатель не равен нулю и можно вычислить и напечатать значение функции; 2 ветвь - знаменатель равен нулю и нужно выдать информацию о невозможности вычислить значение функции.

Рис. 2.2. Блок-схема алгоритма разветвленной структуры.

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

При организации циклов необходимо:

1) задать начальное значение параметра цикла - переменной, которая будет изменяться при каждом повторении цикла;

2) изменить значение параметра цикла при каждом повторении цикла на шаг изменения;

3) проверить условие окончания этих повторений по значению этого параметра и перейти в начало цикла, если повторения ещё не закончены.

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

В цикле с предуcловием (while) – проверка условия завершения осуществляется до выполнения тела цикла. В цикле с постусловием (repeat) - до проверки условия завершения выполняется тело цикла.

Пример: Вычислить при изменении от 0 до 3 с шагом 0,1.

С изменением параметра математическим способом и использованием блока сравнения блок–схема представлена на рис. 2.3 б) и в). Если в блок–схеме используется блок организации цикла, то эта блок – схема представлена на рис. 2.3 а).

а) б) в)

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

Типовые алгоритмы.

Алгоритмы последовательного поиска, двоичного поиска, сортировки относятся к циклическим (итеративным) структурам.

Алгоритмы сортировки.

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

Сортировки методом простого выбора. Находят максимальный элемент в массиве из N элементов и меняют его местами с последним элементом (сортировка по возрастанию). Далее рассматривают массив без последнего элемента N-1. Общее количество сравнений пропорционально N².

Сортировка методом поплавка. Рассматривается весь массив и максимальный элемент постепенно перемещается на последнее место. Затем рассматривают массив из N-1 элементов. Общее количество сравнений пропорционально N².

Сортировка методом вставок. На i-м шаге считается, что первая часть массива, содержащая i-1 элемент, уже упорядочена. Далее берется i-й элемент, и для него подбирается j-е место в отсортированной части массива, такое, что упорядоченность не нарушается. i-й элемент помещается на это место, таким образом, что отсортированная часть массива увеличивается на один элемент. Общее количество сравнений пропорционально N².

Алгоритмы поиска.

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

Алгоритм двоичного поиска. Если массив упорядочен, то тогда можно использовать алгоритм бинарного (двоичного) поиска. По результату сравнения искомого значения со средним элементом массива из рассмотрения исключают первую или вторую половину списка, в зависимости от того больше или меньше «средний» (находящийся в середине списка) элемент искомого элемента. Для поиска в оставшейся части списка его тоже разбивают на две части и процедура повторяется. Таким образом, метод состоит в последовательном разделении рассматриваемого списка на сегменты до тех пор, пока не будет найден искомый элемент или поле поиска не сузится до пустого сегмента. Общее количество сравнений пропорционально log₂N.

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

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

Рекурсивные системы представляют собой циклические процессы и зависят от правильного управления ими. Их работа зависит от проверки условия завершения (для двоичного поиска – пустой список или найденное значение) и правильного их построения, которое обеспечивает выполнение этого условия завершения. [1, 10]

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: