4_Алгоритмы. Лекция 3 Понятие алгоритма. Изображение алгоритма в виде блоксхемы. Алгоритмы линейной и разветвляющейся структуры

• Название: Лекция 3 Понятие алгоритма. Изображение алгоритма в виде блоксхемы. Алгоритмы линейной и разветвляющейся структуры
• Дата: 29.06.2021
• Размер: 110.6 Kb.
• Имя файла: 4_Алгоритмы.docx
• Тип: Лекция; #222412

ЛЕКЦИЯ № 3

Понятие алгоритма. Изображение алгоритма в виде блок-схемы. Алгоритмы линейной и разветвляющейся структуры
Цель лекции:

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

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

• 
  Ввести исходные данные.
  
• 
  Преобразовать исходные данные в результаты (выходные данные).
  
• 
  Вывести результаты.
  

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

• 
  на естественном языке;
  
• 
  в виде блок-схемы;
  
• 
  в виде R-схемы.
  

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

1. 
   Ввести в компьютер числовые значения переменных а, b и с.
   
2. 
   Вычислить d по формуле d = b² - 4ас.
   
3. 
   Если d < 0, то напечатать сообщение "Корней нет" и перейти к п.4. Иначе вычислить и напечатать значения x₁ и x₂.
   
4. 
   Прекратить вычисления.
   

1.2. Изображение алгоритма в виде блок-схемы

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

Блок начала-конца алгоритма (рис. 1.1). Надпись на блоке: "начало" ("конец").

Блок ввода-вывода данных (рис. 1.2). Надпись на блоке: слово "ввод" ("вывод" или "печать") и список вводимых (выводимых) переменных.

Р ис. 1.1. Блок начала-конца алгоритма
Р ис. 1.2. Блок ввода-вывода данных

Блок решения или арифметический (рис. 1.3). Надпись на блоке: операция или группа операций.

Условный блок (рис. 1.4). Надпись на блоке: условие. В результате проверки условия осуществляется выбор одного из возможных путей (ветвей) вычислительного процесса. Если условие выполняется, то следующим выполняется этап по ветви "+", если условие не выполняется, то выполняется этап по ветви "–".

Рис. 1.3. Арифметический блок




Рис. 1.4. Условный блок



1.3. Алгоритмы линейной структуры

Линейный алгоритм - это такой, в котором все операции выполняются последовательно одна за другой (рис. 1.5).

Рис. 1.5 Размещение блоков в линейном алгоритме



Рассмотрим примеры линейных алгоритмов.
ПРИМЕР 1. Зная длины трех сторон треугольника, вычислить площадь и периметр треугольника.

Пусть a, b, c - длины сторон треугольника. Необходимо найти S - площадь треугольника, P - периметр. Для нахождения площади можно воспользоваться формулой Герона:

,

где r - полупериметр.

Входные данные: a, b, c.

Выходные данные: S, P.

Блок-схема алгоритма представлена на рис. 1.6.

Рис. 1.6. Алгоритм примера 1.



Внимание!!! В этих блоках знак "=" означает не математическое равенство, а операцию присваивания. Переменной, стоящей слева от оператора, присваивается значение, указанное справа. Причем это значение может быть уже определено или его необходимо вычислить с помощью выражения. Например, операция r = (a+b+c)/2 - имеет смысл (переменной r присвоить значение r=(a+b+c)/2), а выражение (a+b+c)/2=r - бессмыслица.
ПРИМЕР 2. Заданы длины двух катетов в прямоугольном треугольнике. Найти длину гипотенузы, площадь треугольника и величину его углов.

Входные данные: a, b - длины катетов.

Выходные данные: с - длина гипотенузы, S - площадь треугольника, α, β - углы.

Блок-схема представлена на рис.1.7.

Рис. 1.7 Алгоритм примера 2.



1.4. Алгоритмы разветвленной структуры
Алгоритмы разветвленной структуры применяются, когда в зависимости от некоторого условия необходимо выполнить либо одно, либо другое действие. В блок-схемах разветвленные алгоритмы изображаются так, как показано на следующих рисунках.
Рис. 1.8 Фрагмент алгоритма


Рис. 1.9 Пример разветвления


В качестве примера рассмотрим блок-схему алгоритма решения уравнения, описанного в подразделе 1.1.
ПРИМЕР 3. Известны коэффициенты a, b и с квадратного уравнения. Вычислить корни квадратного уравнения.

Входные данные: a, b, c.

Выходные данные: x₁ и x₂.
Рис. 1.10. Блок-схема алгоритма решения квадратного уравнения


Нетрудно заметить, что если a принимает значение 0, алгоритм не работает (ведь на 0 делить нельзя). Это - недостаток алгоритмов. Его можно избежать, если проверять значение переменной a сразу после ввода. Можно задать алгоритм, позволяющий при нулевом значении а повторить ввод переменной. Этот процесс будет продолжаться до тех пор, пока а не станет отличным от нуля. Подобные алгоритмы называются циклическими.
Внимание!!! Перед вычислением значения математического выражения это выражение следует проанализировать: для всех ли значений переменных его можно вычислить. В алгоритме необходимо предусмотреть предварительную проверку переменных на значения, для которых выражение не может быть определено. Если, например, требуется вычислить корень четной степени, то нужно перед вычислением проверить подкоренное выражение - оно не должно принимать отрицательные значения, а в случае с дробью - проверить знаменатель на 0. В блок-схеме такие проверки реализуются с помощью условного блока. Отсутствие таких проверок в программе может привести к критическим ошибкам.

Задание 1
Дан алгоритм:




После выполнения данного алгоритма переменной с присвоится значение …
Задание 2
Дана блок-схема:



Тогда после исполнения алгоритма переменной x присваивается значение …
Задание 3

Значениями переменных a и b являются натуральные числа. Пусть a=55 и b=33 тогда в результате работы следующего алгоритма:

1. Если a=b, то работа алгоритма закончена; иначе выполняется пункт 2;

2. Если a>b, то переменной a присваивается значение a-b; иначе переменной bприсваивается значение b-a;

3. Выполняется пункт 1 данного алгоритма.

переменная a примет значение равное …