Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Понятие алгоритма).pdf

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

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

Ниже показан пример записи текста программы на языке BASIC [Ист. 5]

Рисунок 5 Источник 5

Структура следования

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

Рисунок 6 Источник 2

«Серия»-тут представляет составной оператор, в языке Pascal-это «begin», «end».

2.5 Структура ветвления

Ветвление – это структура, обеспечивающая выбор между двумя альтернативами. Выполняется проверка, а затем выбирается один из путей. Эта структура называется также «ЕСЛИ – ТО – ИНАЧЕ», или «развилка». Каждый из путей (ТО или ИНАЧЕ) ведет к общей точке слияния, так что выполнение программы продолжается независимо от того, какой путь был выбран. Может оказаться, что для одного из результатов проверки ничего предпринимать не надо. В этом случае можно применять только один обрабатывающий блок (структура «ЕСЛИ – ТО»). Цикл «Пока» (цикл с предусловием) начинается с проверки логического выражения. Если оно истинно, то выполняется тело цикла, затем все повторяется снова, пока логическое выражение сохраняет значение «истина». Как только оно становится ложным, управление передается по программе дальше В цикле «До» (цикл с постусловием) проверка условия выполняется после операторов тела цикла. Цикл повторяется, если условие ложно. Как только оно становится истинным, управление передается по программе дальше . Пожалуй, самым важным достижением структурного подхода к разработке алгоритмов является нисходящее проектирование программ. Этот метод основан на идее уровней абстракции, которые становятся уровнями модулей в разрабатываемой программе. Это позволяет программисту сначала сконцентрировать внимание на определении того, что надо сделать в программе, а лишь затем решать, как это надо делать. При нисходящем проектировании исходная, подлежащая решению задача разбивается на ряд подзадач, подчиненных по своему содержанию главной задаче. Такое разбиение называется детализацией или декомпозицией. На следующем этапе эти задачи, в свою очередь, разбиваются на более мелкие подчиненные подзадачи и так далее, до уровня относительно небольших подзадач, которые требуют для решения небольших модулей. Модуль – это последовательность логически связанных операций, оформленных как отдельная часть программы. Модули связаны между собой только по входным и выходным данным. Использование модулей имеет следующие преимущества: 1) возможность создания программы несколькими программистами; 2) простота проектирования и последующих модификаций программы; 3) упрощение отладки программы – поиска и устранения в ней ошибок; 4) возможность использования готовых библиотек наиболее употребительных модулей. [Ист 1, стр 32]

---

Структура цикла

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

Многократное повторение последовательности действий называется циклом, а многократно повторяющиеся действия – телом цикла.

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

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

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

Рисунок 7 Источник 6

а), б) – циклическая структура “Для каждого”

в) – циклическая структура “Пока”

г) – циклическая структура “До”

I – счетчик числа повторов, C – приращение счетчика, A – начальное значение счетчика, B – конечное значение счетчика, P – тело цикла.

 1. Цикл “Для каждого” можно записать в следующем виде:

Для каждого I от A до B с шагом С:

P

Конец цикла по I

I – счетчик числа повторов, C – приращение счетчика, A – начальное значение счетчика, B – конечное значение счетчика, P – тело цикла.

2. Цикл “Пока” можно записать так:

Пока Q повторять:

P

Конец цикла

Q – условие. ЭВМ будет выполнять P до тех пор, пока условие Q истинно.

3. Цикл “До” записывается следующим образом:

Повторять:

P

До выполнения Q

Конец цикла

Тело цикла P выполняется до тех пор, пока условие Q ложно.

Одним из самых распространенных в практике вычислений алгоритмом циклической структуры является алгоритм вычислений некоторой функции y=f(x) для значений x, которые меняются от начального значения x₀ до конечного x_k с шагом h.

Исходными данными алгоритма являются значения: x₀, x_k, h. Необходимо вычисления по формуле y=f(x) повторять (x_k-x₀)/h+1 раз, т. е. при построении алгоритма организовать цикл. Параметром цикла выберем переменную x.

---

Схема алгоритма решения этой задачи на рис. 7. В схеме блок 3 присваивает начальное значение параметру цикла x, блок 6 осуществляет изменение на h параметра x при каждом выполнении цикла, блок 7 управляет циклом, для чего проверяется условие повторения цикла x<=x_k. При выполнении этого условия (да) управление передается на начало цикла, а при невыполнении – осуществляется выход из цикла, т.е. переход к следующему по порядку блоку

Рисунок 8 Источник 6

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

Цикл с предусловием (цикл-пока)

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

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

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

Рисунок 9 Источник 7

Пример. Найти факториал числа N.

Пусть F - переменная, накапливающая факториал, R - число, меняющееся от 1 до N. Тогда F=1*2*3*...*N или F=R*(R+1)*(R+2)*...*N

Рисунок 10 Источник 7

Цикл с полст-условием (до)

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

Рисунок 11 Источник 7

Пример. Задача, в которой требуется вводить с клавиатуры числа и подсчитывать их сумму. Сумму необходимо подсчитывать до первого введенного отрицательного числа.
Пусть S - сумма, A - вводимое число [Ист 7]

---

Рисунок 12 Источник 7

Понятие линейного алгоритма

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

Графическое представление алгоритмической конструкции в словестном виде «следование» приведено на рисунке:

Рисунок 13Источник 8

Линейный алгоритм приготовления отвара шиповника.

Рисунок 14Источник 8

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

Пример в виде программной записи:

У исполнителя Робот есть четыре команды перемещения (вверх, вниз, влево и вправо), при выполнении каждой из них Робот перемещается на одну клетку в соответствующем направлении. По команде закрасить Робот закрашивает клетку, в которой он находится. Запишем линейный алгоритм, исполняя который Робот нарисует на клетчатом поле следующий узор и вернётся в исходное положение:

Рисунок 15Источник 8

алг узор

нач

   закрасить

   вправо

   вправо

   закрасить

   вниз

   влево

   закрасить

   вверх

   влево

кон

Где «алг» значит суть алгоритма, «нач»-начало, далее действия и «кон»-конец

Пример в виде табличной записи:

Дан фрагмент линейного алгоритма:

x:=2

y:=x⋅x

y:=y⋅y

x:=y⋅x

s:=x+y

Рисунок 16 Источник 8

С помощью операции div вычисляется целое частное, с помощью операции mod — остаток. [Ист. 8]

Рисунок 17Источник 8

Понятие разветляющегося алгоритма

Алгоритмы, в основе которых лежит структура «ветвления», называют разветвляющимися.
Блок-схемы ветвления представлены на рисунках.

Полная форма ветвления:

Рисунок 18 Источник 8

На программном языке команда ветвления записывается так:

Рисунок 19Источник 8

Ещё один пример:

Рисунок 20Источник 8

---

Неполная форма ветвления:

Рисунок 21Источник 8

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

Рисунок 22Источник 8

Ещё один пример:

Рисунок 23Источник 8

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

A<B−А меньше ВA<=B−А меньше или равно ВA=B− А равно ВA>B−А больше ВA>=B−А больше или равно ВA<>B−А не равно В

Здесь буквы A и B можно заменять на любые переменные, числа и арифметические выражения. Приведённые операции сравнения допускаются и для символьных переменных.

Понятие цикличного алгоритма

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

Алгоритмы, содержащие конструкцию повторения, называют циклическими или циклами.

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

В зависимости от способа организации повторений различают три типа циклов:

1. цикл с заданным условием продолжения работы;
2. цикл с заданным условием окончания работы;
3. цикл с заданным числом повторений.

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

Рисунок 24Источник 8

На программном языке эта конструкция записывается так:

Рисунок 25 Источник 8

Выполняется цикл-ПОКА следующим образом:

• проверяется условие (вычисляется значение логического выражения);
• если условие удовлетворяется (Да), то выполняется тело цикла и снова осуществляется переход к проверке условия;
• если же условие не удовлетворяется, то выполнение цикла заканчивается.

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

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

Рисунок 26Источник 8

Пример: правее Робота расположен коридор неизвестной длины. Необходимо, чтобы Робот закрасил все клетки этого  коридора.

---