Основы алгоритмизации
Линейный алгоритм – это алгоритм, в котором действия выполняются однократно и строго последовательно.
Самый простой пример реализации линейного алгоритма – путь из университета домой.
Словесный способ записи данного алгоритма:
1. выйти из университета на остановку;
5. выйти на требуемой остановке;
Очевидно, что данный пример относится к линейному алгоритму, т.к. все действия следуют одно за другим, без условий и повторений.
Разветвляющийся алгоритм – это алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.
Самый простой пример реализации разветвляющегося алгоритма – если на улице идет дождь, то необходимо взять зонт, иначе не брать зонт с собой.
Приведенный выше пример псевдокода по нахождению частного двух чисел также относится к разветвляющемуся алгоритму.
Циклический алгоритм – это алгоритм, команды которого повторяются некое количество раз подряд.
Самый простой пример реализации циклического алгоритма – при чтении книги будут повторяться одни и те же действия: прочитать страницу, перелистнуть и т.д.
Блок-схема – это графическая реализация алгоритма.
Блок-схема представляет собой удобный и наглядный способ записи алгоритма.
Блок-схема состоит из функциональных блоков разной формы, связанных между собой стрелками. В каждом блоке описывается одно или несколько действий. Основные виды блоков разберем позже
Любая команда алгоритма записывается в блок-схеме в виде графического элемента – блока, и дополняется словесным описанием. Блоки в блок-схемах соединяются линиями потока информации. Направление потока информации указывается стрелкой. В случае потока информации сверху вниз и слева направо стрелку ставить не обязательно. Блоки в блок-схеме имеют только один вход и один выход (за исключением логического блока – блока с условием).
Блок начала блок-схемы имеет один выход и не имеет входов, блок конца блок-схемы имеет один вход и не имеет выходов. Блок условия – единственный блок, имеющий два выхода, т.к. соответствует разветвляющемуся алгоритму. На одном выходе указывается "да", на другом – "нет". Все остальные блоки имеют один вход и один выход. Блок выполнения действия может содержать присвоение значения переменной (например "х=5") или вычисление (например "у=4").
Математические выражения и логические высказывания должны быть описаны математическим языком, т.к. блок-схема не должна иметь привязки к какому-то определенному языку программирования. Одна и таже блок-схема может быть реализована в программах на разных языках программирования.
Все три вида алгоритмов реализуются в блок-схеме названными выше типами блоков. К примеру, в линейном алгоритме могут присутствовать все блоки, кроме блока условия. В разветвляющемся и циклическом алгоритмах могут быть использованы все названные виды блоков, но обязательным является блок условия. Внутри блока условия записывается условие, про которое можно однозначно ответить, истинно оно или ложно Если условие истинно, то выполняются действия, соответствующие стрелке "да", иначе стрелке "нет".
Занятие 2. Графическая реализация линейного алгоритма
Приведем простейшие примеры, соответствующие линейному алгоритму.
Пример 1. Вася хочет позвонить Пете по городскому телефону. Необходимо составить блок-схему, описывающую порядок действий Васи.
Решение. Чтобы позвонить по городскому телефону, нужно знать номер Пети. Значит, сначала надо найти номер телефона Пети, набрать его и поговорить с Петей. На этом цель Васи (поговорить с Петей по телефону) будет достигнута. Результат блок схемы представлен на рис. 2.1.
Рис 1. Блок-схема для примера 1
Пример 2. Ученику требуется купить учебник. Составить блок-схему, описывающую порядок действий ученика.
Решение. Сначала ученику нужно взять деньги, потом прийти в книжный магазин и заплатить за учебник. На этом цель (покупка учебника) будет достигнута. Результат блок схемы представлен на рис.2.
Рис. 2. Блок-схема для примера 2
Пример 3. Даны числа a=2, b=7. Вычислить сумму S и разность R чисел a и b.
Решение. Сначала следует задать значения для чисел a и b, согласно условиям задачи. После этого их уже можно будет использовать в расчетах для получения суммы и разности по формулам: S=a+b, R=a-b. Полученные значения суммы и разности нужно будет показать на экране, и мы используем блок вывода данных. Если не выводить данные на экран, то пользователь нашего алгоритма не узнает, какие получились значения суммы и разности. Результат блок схемы представлен на рис. 3.
Рис. 2.3. Блок-схема для примера 3: а) в каждом блоке по одному действию, б) действия объединены по смыслу операции
В блок-схеме на рис. 3а каждое действие расположено в отдельном блоке. В блок-схеме рис. 3б объединены между собой схожие по смыслу операции. В дальнейшем мы будем объединять некоторые действия в один блок. Это очень удобно и визуально упрощает чтение блок-схемы.
----------------— конец загятия 11.04 ----------------------------
Занятие 3. Графическая реализация разветвляющегося алгоритма
В разветвляющемся алгоритме обязательным блоком является блок условия, который представлен на рис. 4.
Рис. 4. Использование блока условия в общем виде
Внутри блока условия записывается условие. Если данное условие верно, то выполняются блоки, идущие по стрелке "да", т.е. "Набор действий 1". Если условие оказывается неверным, т.е. ложным, то выполняются блоки, идущие по стрелке "нет", а именно "Набор действий 2". Разветвление заканчивается, когда обе стрелки ("да" и "нет") соединяются. На рис. 2.5 представлен еще один вариант использования блока условия. Бывают задачи, в которых, исходя из условия, необходимо либо выполнить действие, либо пропустить его. Если условие верно выполняется, то следуют блоки, соответствующие стрелке "да", т.е. "Набор действий 1". Если же условие оказывается ложным, то следует перейти по стрелке "нет". Т.к. стрелке "нет" не соответствует ни одного блока с действием, то ни одного действия не будет выполнено. Т.е. получается, что мы пропустили и не выполнили "Набор действий 1".
Рис. 5. Вариант использования блока условия
В разветвляющемся алгоритме возможна запись сразу нескольких условий, которые могут объединяться союзом "ИЛИ" или пересекаться союзом "И". Рассмотрим случай двух условий: "условие 1" и "условие 2".
Если необходимо, чтобы оба условия были верными одновременно, то следует использовать логическое пересечение "И":
Если достаточно, чтобы только одно условие выполнялось – либо первое, либо второе, то следует использовать логическое объединение "ИЛИ":
Приведем простейшие примеры, соответствующие разветвляющемуся алгоритму.
Пример 4. Джон звонит Полу по городскому телефону, но трубку может взять не только Пол. Составить блок-схему, описывающую действия Джона в этом случае.
Решение. В отличие от примера 1, здесь присутствует условие – Пол ли взял трубку телефона. На данное условие можно однозначно ответить: "да", Пол, или "нет", кто-то другой. Если трубку взял Пол, то Джону нужно с ним поговорить, и цель будет достигнута. Если трубку взял кто-то другой, то необходимо позвать Пола к телефону, поговорить с ним, и цель также будет достигнута. Третьего варианта, например, "не туда попали" или "его нет дома" мы не рассматриваем. Результат блок-схемы представлен на рис. 2.6.
Рис. 6. Блок-схема для примера 4
Пример 5. Ученику требуется купить учебник. В магазине в наличие оказался нужный учебник в жесткой и мягкой обложке. Составить блок-схему, описывающую действия ученика.
Решение. В данном примере присутствует условие: "Нужна жесткая обложка".
Ученик может согласиться с этим высказыванием, тогда он выполнит действие, соответствующее стрелке "да" и купит учебник в жесткой обложке.
Если ученик не соглашается с данным условием, то будет выполняться действие, соответствующее стрелке "нет", и в этом случае ученик купит учебник в мягкой обложке.
И в том, и в другом случае, цель будет достигнута и задача будет выполнена, т.к. ученик купит учебник.
Результат блок схемы представлен на рис. 7.
Рис. 7. Блок-схема для примера 5
Пример 6. Даны числа a=2, b=7. Вычислить сумму S и разность R чисел a и b. Сравнить полученные значения S и R и указать большее из них.
Решение. Как и в примере 3, сначала необходимо задать значения a и b. Затем рассчитать сумму и разность по формулам: S=a+b, R=a-b, и вывести полученные числа на экран (блок вывода данных). Когда значения будут получены, следует сравнить их между собой. Условие запишется в виде: S>R. Если полученная сумма S будет больше разности R, то мы пойдем по стрелке "да" и выведем фразу "maxS". Если же условие окажется ложным (т.е. S<R), то пойдем по стрелке "нет" и выведем фразу "maxR". Результат блок схемы представлен на рис. 2.8.
Рис. 8. Блок-схема для примера 6
Занятие 4. Графическая реализация циклического алгоритма
В рассмотрении циклического алгоритма следует выделить несколько понятий.
Тело цикла – это набор инструкций, предназначенный для многократного выполнения.
Итерация – это единичное выполнение тела цикла.
Переменная цикла – это величина, изменяющаяся на каждой итерации цикла.
Каждый цикл должен содержать следующие необходимые элементы:
первоначальное задание переменной цикла,
Циклы бывают двух видов – с предусловием и с постусловием. В цикле с предусловием сначала проверяется условие входа в цикл, а затем выполняется тело цикла, если условие верно. Цикл с предусловием представлен на рис. 9. Цикл с предусловием также может быть задан с помощью счетчика. Это удобно в тех случаях, когда точно известно количество итераций. В общем виде блок-схема, реализующая цикл с предусловием, представлена ниже. Сначала задается начальное значение переменной цикла, затем условие входа в цикл, тело цикла и изменение переменной цикла. Выход из цикла осуществляется в момент проверки условия входа в цикл, когда оно не выполняется, т.е. условие ложно. Цикл с предусловием может ни разу не выполниться, если при первой проверке условия входа в цикл оно оказывается ложным.
Рис. 9. Циклический алгоритм с предусловием в общем виде
В цикле с постусловием сначала выполняется тело цикла, а потом проверяется условие. Циклический алгоритм с постусловием представлен на рис. 10.
Рис. 2.10. Циклический алгоритм с постусловием в общем виде
Если условие верно, то итерация повторяется, если же неверно, то осуществляется выход из цикла. В отличие от цикла с предусловием, любой цикл с постусловием всегда выполнится хоть раз.
Примечание. Как видно из представленных блок-схем для циклов с предусловием и постусловием, условие записывается внутри блока условия (формы ромба), как и в разветвляющемся алгоритме. Принципиальная разница между разветвляющимся и циклическим алгоритмами при графической реализации состоит в том, что в циклическом алгоритме в обязательном порядке присутствует стрелка, идущая наверх. Именно эта стрелка обеспечивает многократный повтор тела цикла.
Приведем простейшие примеры, соответствующие циклическому алгоритму.
Пример 7. Вася звонит Пете, но у Пети может быть занята линия. Составить блок-схему действий Васи в этом случае.
Решение. Когда телефонная линия занята, то необходимо снова и снова набирать номер, пока Петя не закончит предыдущий разговор, и телефонная линия не окажется вновь свободной. Блок-схема представлена на рис. 11.
Рис. 11. Блок-схема для примера 7
Здесь тело цикла состоит из одного действия "Набрать номер Пети", т.к. именно это действие следует повторять, пока линия будет занята. Под итерацией цикла понимается очередная попытка дозвониться до Пети. Как таковой переменной цикла здесь нет, т.к. ситуация взята из жизни. Выход из цикла происходит в тот момент, когда условие "У Пети занято" стало неверным, т.е. телефонная линия свободна – действительно, нет необходимости больше набирать номер Пети. В данном примере применен цикл с постусловием, т.к. сначала необходимо набрать номер Пети, ведь иначе мы не можем ответить на вопрос – занята ли линия у Пети.
Пример 8. Ученику требуется купить учебник. Составить блок-схему, описывающую действия ученика в случае, если учебника нет в ряде магазинов.
Решение. Действия ученика в данном примере очевидны: когда он приходит в первый и любой последующий магазины, то возможны два варианта – учебник имеется в наличии или учебника нет в продаже. Если учебника нет в продаже, то ученику следует пойти в другой книжный магазин и спросить данный учебник, и т.д. пока учебник не будет куплен, т.к. перед учеником стоит конечная цель – купить учебник. Мы будем использовать цикл с предусловием, т.к. сначала требуется найти магазин, имеющий в наличии данный учебник. Цикл будет выполняться, пока условие "В данном магазине нет учебника" будет верным, а выход из цикла осуществится, когда условие станет ложным, т.е. когда ученик придет в магазин, в котором есть данный учебник. Действительно, в этом случае ученик купит нужный ему учебник и не будет больше искать книжные магазины. Результат блок-схемы представлен на рис.12.
Любой алгоритм может быть реализован с помощью блок-схемы. Для каждого вида алгоритма предусмотрена своя конструкция из определенных блоков. Проверка блок-схемы и получение результата достигается при выполнении блок-схемы.
3. Какие блоки используются при реализации линейного, разветвляющегося, циклического алгоритмов?
4. Можно ли составить разные варианты блок-схем для одной и той же задачи?
5. Какие виды циклического алгоритма бывают?
6. Какие пункты должны присутствовать в любом цикле?
7. Что такое выполнение блок-схемы?
8. Для чего следует выполнять блок-схему?
1. Составьте блок-схемы для задачи по походу в магазин за яблоками. Используйте линейный, разветвляющийся и циклический алгоритмы.
2. Составьте блок-схему для нахождения корней квадратного уравнения через дискриминант. Используйте разветвляющийся алгоритм. Получите ответ, выполнив блок-схему.
3. Составьте блок-схемы для вывода на экран целых чисел от 1 до 10. Используйте цикл с предусловием, с постусловием. Выполните блок-схемы.