Базовые структуры алгоритмов – Виды алгоритмов


Базовые структуры алгоритмов

Изучив этот пункт, мы:

Познакомимся с основными видами алгоритмов; узнаем, какие структуры алгоритмов являются базовыми;

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

Узнаем о структурных алгоритмы и их преимущества.

==== 55.1.Виды алгоритмов ================================================ ===

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

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

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

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

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

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

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

Читать  Динамические массивы Pascal

Третий вид алгоритмов составляют предусматривающие возможность повторного выполнения определенной последовательности действий.

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

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

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

 

Базовая структура линейного алгоритма называется Следованием, ее блок-схему представлен на рис.55.1.

 

Рис. 55.1. Базовая структура следования

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

Например, для нахождения силы тяги F, которую развивает двигатель автомобиля, измеряют время T, за который автомобиль массы M, двигаясь из состояния покоя, проходит заданное расстояние S.Алгоритм нахождения силы тяги состоит из двух действий: первая — вычисление ускорения автомобиля (a = 2s / t 2)

Вторая — вычисление силы тяги (F = am).Обе эти действия выполняются, какими бы ни были исходные данные задачи.

Читать  Лекция Паскаль 1 – Создание проекта, создание форм, обработка событий

 

==== 55.3.Базовая структура ветвления =======================================

Базовая структура алгоритма с разветвлением тоже называется Разветвлением.

Различают полную и краткую форму разветвления (рис. 55.2).

А) б)

Рис. 55.2. Базовая алгоритмическая структура ветвления: а) полная форма; б) краткая форма

Полная форма разветвления означает, что осуществляется выбор между двумя действиями. Если проверка условия дает результат «да», то выбирается действие 1; в противном случае, то есть если проверка условия дает результат «нет», — выбирается действие 2 (рис.55.2). Полную форму ветвления можно прочитать в такой образом:

Если проверка условия дает результат «да», то выполнить действие 1, иначе выполнить действие 2.

Например, для предоставления X значение большего из двух заданных чисел A и B (a s B) нужно проверить, больше A по B; если да, то предоставить X значение A, а если нет (то есть иначе), то предоставить X значение B. Итак, имеем полную форму ветвления:

Если a> b, то предоставить X значение A, иначе предоставить X значение B. Короткую форму разветвления (рис. 55.2б) можно прочитать следующим образом: если проверка условия дает результат «да», то выполнить действие.

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

Если число отрицательное, то изменить его знак на противоположный.

Отметим, что и полная, и короткая формы ветвления являются Замкнутыми: каждая из них имеет один вход и один выход.

==== 55.4.Базовая структура «повторение» =======================================

Базовая структура алгоритма с повторением называется Повторением, или чаще Циклом. Различают две основные разновидности циклов: циклы, где условие проверяется До выполнения действия — Циклы с предусловием (рис.55.3), и циклы, где проверка условия осуществляется После выполнения действия — Циклы с постусловием (рис.55.3б).

Читать  Технология построения алгоритмов

В цикле с предусловием (рис.  55.3) условие цикла формулируется таким образом, чтобы повторное выполнение действия делалось, пока проверка условия дает результат «да». Поэтому такие циклы называют еще циклами «пока».Цикл «пока» можно прочитать следующим образом:

Пока проверка условия дает результат

«Да», выполнять действие.

Если при очередной проверке условия будет получено результат «нет», повторное выполнение действия будет прекращено и произойдет выход из цикла.

Например, для подсчета остатка от

Деления целого числа M на целое число N с помощью вычитания можно воспользоваться циклом:

Пока m ≥ n, уменьшить M на N.

Рис. 55.3. Базовая алгоритмическая структура повторения: а) цикл с предусловием;

Б) цикл с постусловием

В цикле с постусловием (рис. 55.3, б) условие цикла формулируется противоположным образом: если очередная проверка условия дает результат «да», происходит выход из цикла. Поэтому такие циклы называют также циклами «до».Цикл «до» можно сокращенно прочитать так:

Повторять действие До получения результата «да» при проверке условия.

Например, подсчет остатка от деления целого числа M на целое число N (mN) можно реализовать с помощью цикла:

Повторять уменьшить M на N в M <n.

Обратите внимание на то, что является общим для обоих типов цикла:

·  обе базовые структуры цикла является замкнутыми;

·  количество повторений цикла определяется его условием;

·  выход из цикла происходит только через проверку условия цикла.

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

«Нет». Поэтому рассмотрены типы циклов не является взаимозаменяемыми: цикл с постусловием можно заменить циклом с предусловием, а наоборот — нет.

==== 55.5.Структурные методы ==============================================

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

Читать  Лекция Паскаль 10 – Массивы, Объявления одномерного массива, Индексация элементов

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

Например, в базовой структуре следования (рис. 55.1) функциональный блок Действие 1 может быть замещен разветвлением, а блок Действие 2 — повторением. Такое замещение можно продолжать дальше и дальше.

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

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

ВЫВОДЫ

Контрольные вопросы и упражнения

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

А) линейным;

Б) методом с разветвлением; в) алгоритмом с повторением.

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

А) линейным;

Б) методом с разветвлением; в) алгоритмом с повторением.

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

А) линейным;

Б) методом с разветвлением; в) алгоритмом с повторением.

4. Как можно прочитать базовую структуру разветвления? вставьте пропущенные слова.

«… проверка условия дает результат… … выполнить действие 1, … выполнить действие 2».

А) пока; б) если;

В) повторять; г) то;

Д) иначе; е) в РФ;

Е) «Да»; ж) «Нет».

5. Как можно прочитать базовую структуру цикла с предусловием? вставьте пропущенные слова.

«… проверка условия дает результат…, выполнять действие».

А) пока; б) если;

В) повторять; г) то;

Читать  Строки Паскаль – Тип STRING для обработки текстов

Д) иначе; е) в РФ;

Е) «Да»; ж) «Нет».

6. Как можно прочитать базовую структуру цикла с постусловием? вставьте пропущенные слова.

«… действие… получения результата… при проверке условия».

А) пока; б) если;

В) повторять; г) то;

Д) иначе; е) в РФ;

Е) «Да»; ж) «Нет».

7. Спортсмены на соревнованиях пробегают дистанцию ​​от пункта А до пункта Б и обратно. Составьте блок-схему алгоритма определения средней скорости спортсмена на дистанции, если известно, что от пункта А до пункта Б он двигался со скоростью V 1, а от пункта Б в пункт А со скоростью V 2.

8. Составьте блок-схему структурного алгоритма подготовки к путешествию: а) велосипеда;

Б) автомобиля;

В) надувной лодки; г) байдарки.

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

10. В данный момент электронные часы показывает g часов h минут. Составьте блок-схему структурного алгоритма определения, покажет часы через одну минуту.

11. В супермаркете цену молочного десерта за два дня до исчерпания срока его годности уменьшается на 25% от его первоначальной цены. После исчерпания срока годности десерт течение 2 дней продают за четверть первоначальной цены, после чего снимают с продажи. Составьте структурный алгоритм определения цены десерта на N-й день после его изготовления, если известны начальная цена десерта C и срок годности T (дней), где T> 2.

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

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

А) положить на ячейку с номером N;

Б) отдать изобретателю за игру.

[Всего голосов: 3    Средний: 5/5]