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

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

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

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

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

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

Пусть a, b, c - длины сторон треугольника. Необходимо найти S - площадь треугольника, P - периметр.

Для нахождения площади можно воспользоваться формулой Герона:

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

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

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

Рис. 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.3. Заданы длины двух катетов в прямоугольном треугольнике. Найти длину гипотенузы, площадь треугольника и величину его углов.

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

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

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

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

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


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

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

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

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

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

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

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

(1.1)

При отрицательном дискриминанте выводится сообщение о том, что действительных корней нет, и вычисляются комплексные корни.Комплексные числа записываются в виде a + ib (формула 1.2):

(1.2)

a - действительная часть комплексного числа, b - мнимая часть комплексного числа.У обоих комплексных корней действительные части одинаковые, а мнимые отличаются знаком. Поэтому можно в переменной x₁ хранить действительную часть числа -b/2a, в переменной x₂ - модуль мнимой части , а в качестве корней вывести x₁+ix₂ и x₁-ix₂.

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

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

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

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

Входные данные: a, b, c. Выходные данные: х₁, х₂, х₃, х₄.

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

Вычисление дискриминанта уравнения d.
Если d >= 0, определяются y₁ и y₂, а иначе корней нет.
Если y₁, y₂ < 0, то корней нет.
Если y₁, y₂ >= 0, то вычисляются четыре корня по формулам 1.3 и выводятся значения корней.

(1.3)

Если условия 3) и 4) не выполняются, то необходимо проверить знак y₁. Если y₁ >= 0, то вычисляются два корня по формуле 1.4. Если же y₂ >= 0, то вычисляются два корня по формуле 1.5. Вычисленные значения корней выводятся.

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

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

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


Рис. 1.14. Проверка входных данных	Рис. 1.15. Повторение ввода переменной а

ПРИМЕР 1.7. Решить кубическое уравнение ax³+ bx² + cx + d=0. Кубическое уравнение имеет вид

ax³ + bx² + cx + d = 0

(1.6)

После деления на a уравнение (1.6) принимает канонический вид:

x³ + rx² + sx + t = 0

(1.7)

где r = b/a, s = c = a, t = d/a. В уравнении (1.7) сделаем замену x = y - y/3 и получим приведенное уравнение (1.8)

y³ + py + q = 0

(1.8)

где

Число действительных корней приведенного уравнения (1.8) зависит от знака дискриминанта

(табл. 1.1).

Табл. 1.1. Количество корней кубического уравнения
Дискриминант	Количество действительных корней	Количество комплексных корней
D > = 0
D < 0		—

Корни приведенного уравнения могут быть рассчитаны по формулам Кардано (1.9).

(1.9)

где

При отрицательном дискриминанте уравнение (1.6) имеет 3 действительных корня, но они будут вычисляться через вспомогательные комплексные величины. Чтобы избавиться от этого, можно воспользоваться формулами (1.10)

(1.10)

Таким образом, при положительном дискриминанте кубического уравнения (1.8) расчет корней будем вести по формулам (1.9), а при отрицательном - по формулам (1.10). После расчета корней приведенного уравнения (1.8) по формулам (1.9) или (1.10) необходимо по формуле x_k = y_k - y/3, где k = 1, 2, 3 перейти к корням заданного кубического уравнения (1.6).

Блок-схема решения кубического уравнения представлена на рис. 1.17.

Описание блок-схемы. В блоке 1 вводятся коэффициенты кубического уравнения, в блоках 2-3 рассчитываются коэффициенты канонического и приведенного уравнений. Блок 4 предназначен для вычисления дискриминанта. В блоке 5 проверяется знак дискриминанта кубического уравнения. Если он отрицателен, то корни вычисляются по формулам (1.10) (блоки 6-7). При положительном значении дискриминанта расчет идет по формулам (1.9) (блок 9). Блоки 8 и 10 предназначены для вывода результатов на экран.

Рис. 1.16. Блок-схема задачи решения кубического уравнения