Статья рассказывает про алгоритмы с разветвлённой структурой. Читатель узнает, чем их решение отличается от решения линейных алгоритмов, как выглядит программный способ записи таких алгоритмов, а также какова будет блок-схема.
В предыдущей статье шла речь об алгоритмах, их особенностях и свойствах. Особое внимание было уделено линейной структуре как самому простому способу реализации. Сегодня поговорим о более сложных алгоритмах, обладающих разветвлённой структурой. Но прежде чем продолжать, следует кое-что вспомнить.
Алгоритм – это ясный перечень действий, который направлен на решение какой-либо задачи. Одно из свойств алгоритма — дискретность. Дискретность связана с наличием в алгоритмической последовательности ряда операций (этапов, действий), выполняемых пошагово, то есть дискретно. Алгоритм обладает свойством дискретности, так как он представляет собой процесс решения задачи в виде последовательного выполнения простых шагов. И каждое действие исполняется лишь после окончания исполнения предыдущего. Также предполагается наличие определённых исходных данных и результата выполнения.
Блок-схема — графический способ описания алгоритмов. Графическое представление обеспечивает наглядность и упрощает запись, делая последовательность более понятной. При использовании схемы каждому действию соответствует определённая геометрическая фигура (эти фигуры называют блоками). Вот наиболее часто употребляемые:
Ещё раз о линейности
Линейная последовательность — самая простая из возможных структур. При наличии линейности команды выполняются в чёткой последовательности и в порядке их записи, то есть друг за другом. Вот линейная алгоритмическая последовательность посадки дерева:
1) выкапывание ямки в земле;
2) размещение в ямке саженца;
3) закапывание ямки;
4) поливание места посадки водой.
Такой линейный алгоритм имеет следующую блок-схему:
А вот и общая схема линейного алгоритма:
Ветвление в алгоритмических последовательностях
На практике очень редко встречается, чтобы последовательность всех требуемых действий была известна заранее. Если на минуту покинуть мир алгоритмизации и программирования, можно спроецировать ветвление на многие жизненные ситуации. Если на улице дождь, человек берёт зонт, если очень жарко, будет выбрана одежда полегче и т. д. Всё зависит от условия выбора. Как тут не вспомнить рыцаря на распутье из русских народных сказок?
«Направо пойдёшь — жену найдёшь, налево пойдешь — богатым будешь, прямо пойдёшь — смерть найдёшь».
Подобная ситуация заставляет принимать решения с учётом определённого условия. Если нужна жена, то витязь идёт направо, если богатство, то налево, если жизнь не мила, то прямо. Условия, которые влияют на решение, располагаются между словами «если» и «то».
От значения условий зависит дальнейшее поведение. Когда условие выполняется, оно принимает значение «истина», когда нет — «ложь». Иногда анализ ситуации и выбор не вызывают особых затруднений, а иногда принять решение очень трудно. А всё потому, что принимающий решение пытается продумать каждый из вариантов и предугадать последствия выбора. Нельзя не вспомнить гроссмейстера, который анализирует позицию на ходы вперёд, прежде чем передвинуть фигуру на шахматной доске.
Компьютерные программы и игры тоже построены на выборе действий. А блок-схема при наличии ветвления приобретает иной вид:
Логика разветвляющих алгоритмов
Логику можно описать следующим образом:
ЕСЛИ <условие истинно> ТО <действие 1> ИНАЧЕ <действие 2>Ветвление — метод и форма организации действий, когда в зависимости от выполнения определённого условия совершается та либо иная последовательность шагов.
В результате совсем несложно составить алгоритм покупки мороженого с учётом наличия необходимой суммы денег. Описать эту алгоритмическую последовательность с помощью схемы и блоков тоже не составит труда:
Для закрепления можно решить задачу.
Есть 3 монеты одинакового достоинства. Одна из монет фальшивая (известно, что она имеет меньший вес). Найдите фальшивую монету на чашечных весах без гирь с помощью только одного взвешивания.
Решение легко описывается посредством схематических блоков:
Следующий пример легко экстраполируется в жизнь. Речь идёт об алгоритме для перехода дороги при наличии светофора. Он имеет следующий вид:
1. Подходим к светофору.
2. Смотрим, какой горит свет.
3. Если зелёный, переходим дорогу.
4. Если красный, ждём, пока загорится зелёный, а потом переходим дорогу.Соответствующая блок-схема:
Программный способ записи
Чтобы алгоритм было понятен компьютеру, машине и любой другой цифровой системе, следует оформить его в таком виде, который эта система способна воспринимать. То есть надо написать программу, используя для этого команды из СКИ. СКИ — это список команд исполнителя — перечень команд, ему понятных. А любой исполнитель способен исполнить лишь те команды, которые включены в его СКИ, а если говорить человеческим языком — входят в набор его компетенций.
Для примера можно реализовать алгоритм на языке программирования Pascal. Исходя из вышесказанного, следует использовать команды, входящие в терминологию Pascal.
Простейший пример описания алгоритма с разветвляющейся структурой — условный оператор IF. Полная конструкция этого условного оператора имеет следующий вид:
if<логическое выражение>then<оператор 1>else<оператор 2>Здесь if — это «если», then — это «то», else — «иначе».
Условный оператор работает просто:
— вычисляется значение логического выражения, которое расположено после служебного слова IF;
— если результат — истина, выполняется оператор 1, который размещён после THEN, причём действие после ELSE пропускается;
— если результат — ложь, пропускается уже действие после THEN, а действие после ELSE выполняется с помощью оператора 2.Теперь можно вспомнить пресловутого витязя на распутье и написать простую программу, реализующую этот алгоритм с помощью соответствующих условных операторов.
program Algoritm_vetvlenia; Var x :string; Begin WriteLn ('Витязь, куда путь держишь?'); ReadLn (x); If x='Направо' then writeLn ('Направо пойдёшь — жену найдёшь'); If x='Налево' then writeLn ('Налево пойдешь — богатым будешь'); If x='Прямо' then writeLn ('Прямо пойдёшь — смерть найдёшь'); ReadLn; End.Попробовать этот алгоритм в работе можно на любом онлайн-компиляторе, поддерживающим Pascal. Но не стоит на этом останавливаться — лучше всего написать собственную программу, что позволит получить максимальную пользу от урока.
Источники:
• http://informatic.hop.ru/p33.htm;
• https://interneturok.ru/lesson/informatika/6-klass/algoritm-i-ispolniteli/prakticheskaya-rabota-2-sostavlenie-algoritmov;
• https://www.turbopro.ru/index.php/algoritmizatsiya-i-ispolniteli/5210-algoritmy-ponyatie-i-vidy-algoritma-blok-skhemy;
• https://www.yaklass.ru/p/informatika/6-klass/algoritmy-14002/tipy-algoritmov-13610/re-61ead1ff-bc77-453f-ac99-e46da267f3f3.
В предыдущих уроках мы рассмотрели наиболее простой, линейный тип алгоритмов. Напомню, что всего существует три типа: линейные, разветвляющиеся и циклические (алгоритмы с повторениями). В этом уроке я расскажу вам о втором типе алгоритмов — об алгоритмах с ветвлениями.
Ветвления
Ветвление – это команда алгоритма, в которой делается выбор, выполнять или не выполнять какую-нибудь группу команд в зависимости от условий.
Ветвление используется в двух случаях:
- Когда требуется пропустить определенную команду или группу команд.
- Когда нужно записать выбор тех или иных действий в зависимости от условия.
В блок-схеме условие ветвления изображается в ромбе, из которого обязательно выходят ДВЕ стрелки – первая (стрелка «Да») указывает на команды, которые будут выполняться в случае, если условие соблюдено; вторая (стрелка «Нет») – на команды, которые будут выполнены, если условие не соблюдено. Даже если команда, на которую указывает одна из стрелок (Чаще всего «Нет») отсутствует, стрелка все равно имеет место быть.
В словесной формулировке запись ветвления выглядит так:
ЕСЛИ <условие выбора > ТО <команды, выполняемые при соблюдении условия> ИНАЧЕ <команды, выполняемые при несоблюдении условия>
Реализация ветвления в Паскаль.
Как же реализовать ветвление в Паскаль? Проще, чем вы думаете:
if <условие выбора > then <команды, выполняемые при соблюдении условия> else <команды, выполняемые при несоблюдении условия>
Запомните! Перед else никогда не ставят точку с запятой!
Давайте поговорим об условии выбора. Понятно, что этологическое выражение. Если оно является правдой, то выполняется главная ветвь, если ложь, то боковая ветвь.
Рассмотрим несколько задач из сборника М.Э.Абрамяна «1000 задач по программированию».
If1. Дано целое число. Если оно является положительным, то прибавить к нему 1; в противном случае не изменять его. Вывести полученное число.
В данной программе даже не надо реализовывать боковую ветвь.
program if1; var a: integer; begin read(a); if a > 0 then Inc(a); write(a); end.
If2. Дано целое число. Если оно является положительным, то прибавить к нему 1; в противном случае вычесть из него 2. Вывести полученное число.
program if2; var a: integer; begin read(a); if a > 0 then Inc(a) else a -= 2; write(a); end.
If3. Дано целое число. Если оно является положительным, то прибавить к нему 1; если отрицательным, то вычесть из него 2; если нулевым, то заменить его на 10. Вывести полученное число.
Для того чтобы решить эту задачу мы должны использовать вложенный if.
program if3;
var
a: integer;
begin
read(a);
if a >= 0 then
if a = 0 then a := 10 else Inc(a) {перед else нет точки с запятой.}
else a -= 2;
write(a);
end.
If5. Даны три целых числа. Найти количество положительных и количество отрицательных чисел в исходном наборе.
program if5;
var
a, b, c, plus, minus: integer;
begin
write('Введите три целых числа: ');
read(a, b, c);
plus := 0;
minus := 0;
if a > 0 then Inc(plus) else Inc(minus);
if b > 0 then Inc(plus) else Inc(minus);
if c > 0 then Inc(plus) else Inc(minus);
writeln('Количество положительных чисел - ', plus);
writeln('Количество отрицательных чисел - ', minus);
end.
If30. Дано целое число, лежащее в диапазоне 1–999. Вывести его строку-описание вида «четное двузначное число», «нечетное трехзначное число» и т. д.
program if30;
var
a: integer;
begin
write('Введите число: ');
read(a);
if Odd(a) then write('Нечетное ') else write('Четное ');
if a >= 100 then write('трехзначное число') else
if a < 10 then write('однозначное число') else write('двухзначное число');
end.
Вот и все! Не забывайте кликать по кнопочкам и добавлять наш сайт в закладки!
В одной из прошлых статей мы поговорили о алгоритмах и в ней же я обещал в скором времени рассказать про блок схемы. Что же, время пришло.
Давайте сначала поймем, что такое блок схемы.
Блок-схема — распространенный тип схем (графических моделей), описывающих алгоритмы или процессы, в которых отдельные шаги изображаются в виде блоков различной формы, соединенных между собой линиями, указывающими направление последовательности
Ага, то есть блок схема, это способ представления нашего алгоритма в картинках. Но зачем? Дело в том, что человеку, как существу, имеющему зрение, проще и удобнее, зачастую, воспринимать информацию, если она продублирована в виде текста или имеет какие-то графические обозначения. Если не вдаваться в подробности, то это называется зрительным восприятием. Согласитесь, если вы видите объект беседы перед собой, вам проще его воспринимать, обсуждать и т.д.
Существует несколько основных блоков. В интернете вы можете найти примерно такое описание для части из них. Цвет фона значения не имеет, и здесь он синий для большей наглядности (наверное)
Процесс– под процессом здесь понимается какое-то действие. Арифметическая или логическая операция. Что то, что приведет вас к финальному результату выполнив один пункт вашего алгоритма. Допустим “a+b” будет помещаться именно в такой блок.
Решение – немного странное название, но думаю, что вы уже догадались, что это условие. С ним мы уже сталкивались в прошлой статье по алгоритмам. Когда нам приходилось РЕШАТЬ, что делать дальше, на основе какого-то результата.
Модификация – забудьте про это слово. Это просто цикл. О циклах мы тоже говорили. Но конкретно этот цикл немного специфичный. Это обозначение цикла For, который является счетным циклом и немного отличатся от остальных. Иные циклы могут быть представлены без специального оператора, это мы с вами попробуем изобразить чуть ниже.
Предопределенный процесс – некая модификация первого блока. Что значит предопределенный? Значит определённый заранее. И тут вообще ступор, но тем не менее он именно так и называется. Говоря простым языком – это ПОДпрограмма, (метод или процедура/функция). Такого мы еще не видели.
Подпрограмма – буквально, программа в программе. То есть это некоторый кусок кода, который выделен в отдельную группу для того, чтобы не писать его каждый раз в разных частях алгоритма/программы. В дальнейшем этот кусок алгоритма/программы может быть запущен, там, где нужно. Сейчас не стоит зацикливаться, подпрограммы мы еще рассмотрим и не раз.
Ввод-вывод, это два блока которые выглядят одинаково, как правило понять, что там происходит можно по тексту внутри блока. Объединены в одну группу, потому что близки по специфике. Получение данных, вывод данных. Мы с вами уже использовали ввод, кстати говоря, когда наш робот читал название колбасы.
Пуск-останов – это те же самые начало и конец, тут думаю пояснения не требуются.
Сейчас вы в ужасе, что я почти для каждого из пунктов подобрал синонимы, и порой более логичные, и понятные. Да, дело в том, что алгоритмизация, это забытый аспект программирования. И из-за этого появляются некоторые сложности. Если что-то не развивать, оно и не разовьется. Может быть многие со мной не согласятся, но я спрошу их, как часто они видят блок схемы в курсах по программированию? Бинго. Ни где их нет.
Зачем же я вам показал отличающиеся название, от тех, что я обычно использую? Что бы вы просто не впадали в ступор если вдруг увидите останов, вместо конца. Более подробно о том, как же все-таки правильно и где какие размеры и сколько градусов углы у каждого ромбика вы можете почитать в ГОСТ 19.701-90 «Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения». Мы в такие подробности вдаваться не будем, по причине того, что мы любители и нам за это не платят, но уметь строить блок-схемы и самое главное читать их, мы должны уметь.
В блок схеме, как правило каждый пункт алгоритма соответствует своему блоку, исключения могут составить блоки, которые реализуют сразу несколько пунктов, допустим цикл For. Или блоки процесса или подпроцесса, которые можно объединять в один, если захочется. Стоит сделать оговорку, что все эти блоки имеют свои размеры, и не стоит растягивать один блок процесса так, чтобы в него все влезло, а вокруг него лепить кучу маленьких.
Между собой блоки соединяются стрелочками, указывающими к какому блоку стоит перейти дальше. В блоках условия/выбора нужно указать какая из стрелочек переведет нас при каком результате. То, что написано внутри блока выбора иногда может быть представлено как вопрос. И если ответ на него да, то идем по стрелочки с надписью да, если нет, то нет. Мы немного расширим наш кругозор вариантов, когда поговорим о “логике”, лжи и истине.
Быть или не быть? Вот в чем блок-схема…. Если быть, то да, следовательно, быть. Если нет, значит нет, ну и вы поняли…
Если у кого то язык чуть не сломался когда читали что в ромбике, то вы заметили, что на самом деле там все должно быть однозначно. И по идеи стоит заменить на вопрос «Быть?» тогда все станет немного логичнее, если вы запнулись на этом месте, значит вы на верном пути в понимании процесса, если нет, то ничего страшного, все еще впереди, тем-более что об условиях я мало рассказал, пока что.
А вот так вот должна выглядеть блок-схема для нашего первого алгоритма. Не густо, но там и алгоритм без ветвлений и чего-либо еще.
Давайте не будем тратить время зря, и сразу перейдем к финальному алгоритму
Тут у нас появляется ввод (в ромбике), даже два. Первый раз, робот читает с бумажки, второй с этикетки.
На самом деле вопрос спорный, ввод это или операция. Будем считать, что это ввод, я программист я так вижу. Вообще многие из стандартов, связанных с обозначением и прочим уже устаревают, и не все из них успевают менять. Вот если допустим в недалеком будущем, полноценный ИИ решит что-то прочесть, это будет ввод или операция? Операция? То есть это не его решение что-то вложить в себя, а просто кусок кода, а то есть ввод пользователя, живого человека, это нечто иное? Слава богу прав у железок пока нет, и статьи за оскорбление чувств кибернетических организмов пока не придумали. 🙂
А видите условие с переходом по НЕТ, не далее, а назад. Это, по сути, тот цикл о котором мы говори. Если колбаса не та, мы возвращаемся к тому, что берем колбасу (старую он бросает на пол, тсссс, потом исправим, может быть), и снова читаем, и снова проверяем. Именно поэтому в прошлый раз я рассказал вам о ветвлениях, это, наверное, более широкое определение всем возможным переходам, будь то по условию или из-за цикла, а может быть и без условия (поговорим о том хорошо это или нет, когда встретимся с кодом на С++ или ASM).
Как вы заметили, блок схемы могут быть довольно большими, но как быть, если вдруг что-то не влезло, а вот так, например как я и сделал. Указываем одинаковые цифры в кругляшках и переходим по нему. Есть другие способы, но нам пока и этого хватит.
А теперь еще раз, зачем же это нужно? Думаю, сейчас вы наглядно видите, что смотреть за тем, куда идет выполнение нашего алгоритма, стало проще. И в некоторых довольно разветвленных алгоритмах, блок схемы помогают лучше понять, что за чем и когда выполняется. Нужно просто вести пальцем по стрелочкам и отвечать на условия, да или нет.
Блок схемы важный, но не основной этап, они скорее пригодятся тем, кто будет разбираться в вашем коде, куда важнее алгоритм, который эта блок схема представляет, поэтому думаю на сегодня хватит.
Не забывайте что каждое подобное знание дает вам преимущество перед вашими конкурентами или коллегами. Сегодня вы научились читать и создавать блок-схемы, в определенных кругах этот навык о многом говорит.
Надеюсь вам было интересно, а пока-что, до скорого.
В этой статье будут рассмотрены примеры блок-схем, которые могут встретиться вам в учебниках по информатике и другой литературе. Блок-схема представляет собой алгоритм, по которому решается какая-либо задача, поставленная перед разработчиком. Сначала нужно ответить на вопрос, что такое алгоритм, как он представляется графически, а самое главное – как его решить, зная определенные параметры. Нужно сразу отметить, что алгоритмы бывают нескольких видов.
Что такое алгоритм?
Это слово ввел в обиход математик Мухаммед аль-Хорезми, который жил в период 763-850 года. Именно он является человеком, который создал правила выполнения арифметических действий (а их всего четыре). А вот ГОСТ от 1974 года, который гласит, что:
Алгоритм – это точное предписание, которое определяет вычислительный процесс. Причем имеется несколько переменных с заданными значениями, которые приводят расчеты к искомому результату.
Алгоритм позволяет четко указать исполнителю выполнять строгую последовательность действий, чтобы решить поставленную задачу и получить результат. Разработка алгоритма – это разбивание одной большой задачи на некую последовательность шагов. Причем разработчик алгоритма обязан знать все особенности и правила его составления.
Особенности алгоритма
Всего можно выделить восемь особенностей алгоритма (независимо от его вида):
- Присутствует функция ввода изначальных данных.
- Есть вывод некоего результата после завершения алгоритма. Нужно помнить, что алгоритм нужен для того, чтобы достичь определенной цели, а именно – получить результат, который имеет прямое отношение к исходным данным.
- У алгоритма должна быть структура дискретного типа. Он должен представляться последовательными шагами. Причем каждый следующий шаг может начаться только после завершения предыдущего.
- Алгоритм должен быть однозначным. Каждый шаг четко определяется и не допускает произвольной трактовки.
- Алгоритм должен быть конечным – необходимо, чтобы он выполнялся за строго определенное количество шагов.
- Алгоритм должен быть корректным – задавать исключительно верное решение поставленной задачи.
- Общность (или массовость) – он должен работать с различными исходными данными.
- Время, которое дается на решение алгоритма, должно быть минимальным. Это определяет эффективность решения поставленной задачи.
А теперь, зная, какие существуют блок-схемы алгоритмов, можно приступить к рассмотрению способов их записи. А их не очень много.
Словесная запись
Такая форма, как правило, применяется при описании порядка действий для человека: «Пойди туда, не знаю куда. Принеси то, не знаю что».
Конечно, это шуточная форма, но суть понятна. В качестве примера можно привести еще, например, привычную запись на стеклах автобусов:«При аварии выдернуть шнур, выдавить стекло».
Здесь четко ставится условие, при котором нужно выполнить два действия в строгой последовательности. Но это самые простые алгоритмы, существуют и более сложные. Иногда используются формулы, спецобозначения, но при обязательном условии – исполнитель должен все понимать.
Допускается изменять порядок действий, если необходимо вернуться, например, к предыдущей операции либо обойти какую-то команду при определенном условии. При этом команды желательно нумеровать и обязательно указывается команда, к которой происходит переход: «Закончив все манипуляции, повторяете пункты с 3 по 5».
Запись в графической форме
В этой записи участвуют элементы блок-схем. Все элементы стандартизированы, у каждой команды имеется определенная графическая запись. А конкретная команда должна записываться внутри каждого из блоков обычным языком или математическими формулами. Все блоки должны соединяться линиями – они показывают, какой именно порядок у выполняемых команд. Собственно, этот тип алгоритма более подходит для использования в программном коде, нежели словесный.
Запись на языках программирования
В том случае, если алгоритм необходим для того, чтобы задачу решала программа, установленная на ПК, то нужно его записывать специальным кодом. Для этого существует множество языков программирования. И алгоритм в этом случае называется программой.
Блок-схемы
Блок-схема – это представление алгоритма в графической форме. Все команды и действия представлены геометрическими фигурами (блоками). Внутри каждой фигуры вписывается вся информация о тех действиях, которые нужно выполнить. Связи изображены в виде обычных линий со стрелками (при необходимости).
Для оформления блок-схем алгоритмов имеется ГОСТ 19.701-90. Он описывает порядок и правила создания их в графической форме, а также основные методы решения. В этой статье приведены основные элементы блок-схем, которые используются при решении задач, например, по информатике. А теперь давайте рассмотрим правила построения.
Основные правила составления блок-схемы
Можно выделить такие особенности, которые должны быть у любой блок-схемы:
- Обязательно должно присутствовать два блока – «Начало» и «Конец». Причем в единичном экземпляре.
- От начального блока до конечного должны быть проведены линии связи.
- Из всех блоков, кроме конечного, должны выходить линии потока.
- Обязательно должна присутствовать нумерация всех блоков: сверху вниз, слева направо. Порядковый номер нужно проставлять в левом верхнем углу, делая разрыв начертания.
- Все блоки должны быть связаны друг с другом линиями. Именно они должны определять последовательность, с которой выполняются действия. Если поток движется снизу вверх или справа налево (другими словами, в обратном порядке), то обязательно рисуются стрелки.
- Линии делятся на выходящие и входящие. При этом нужно отметить, что одна линия является для одного блока выходящей, а для другого входящей.
- От начального блока в схеме линия потока только выходит, так как он является самым первым.
- А вот у конечного блока имеется только вход. Это наглядно показано на примерах блок-схем, которые имеются в статье.
- Чтобы проще было читать блок-схемы, входящие линии изображаются сверху, а исходящие снизу.
- Допускается наличие разрывов в линиях потока. Обязательно они помечаются специальными соединителями.
- Для облегчения блок-схемы разрешается всю информацию прописывать в комментариях.
Графические элементы блок-схем для решения алгоритмов представлены в таблице:
Линейный тип алгоритмов
Это самый простой вид, который состоит из определенной последовательности действий, они не зависят от того, какие данные вписаны изначально. Есть несколько команд, которые выполняются однократно и только после того, как будет сделана предшествующая. Линейная блок-схема выглядит таким образом:
Причем связи могут идти как сверху вниз, так и слева направо. Используется такая блок-схема для записи алгоритмов вычислений по простым формулам, у которых не имеется ограничений на значения переменных, входящих в формулы для расчета. Линейный алгоритм – это составная часть сложных процессов вычисления.
Разветвляющиеся алгоритмы
Блок-схемы, построенные по таким алгоритмам, являются более сложными, нежели линейные. Но суть не меняется. Разветвляющийся алгоритм – это процесс, в котором дальнейшее действие зависит от того, как выполняется условие и какое получается решение. Каждое направление действия – это ветвь.
На схемах изображаются блоки, которые называются «Решение». У него имеется два выхода, а внутри прописывается логическое условие. Именно от того, как оно будет выполнено, зависит дальнейшее движение по схеме алгоритма. Можно разделить разветвляющиеся алгоритмы на три группы:
- «Обход» – при этом одна из веток не имеет операторов. Другими словами, происходит обход нескольких действий другой ветки.
- «Разветвление» – каждая ветка имеет определенный набор выполняемых действий.
- «Множественный выбор» – это разветвление, в котором есть несколько веток и каждая содержит в себе определенный набор выполняемых действий. Причем есть одна особенность – выбор направления напрямую зависит от того, какие заданы значения выражений, входящих в алгоритм.
Это простые алгоритмы, которые решаются очень просто. Теперь давайте перейдем к более сложным.
Циклический алгоритм
Здесь все предельно понятно – циклическая блок-схема представляет алгоритм, в котором многократно повторяются однотипные вычисления. По определению, цикл – это определенная последовательность каких-либо действий, выполняемая многократно (более, чем один раз). И можно выделить несколько типов циклов:
- У которых известно число повторений действий (их еще называют циклами со счетчиком).
- У которых число повторений неизвестно – с постусловием и предусловием.
Независимо от того, какой тип цикла используется для решения алгоритма, у него обязательно должна присутствовать переменная, при помощи которой происходит выход. Именно она определяет количество повторений цикла. Рабочая часть (тело) цикла – это определенная последовательность действий, которая выполняется на каждом шаге. А теперь более детально рассмотрим все типы циклов, которые могут встретиться при составлении алгоритмов и решении задач по информатике.
Циклы со счетчиками
На рисунке изображена простая блок-схема, в которой имеется цикл со счетчиком. Такой тип алгоритмов показывает, что заранее известно количество повторений данного цикла. И это число фиксировано. При этом переменная, считающая число шагов (повторений), так и называется – счетчик. Иногда в учебниках можно встретить иные определения – параметр цикла, управляющая переменная.
Блок-схема очень наглядно иллюстрирует, как работает цикл со счетчиком. Прежде чем приступить к выполнению первого шага, нужно присвоить начальное значение счетчику – это может быть любое число, оно зависит от конкретного алгоритма. В том случае, когда конечное значение меньше величины счетчика, начнет выполняться определенная группа команд, которые составляют тело цикла.
После того, как тело будет выполнено, счетчик меняется на величину шага счетчика, обозначенную буквой h. В том случае, если значение, которое получится, будет меньше конечного, цикл будет продолжаться. И закончится он лишь в тогда, когда конечное значение будет меньше, чем счетчик цикла. Только в этом случае произойдет выполнение того действия, которое следует за циклом.
Обычно в обозначениях блок-схем используется блок, который называется «Подготовка». В нем прописывается счетчик, а затем указываются такие данные: начальное и конечное значения, шаг изменения. На блок-схеме это параметры I н, Ik и h, соответственно. В том случае, когда h=1, величину шага не записывают. В остальных случаях делать это обязательно. Необходимо придерживаться простого правила – линия потока должна входить сверху. А линия потока, которая выходит снизу (или справа, в зависимости от конкретного алгоритма), должна показывать переход к последующему оператору.
Теперь вы полностью изучили описание блок-схемы, изображенной на рисунке. Можно перейти к дальнейшему изучению. Когда используется цикл со счетчиком, требуется соблюдать определенные условия:
- В теле не разрешается изменять (принудительно) значение счетчика.
- Запрещено передавать управление извне оператору тела. Другими словами, войти в цикл можно только из его начала.
Циклы с предусловием
Этот тип циклов применяется в тех случаях, когда количество повторений заранее неизвестно. Цикл с предусловием – это тип алгоритма, в котором непосредственно перед началом выполнения тела осуществляется проверка условия, при котором допускается переход к следующему действию. Обратите внимание на то, как изображаются элементы блок-схемы.
В том случае, когда условие выполняется (утверждение истинно), происходит переход к началу тела цикла. Непосредственно в нем изменяется значение хотя бы одной переменной, влияющей на значение поставленного условия. Если не придерживаться этого правила, получим «зацикливание». В том случае, если после следующей проверки условия выполнения тела цикла оказывается, что оно ложное, то происходит выход.
В блок-схемах алгоритмов допускается осуществлять проверку не истинности, а ложности начального условия. При этом из цикла произойдет выход только в том случае, если значение условия окажется истинным. Оба варианта правильные, их использование зависит от того, какой конкретно удобнее использовать для решения той или иной задачи. Такой тип цикла имеет одну особенность – тело может не выполниться в случае, когда условие ложно или истинно (в зависимости от варианта, который применяется для решения алгоритма).
Ниже приведена блок-схема, которая описывает все эти действия:
Что такое цикл с постусловием?
Если внимательно присмотреться, то этот вид циклов чем-то похож на предыдущий. Самостоятельно построить блок-схему, описывающую этот цикл, мы сейчас и попробуем. Особенность заключается в том, что неизвестно заранее число повторений. А условие задается уже после того, как произошел выход из тела. Отсюда видно, что тело, независимо от решения, будет выполняться как минимум один раз. Для наглядности взгляните на блок-схему, описывающую выполнение условия и операторов:
Ничего сложного в построении алгоритмов с циклами нет, достаточно в них только один раз разобраться. А теперь перейдем к более сложным конструкциям.
Сложные циклы
Сложные – это такие конструкции, внутри которых есть один или больше простых циклов. Иногда их называют вложенными. При этом те конструкции, которые охватывают иные циклы, называют «внешними». А те, которые входят в конструкцию внешних – внутренними. При выполнении каждого шага внешнего цикла происходит полная прокрутка внутреннего, как представлено на рисунке:
Вот и все, вы рассмотрели основные особенности построения блок-схем для решения алгоритмов, знаете принципы и правила. Теперь можно рассмотреть конкретные примеры блок-схем из жизни. Например, в психологии такие конструкции используются для того, чтобы человек решил какой-то вопрос:
Или пример из биологии для решения поставленной задачи:
Решение задач с блок-схемами
А теперь рассмотрим примеры задач с блок-схемами, которые могут попасться в учебниках информатики. Например, задана блок-схема, по которой решается какой-то алгоритм:
При этом пользователь самостоятельно вводит значения переменных. Допустим, х=16, а у=2. Процесс выполнения такой:
- Производится ввод значений х и у.
- Выполняется операция преобразования: х=√16=4.
- Выполняется условие: у=у2=4.
- Производится вычисление: х=(х+1)=(4+1)=5.
- Дальше вычисляется следующая переменная: у=(у+х)=(5+4)=9.
- Выводится решение: у=9.
На этом примере блок-схемы по информатике хорошо видно, как происходит решение алгоритма. Нужно обратить внимание на то, что значения х и у задаются на начальном этапе и они могут быть любыми.
Представление алгоритмов в виде блок-схем
Блок-схемой
будем называть такое графическое
представление алгоритма, когда отдельные
действия (или команды) представляются
в виде геометрических фигур – блоков.
Внутри блоков указывается информация
о действиях, подлежащих выполнению.
Связь между блоками изображают с помощью
линий, называемых линиями
связи,
обозначающих передачу управления.
Существует
Государственный стандарт, определяющий
правила создания блок-схем. Конфигурация
блоков, а также порядок графического
оформления блок-схем регламентированы
ГОСТ 19.701-90 “Схемы алгоритмов и
программ”. В табл. 2.1 приведены
обозначения некоторых элементов, которых
будет вполне достаточно для изображения
алгоритмов при выполнении студенческих
работ.
Правила составления блок-схем:
-
Каждая
блок-схема должна иметь блок «Начало»
и один блок «Конец». -
«Начало»
должно быть соединено с блоком «Конец»
линиями потока по каждой из имеющихся
на блок-схеме ветвей. -
В
блок-схеме не должно быть блоков, кроме
блока «Конец»,
из которых не выходит линия потока,
равно как и блоков, из которых управление
передается «в никуда». -
Блоки
должны быть пронумерованы. Нумерация
блоков осуществляется сверху вниз и
слева направо, номер блока ставится
вверху слева, в разрыве его начертания. -
Блоки
связываются между собой линиями потока,
определяющими последовательность
выполнения блоков. Линии потоков должны
идти параллельно границам листа. Если
линии идут справа
налево
или снизу
вверх,
то стрелки в конце линии обязательны,
в противном случае их можно не ставить. -
По
отношению к блокам линии могут быть
входящими
и выходящими.
Одна и та же линия потока является
выходящей для одного блока и входящей
для другого. -
От
блока «Начало»
в отличие от всех остальных блоков
линия потока только выходит, так как
этот блок – первый в блок-схеме. -
Блок
«Конец»
имеет только вход, так как это последний
блок в блок-схеме. -
Для
простоты чтения желательно, чтобы линия
потока входила в блок «Процесс» сверху,
а выходила снизу. -
Чтобы
не загромождать блок-схему сложными
пересекающимися линиями, линии потока
можно разрывать. При этом в месте разрыва
ставятся соединители,
внутри которых указываются номера
соединяемых блоков. В блок-схеме не
должно быть разрывов, не помеченных
соединителями. -
Чтобы
не загромождать блок, можно информацию
о данных, об обозначениях переменных
и т.п. размещать в комментариях
к блоку.
|
Название |
Обозначение |
Назначение |
|
1 |
2 |
3 |
|
Терминатор |
|
Начало/Конец |
|
Процесс |
|
Обработка |
|
Решение |
|
Ветвление, |
|
Подготовка |
|
Заголовок |
|
Предопределенный |
|
Обращение |
|
Данные |
|
Ввод/Вывод |
|
Соединитель |
|
Маркировка |
|
Комментарий |
|
Используется |
|
Горизонтальные |
|
Линии |
Типы алгоритмов
Тип алгоритма
определяется характером решаемой в
соответствии с его командами задачи.
Различают три типа алгоритмов: линейные,
разветвляющиеся, циклические.
Линейный
алгоритм
состоит из
упорядоченной последовательности
действий, не зависящей от значений
исходных данных, при этом каждая команда
выполняется только один раз строго
после той команды, которая ей предшествует.
Таким,
например, является алгоритм вычисления
по простейшим безальтернативным
формулам, не имеющий ограничений на
значения входящих в эти формулы
переменных. Как правило, линейные
процессы являются составной частью
более сложного алгоритма.
Разветвляющимися
называются
алгоритмы, в которых в зависимости от
значения какого-то выражения или от
выполнения некоторого логического
условия дальнейшие действия могут
производиться по одному из нескольких
направлений.
Каждое
из возможных направлений дальнейших
действий
называется
ветвью.
В
блок-схемах разветвление реализуется
специальным блоком «Решение».
Этот блок предусматривает возможность
двух выходов. В самом блоке «Решение»
записывается логическое условие, от
выполнения которого зависят дальнейшие
действия.
Различают
несколько видов разветвляющихся
алгоритмов.
1.
«Обход»
– такое разветвление, когда одна из
ветвей не содержит ни одного оператора,
т.е. как бы обходит несколько действий
другой ветви.
2.
«Разветвление»
– такой
тип разветвления, когда в каждой из
ветвей содержится некоторый набор
действий.
3.
«Множественный
выбор» –
особый тип разветвления, когда каждая
из нескольких ветвей содержит некоторый
набор действий. Выбор направления
зависит от значения некоторого выражения.
Циклические
алгоритмы
применяются в тех случаях, когда требуется
реализовать многократно повторяющиеся
однотипные вычисления. Цикл
– это последовательность действий,
которая может выполняться многократно,
т.е. более одного раза.
Различают:
-
циклы
с известным числом повторений (или со
счетчиком); -
циклы
с неизвестным числом повторений (циклы
с предусловием и циклы с постусловием).
В
любом цикле должна быть переменная,
которая управляет выходом из цикла,
т.е. определяет число повторений цикла.
Последовательность
действий, которая должна выполняться
на каждом шаге
цикла (т.е.
при каждом повторении цикла), называется
телом цикла
или рабочей
частью цикла.
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
