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

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

Естественно, что при таком подходе к алгоритмам изучение основных принципов их конструирования должно начинаться с изучения этих базовых элементов. Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур следование, цикл, ветвление. Характерной особенностью базовых структур является наличие в них одного входа и одного выхода. 1. Базовая структура следование. Образуется последовательностью действий, следующих одно за другим, представлена на рис1. Применение этой структуры рассмотрим на примере 1. Пример 1. Найти корень линейного уравнения вида ах b 0. Для решения примера 1 составим блок-схему алгоритма рис. 2 Следуя последовательности блоков в алгоритме можно составить программу на языке Лого, которая может быть представлена, так как на рис. 3. Для запуска программы в командном поле введем имя программы - УРАВНЕНИЕ и нажмем клавишу Enter. В появившемся диалоговом окне введем значение для коэффициента А 2, во втором - В 5. В третьем диалоговом окне появится значение рассчитанного параметра Х -2,5. Пример 2. Тело движется прямолинейно с ускорением а м с2 и начальной скоростью м с. Требуется определить, какой путь пройдет тело за Т секунд.

Гейн А.Г Житомирский В.Г стр.15 . Описание и использование функций В число Лого входят стандартные функции SQRT - квадратный корень, SIN - синус, COS - косинус градусного аргумента, POWER - квадрат.

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

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

Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока. В языке Лого существует только один вид цикла, применяемый для повторения определенных действий. Базовую структуру цикл и команду REPEAT можно применять не только для перемещения Черепашки и рисования, но также и решения вычислительных задач, подразумевающих получения результата. Рассмотрим применение структуры Цикл на примере 3 рис.8 . Пример 3. Получить цифру 5 с помощью операции сложения и цифры 1. Можно заметить, что команды пусть a a 1, сообщи a, повторяются 5 раз, следовательно применив структуру Цикл получим блок-схему применимо к рассматриваемому примеру 3 рис.8 . При вводе А 1, производится операция сложения А 1 и повторяется 5 раз, что в результате получаем А 5. Принцип действия прочитав, в наборе команд REPEAT Черепашка ищет указание числа повторений - указатель начала цикла. Запомнив его место, Черепашка будет выполнять команды, пока не встретит указатель конца цикла После этого Черепашка возвращается к началу цикла и проверяет, выполнила ли она цикл заданное число раз. Если нет, то она продолжает выполнять цикл, в противном случае если она уже выполнила задуманное число раз Черепашка начинает выполнять команды расположенные в квадратных скобках.

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

Сначала команды присваивания ПУСТЬ MAKE заводится новая переменная и ей присваивается начальное значение.

Затем начинаются, повторения - многократно выполняется один и тот же набор действий. В этом наборе обязательно есть действие изменения значения переменной. В такой программе команда присваивания ПУСТЬ МАКЕ встречается дважды. Первый раз при начальной установке переменной а 0 , второй раз - в цикле, при изменении значения переменной а а 1 . Первая команда присваивания выполняется один раз, вторая - многократно.

При изменении переменной в цикле используется ее же предыдущее значение. Поэтому в команде ПУСТЬ а а 1 MAKE а а 1 переменная упоминается дважды присвоить переменной с именем a то значение, которое сейчас имеет переменная - a, увеличенное на единицу. Сначала упоминается имя, а затем - значение. Пример 4. Вычислить уравнение y a b четыре раза и получить результат. Команда пусть y a b, сообщи y, повторяются 4 раза, следовательно применив структуру Цикл получим блок-схему применимо к рассматриваемому примеру 4 рис.9 . При вводе А 12, а B 24 производится операция сложения А B и повторяется 4 раза, что в результате получаем y 36. Пример 5. Вычислить 5 раз значения X i3, Y X 2 и вывести значения на экран.

Сначала команды присваивания ПУСТЬ заводится новая переменная I и ей присваивается начальное значение. Затем начинаются, повторения - многократно выполняется один и тот же набор действий. В этом наборе обязательно есть действие изменения значения переменной. Команда пусть y x 2, сообщи y, пусть x I I I ,сообщи x, повторяются 5 раз, следовательно применив структуру Цикл получим блок-схему применимо к рассматриваемому примеру 5 рис.10 . При выводе значений y и x производится операция возведения x в степень, а y x 2 , что в результате получаем y 32, x 64. Пустой цикл Это такой цикл, когда тело цикла отсутствует, т.е. после слова REPEAT в квадратных скобках ничего не стоит.

Например REPEAT 1000 Если ввести эту команду в ЭВМ, то Черепашка какое-то время не будет реагировать на команды, а будет 1000 раз выполнять НИЧЕГО. Иногда это полезно, потому что обеспечивает паузу между выполнением команд.

Это можно рассмотреть на примере 6. Пример 6. Вывести две фразы СЕГОДНЯ ПРЕКРАСНАЯ ПОГОДА с паузой, затем фразу ВСЕМ ПРИВЕТ . 3. Базовая структура ветвление Обеспечивает в зависимости от результата проверки условия да или нет выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.

Структура ветвление существует в четырех основных вариантах если-то если-то-иначе 1. если-то Обеспечивает ветвление не полная форма. Если условие истинно, то выполняются действия, указанные в списке. If Если 2. если-то-иначе Обеспечивает ветвление полная форма. Если условие истинно, то выполняется первое действие, если условие ложно - выполняется второе действие. Ifelse Если иначе Пример 7. Если х 0, то вычислить значение y sin x. На примере 7 наглядно показано ветвление ЕСЛИ не полная форма. Если условие истинно, то выполняются действия, указанные в программе. Вычисления выполняются командной строкой пусть y sin x, затем если условие выполнено, выводится y. Пример 8. Если a b, то вычислить значение a 2 a, если условие не выполняется, то вычислить b 2 b В примере 8 рассматривается полная форма ветвления.

Если условие истинно, то выполняется первое действие, если условие ложно - выполняется второе действие.

Процедуры с параметрами 1. Процедура без параметра Рассмотрим применение процедуры без параметра на уже решенном примере 3. Процедура вызывается только с помощью имени, стоящего после ЭТО ТО . Для этого используется процедура без параметра. 2. Процедура с параметром Теперь в список команд Черепашки добавим переменную величину х, которая позволит изменять размер начального значения х. Такой параметр в заголовке процедуры называется формальный параметр - та же самая переменная х. При вызове же процедуры нужно будет указать соответствующее значение - так называемый фактический параметр.

Например, уравнение 100 . Следовательно, начальное значение переменной х 100. Рассмотрим чуть подробнее, что происходит при исполнении процедуры с параметром. Переменную можно представить в виде ящика, на котором наклеена табличка с именем. В этот ящик может поместиться одно значение. Компьютер в любое время может посмотреть, что там находится, а может и поменять хранящееся значение.

Допустим, если дать команду уравнение 100. В заголовке процедуры после ее имени стоит х. Поэтому число 100 компьютер положит в ящик с такой табличкой. Теперь начинается выполнение самой процедуры. Черепашка начинает выполнять цикл. Встретившись с командой пусть х х 1 , она смотрит, какое значение лежит в ящике, и подставляет его в эту команду. Само значение переменной при этом не меняется. Процедура может иметь не один параметр, а несколько.

Рассмотрим пример 9. Пример 9. Вычислить В этом случае при запуске процедуры количество фактических параметров и их порядок должны соответствовать формальным. Если их будет меньше, Лого выдаст сообщение Если больше - Рекурсия В Лого все процедуры равноправны. Допускается, что одна процедура может вызывать вторую, вторая - третью и так далее. Кроме того, в Лого допускается, что процедура может вызывать процедуру со своим собственным именем. Такой вызов процедурой самой себя называется рекурсией. а Процедура, обращающаяся сама к себе Пример 10. Составить процедуру А, бесконечно печатающую слово ПРИВЕТ Процедура А печатает в текстовом окне слово ПРИВЕТ и вызывает процедуру А, которая печатает в текстовом окне слово ПРИВЕТ и вызывает процедуру А и т.д. Слово ПРИВЕТ будет печататься до тех пор, пока пользователь не прервет программу.

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

Пример 11. Используя уравнение х 3 рассчитать и нарисовать траекторию движения Черепашки б Управляемая рекурсия Для остановки программы в нужный момент можно применить условие и команду STOP СТОП . Пример 12. Ввести коэффициенты А, В, С. Если А 200, вычислить Х А.В-В.С. В противном случае остановить программу. Если при очередном вызове параметр А оказался больше 200, то программа остановится. В противном случае последует запрос и ввод коэффициентов А и В, расчет значения Х и новый вызов с увеличенным параметром. в Косвенная рекурсия Если процедура вызывает сама себя не непосредственно, а через другую процедуру, то это называется косвенной рекурсией.

Пример 13. Вычислить значения у sin a и х cos a, установив между ними взаимосвязь и не превышать значения 1. Эти две процедуры вычисления sin a b cos a работают так первая вызывает вторую, а вторая - первую. В результате получается один из примеров косвенной рекурсии.