Алгоритмы

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

1.1. Понятие алгоритма

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

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

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

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

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

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

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

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

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

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

Рис. 1.3. Арифметический блок Рис. 1.4. Условный блок
Рис. 1.3. Арифметический блок Рис. 1.4. Условный блок

В качестве примера рассмотрим блок-схему алгоритма решения уравнения (рис. 1.5), описанного в предыдущем подразделе.

Рис. 1.5. Блок-схема алгоритма решения квадратного уравнения
Рис. 1.5. Блок-схема алгоритма решения квадратного уравнения

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

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

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

Рассмотрим несколько примеров линейных алгоритмов.

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

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

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

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

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

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

ПРИМЕР 1.2. Известны плотность и геометрические размеры цилиндрического слитка, полученного в металлургической лаборатории. Найти объем, массу и площадь основания слитка.

Входные данные: R - радиус основания цилиндра, h - высота цилиндра, ?- плотность материала слитка.
Выходные данные: m - масса слитка, V - объем, S - площадь основания.

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

Рис. 1.8. Алгоритм примера 1.2
Рис. 1.8. Алгоритм примера 1.2

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

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

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

Рис. 1.9 Алгоритм примера 1.3
Рис. 1.9 Алгоритм примера 1.3

1.4. Алгоритмы разветвленной структуры

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

Рис. 1.10 Фрагмент алгоритма Рис. 1.11 Пример разветвления
Рис. 1.10 Фрагмент алгоритма Рис. 1.11 Пример разветвления

Рассмотрим несколько примеров построения алгоритмов разветвленной структуры.

ПРИМЕР 1.4. Известны коэффициенты и с квадратного уравнения. Вычислить корни квадратного уравнения.

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

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

ПРИМЕР 1.5. Составить программу нахождения действительных и комплексных корней квадратного уравнения. Можно выделить следующие этапы решения задачи:

  1. Ввод коэффициентов квадратного уравнения a, b и c.
  2. Вычисление дискриминанта d по формуле d = b2 - 4ас.
  3. Проверка знака дискриминанта. Если d >= 0, то вычисление действительных корней по формуле 1.1 и вывод их на экран.
    (1.1)

    При отрицательном дискриминанте выводится сообщение о том, что действительных корней нет, и вычисляются комплексные корни.Комплексные числа записываются в виде a + ib (формула 1.2):
    (1.2)
    a - действительная часть комплексного числа, b - мнимая часть комплексного числа.У обоих комплексных корней действительные части одинаковые, а мнимые отличаются знаком. Поэтому можно в переменной x1 хранить действительную часть числа -b/2a, в переменной x2 - модуль мнимой части , а в качестве корней вывести x1+ix2 и x1-ix2.

На рис. 1.12 изображена блок-схема решения задачи. Блок 1 предназначен для ввода коэффициентов квадратного уравнения. В блоке 2 осуществляется вычисление дискриминанта. Блок 3 осуществляет проверку знака дискриминанта, если дискриминант отрицателен, то корни комплексные, их расчет происходит в блоке 4 (действительная часть корня записывается в переменную x1, модуль мнимой - в переменную x2), а вывод - в блоке 5 (первый корень x1 + i x2, второй - x1- i x2). Если дискриминант положителен, то вычисляются действительные корни уравнения (блок 6) и выводятся на экран (блок 7).

Рис. 1.12. Блок-схема решения квадратного уравнения
Рис. 1.12. Блок-схема решения квадратного уравнения

ПРИМЕР 1.6. Заданы коэффициенты a, b и с биквадратного уравнения ах4 + bх2 + с = 0. Решить уравнение.

Для решения биквадратного уравнения необходимо заменой y = x2привести его к квадратному и решить это уравнение.

Входные данные: a, b, c. Выходные данные: х1, х2, х3, х4.

Блок-схема представлена на рис. 1.13. Алгоритм состоит из следующих этапов:

  1. Вычисление дискриминанта уравнения d.
  2. Если d >= 0, определяются y1 и y2, а иначе корней нет.
  3. Если y1, y2 < 0 , то корней нет.
  4. Если y1, y2 >= 0 , то вычисляются четыре корня по формулам 1.3 и выводятся значения корней.
    (1.3)
  5. Если условия 3) и 4) не выполняются, то необходимо проверить знак y1. Если y1 >= 0, то вычисляются два корня по формуле 1.4. Если же y2 >= 0, то вычисляются два корня по формуле 1.5. Вычисленные значения корней выводятся.

Рис. 1.13. Алгоритм решения биквадратного уравнения
Рис. 1.13. Алгоритм решения биквадратного уравнения

Еще раз обратимся к алгоритмам на рис. 1.5, 1.12, 1.13. Нетрудно заметить, что если a принимает значение 0, алгоритмы не работают (ведь на 0 делить нельзя). Это - недостаток алгоритмов. Его можно избежать, если проверять значение переменной a сразу после ввода. Алгоритмы такой проверки приведены ниже. В первом случае (рис. 1.14), если введенное значение переменной a = 0, выполнение вычислительного процесса сразу же прекращается. Алгоритм, изображённый на рис. 1.15, позволяет при нулевом значении а повторить ввод переменной. Этот процесс будет продолжаться до тех пор, пока а не станет отличным от нуля. Подобные алгоритмы называются циклическими.

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

НАЦИОНАЛЬНЫЙ ФОНД ПОДГОТОВКИ КАДРОВ. ИНФОРМАТИЗАЦИЯ СИСТЕМЫ ОБРАЗОВАНИЯ.
Сайт сделан по технологии "Конструктор школьных сайтов".
Hosted by uCoz