Алгоритм ветвления. Отличие от алгоритмов линейной структуры | OTUS

Курсы

Программирование
iOS Developer. Basic
-23%
Python Developer. Professional
-13%
Golang Developer. Professional
-17%
Python Developer. Basic
-16%
iOS Developer. Professional
-13%
C# ASP.NET Core разработчик
-18%
Unity Game Developer. Professional
-11%
React.js Developer
-12%
Android Developer. Professional
-7%
Software Architect
-12%
C++ Developer. Professional
-8%
Разработчик C#
-8%
Backend-разработчик на PHP
-8%
Архитектура и шаблоны проектирования
-12%
Программист С Разработчик на Spring Framework MS SQL Server Developer AWS для разработчиков Cloud Solution Architecture Разработчик голосовых ассистентов и чат-ботов Vue.js разработчик VOIP инженер Нереляционные базы данных Супер - интенсив по паттернам проектирования Супер-практикум по использованию и настройке GIT IoT-разработчик Advanced Fullstack JavaScript developer Супер-интенсив Azure
Инфраструктура
Мониторинг и логирование: Zabbix, Prometheus, ELK
-17%
DevOps практики и инструменты
-18%
Архитектор сетей
-21%
Инфраструктурная платформа на основе Kubernetes
-22%
Супер-интенсив «IaC Ansible»
-16%
Супер-интенсив по управлению миграциями (DBVC)
-16%
Administrator Linux. Professional
-5%
Administrator Linux.Basic
-10%
Супер-интенсив «ELK»
-10%
Базы данных Сетевой инженер AWS для разработчиков Cloud Solution Architecture Разработчик голосовых ассистентов и чат-ботов Внедрение и работа в DevSecOps Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Супер-интенсив «СУБД в высоконагруженных системах»
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

Алгоритм ветвления. Отличие от алгоритмов линейной структуры

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

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

Алгоритм – это ясный перечень действий, который направлен на решение какой-либо задачи. Одно из свойств алгоритма — дискретность. Дискретность связана с наличием в алгоритмической последовательности ряда операций (этапов, действий), выполняемых пошагово, то есть дискретно. Алгоритм обладает свойством дискретности, так как он представляет собой процесс решения задачи в виде последовательного выполнения простых шагов. И каждое действие исполняется лишь после окончания исполнения предыдущего. Также предполагается наличие определённых исходных данных и результата выполнения.

Блок-схема — графический способ описания алгоритмов. Графическое представление обеспечивает наглядность и упрощает запись, делая последовательность более понятной. При использовании схемы каждому действию соответствует определённая геометрическая фигура (эти фигуры называют блоками). Вот наиболее часто употребляемые:

1-1801-45f906.png

Ещё раз о линейности

Линейная последовательность — самая простая из возможных структур. При наличии линейности команды выполняются в чёткой последовательности и в порядке их записи, то есть друг за другом. Вот линейная алгоритмическая последовательность посадки дерева: 1) выкапывание ямки в земле; 2) размещение в ямке саженца; 3) закапывание ямки; 4) поливание места посадки водой.

Такой линейный алгоритм имеет следующую блок-схему:

2-1801-c5c0b7.png

А вот и общая схема линейного алгоритма:

3-1801-35f267.png

Ветвление в алгоритмических последовательностях

На практике очень редко встречается, чтобы последовательность всех требуемых действий была известна заранее. Если на минуту покинуть мир алгоритмизации и программирования, можно спроецировать ветвление на многие жизненные ситуации. Если на улице дождь, человек берёт зонт, если очень жарко, будет выбрана одежда полегче и т. д. Всё зависит от условия выбора. Как тут не вспомнить рыцаря на распутье из русских народных сказок?

4-1801-2c4a5c.png

«Направо пойдёшь — жену найдёшь, налево пойдешь — богатым будешь, прямо пойдёшь — смерть найдёшь».

Подобная ситуация заставляет принимать решения с учётом определённого условия. Если нужна жена, то витязь идёт направо, если богатство, то налево, если жизнь не мила, то прямо. Условия, которые влияют на решение, располагаются между словами «если» и «то».

От значения условий зависит дальнейшее поведение. Когда условие выполняется, оно принимает значение «истина», когда нет — «ложь». Иногда анализ ситуации и выбор не вызывают особых затруднений, а иногда принять решение очень трудно. А всё потому, что принимающий решение пытается продумать каждый из вариантов и предугадать последствия выбора. Нельзя не вспомнить гроссмейстера, который анализирует позицию на ходы вперёд, прежде чем передвинуть фигуру на шахматной доске.

Компьютерные программы и игры тоже построены на выборе действий. А блок-схема при наличии ветвления приобретает иной вид:

4.1-1801-fa94a6.png

Логика разветвляющих алгоритмов

Логику можно описать следующим образом:

ЕСЛИ <условие истинно> ТО <действие 1> ИНАЧЕ <действие 2>

Ветвление — метод и форма организации действий, когда в зависимости от выполнения определённого условия совершается та либо иная последовательность шагов.

В результате совсем несложно составить алгоритм покупки мороженого с учётом наличия необходимой суммы денег. Описать эту алгоритмическую последовательность с помощью схемы и блоков тоже не составит труда:

5-1801-c7b186.png

Для закрепления можно решить задачу.

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

Решение легко описывается посредством схематических блоков:

6-1801-145fea.png

Следующий пример легко экстраполируется в жизнь. Речь идёт об алгоритме для перехода дороги при наличии светофора. Он имеет следующий вид: 1. Подходим к светофору. 2. Смотрим, какой горит свет. 3. Если зелёный, переходим дорогу. 4. Если красный, ждём, пока загорится зелёный, а потом переходим дорогу.

Соответствующая блок-схема:

7-1801-391350.png

Программный способ записи

Чтобы алгоритм было понятен компьютеру, машине и любой другой цифровой системе, следует оформить его в таком виде, который эта система способна воспринимать. То есть надо написать программу, используя для этого команды из СКИ. СКИ — это список команд исполнителя — перечень команд, ему понятных. А любой исполнитель способен исполнить лишь те команды, которые включены в его СКИ, а если говорить человеческим языком — входят в набор его компетенций.

Для примера можно реализовать алгоритм на языке программирования 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. Но не стоит на этом останавливаться — лучше всего написать собственную программу, что позволит получить максимальную пользу от урока.

Algo_970x90-1801-545cb2.png

Источники: • 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.

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться