алгоритм. Лекция Понятие алгоритма. Изображение алгоритма в виде блоксхемы. Алгоритмы линейной и разветвляющейся структуры. Цель лекции
 Скачать 456.78 Kb.
|
|
ЛЕКЦИЯ № 1. Понятие алгоритма. Изображение алгоритма в виде блок–схемы. Алгоритмы линейной и разветвляющейся структуры. : Цель лекции Знакомство с понятием алгоритма и возможностью . его изображения в виде блок схемы Приобретение навыков построения . алгоритмов линейной и разветвляющейся структуры Решение любой задачи на ЭВМ необходимо разбить на следующие этапы: разработка алгоритма решения задачи, составление программы решения задачи на алгоритмическом языке, ввод программы в ЭВМ, отладка программы (исправление ошибок), выполнение программы на ПК, анализ полученных результатов. Рассмотрим первый этап решения задачи – разработку алгоритма. 1. Понятие алгоритма Алгоритм – четкое описание последовательности действий, которые необходимо выполнить при решении задачи. Можно сказать, что алгоритм описывает процесс преобразования исходных данных в результаты, т.к. для решения любой задачи необходимо: 1. Ввести исходные данные. 2. Преобразовать исходные данные в результаты (выходные данные). 3. Вывести результаты. Разработка алгоритма решения задачи – это разбиение задачи на последовательно выполняемые этапы, причем результаты выполнения предыдущих этапов могут использоваться при выполнении последующих. При этом должны быть четко указаны как содержание каждого этапа, так и порядок выполнения этапов. Отдельный этап алгоритма представляет собой либо другую, более простую задачу, алгоритм решения которой известен (разработан заранее), либо должен быть достаточно простым и понятным без пояснений. Разработанный алгоритм можно записать несколькими способами: • на естественном языке; • в виде блок-схемы; • в виде R-схемы. Рассмотрим пример алгоритма на естественном языке: 1. Ввести в компьютер числовые значения переменных а, b и с. 2. Вычислить d по формуле d = b² - 4ас. 3. Если d < 0, то напечатать сообщение «Корней нет» и перейти к п.4. Иначе вычислить a d b X , a d b X 2 2 2 1 − − = + − = и напечатать значения Х 1 и Х 2 4. Прекратить вычисления. 2. Изображение алгоритма в виде блок-схемы Блок-схемой называется наглядное графическое изображение алгоритма, когда отдельные его этапы изображаются при помощи различных геометрических фигур – блоков, а связи между этапами (последовательность выполнения этапов) указываются при помощи стрелок, соединяющих эти фигуры. Блоки сопровождаются надписями. Типичные действия алгоритма изображаются следующими геометрическими фигурами: Блок начала-конца алгоритма (рис. 2.1). Надпись на блоке: «начало» («конец»). Блок ввода-вывода данных (рис. 2.2). Надпись на блоке: слово «ввод» («вывод» или «печать») и список вводимых (выводимых) переменных. Рис. 2.1. Блок начала-конца алгоритма Рис. 2.2. Блок ввода-вывода данных Блок решения или арифметический (рис. 2.3). Надпись на блоке: операция или группа операций. Условный блок (рис. 2.4). Надпись на блоке: условие. В результате проверки условия осуществляется выбор одного из возможных путей (ветвей) вычислительного процесса. Если условие выполняется, то следующим выполняется этап по ветви «+», если условие не выполняется, то выполняется этап по ветви «−». Рис. 2.3. Арифметический блок Рис. 2.4. Условный блок В качестве примера рассмотрим блок-схему алгоритма решения уравнения (рис. 2.5), описанного в предыдущем подразделе. Рис. 2.5. Блок-схема алгоритма решения квадратного уравнения 3. Алгоритмы линейной структуры Линейный алгоритм – это такой, в котором все операции выполняются последовательно одна за другой (рис. 3.1). Рис. 3.1. Размещение блоков в линейном алгоритме Рассмотрим несколько примеров линейных алгоритмов. ПРИМЕР 3.1. Зная длины трех сторон треугольника, вычислить площадь и периметр треугольника. Пусть a, b, c – длины сторон треугольника. Необходимо найти S – площадь треугольника, P – периметр. Для нахождения площади можно воспользоваться формулой Герона: r= r r−ar−br −c , где r – полупериметр. Входные данные: a, b, c. Выходные данные: S, P. Блок-схема алгоритма представлена на рис. 3.2. Рис. 3.2. Алгоритм примера 3.1 Внимание!!! В этих блоках знак «=» означает не математическое равенство, а операцию присваивания. Переменной, стоящей слева от оператора, присваивается значение, указанное справа. Причем это значение может быть уже определено или его необходимо вычислить с помощью выражения. Например, операция r = (a+b+c)/2 – имеет смысл (переменной r присвоить значение r=(a+b+c)/2), а выражение (a+b+c)/2=r – бессмыслица. ПРИМЕР 3.2.Известны плотность и геометрические размеры цилиндрического слитка, полученного в металлургической лаборатории. Найти объем, массу и площадь основания слитка. Входные данные: R – радиус основания цилиндра, h – высота цилиндра, ρ – плотность материала слитка. Выходные данные: m – масса слитка, V – объем, S – площадь основания. Блок-схема представлена на рис. 3.3. Рис. 3.3. Алгоритм примера 3.2 ПРИМЕР 3.3. Заданы длины двух катетов в прямоугольном треугольнике. Найти длину гипотенузы, площадь треугольника и величину его углов. Входные данные: a, b – длины катетов. Выходные данные: с – длина гипотенузы, S – площадь треугольника, α, β – углы. Блок-схема представлена на рис. 3.4. Рис. 3.4. Алгоритм примера 3.3 4. Алгоритмы разветвленной структуры Алгоритмы разветвленной структуры применяются, когда в зависимости от некоторого условия необходимо выполнить либо одно, либо другое действие. В блок-схемах разветвленные алгоритмы изображаются так, как показано на рис. 4.1 – 4.2. Рис. 4.1. Фрагмент алгоритма Рис. 4.2. Пример разветвления разветвленной структуры структуры алгоритма Рассмотрим несколько примеров построения алгоритмов разветвленной структуры. ПРИМЕР 4.1. Известны коэффициенты а, b и с квадратного уравнения. Вычислить корни квадратного уравнения. Входные данные: a, b, c. Выходные данные: х 1 , х 2 Блок-схема представлена на рис. 2.5. ПРИМЕР 4.2. Составить программу нахождения действительных и комплексных корней квадратного уравнения. Можно выделить следующие этапы решения задачи: 1. Ввод коэффициентов квадратного уравнения a, b и c. 2. Вычисление дискриминанта d по формуле 2 d = b 4ac − 3. Проверка знака дискриминанта. Если d≥0, то вычисление действительных корней a d b X , a d b X 2 2 2 1 − − = + − = и вывод их на экран. При отрицательном дискриминанте выводится сообщение о том, что действительных корней нет, и вычисляются комплексные корни. Комплексные числа записываются в виде a +ib, где a – действительная часть комплексного числа, b – мнимая часть комплексного числа, i – мнимая единица – 1 i = − , 1 2 , 2 2 2 2 d d b b X i X i a a a a − − = + = − У обоих комплексных корней действительные части одинаковые, а мнимые отличаются знаком. Поэтому можно в переменной x1 хранить действительную часть числа 2 b a − , в переменной x2 – модуль мнимой части 2 d a , а в качестве корней вывести x1+ix2 и x1-ix2. На рис. 4.3 изображена блок-схема решения задачи. Блок 1 предназначен для ввода коэффициентов квадратного уравнения. В блоке 2 осуществляется вычисление дискриминанта. Блок 3 осуществляет проверку знака дискриминанта, если дискриминант отрицателен, то корни комплексные, их расчет происходит в блоке 4 (действительная часть корня записывается в переменную x1, модуль мнимой – в переменную x2), а вывод – в блоке 5 (первый корень x1+ix2, второй – x1-ix2). Если дискриминант положителен, то вычисляются действительные корни уравнения (блок 6) и выводятся на экран (блок 7). Рис. 4.3. Блок-схема решения квадратного уравнения ПРИМЕР 4.3. Заданы коэффициенты a, b и с биквадратного уравнения ах 4 +bх² +с=0. Решить уравнение. Для решения биквадратного уравнения необходимо заменой y = x 2 привести его к квадратному и решить это уравнение. Входные данные: a, b, c. Выходные данные: х 1 , х 2 , х 3 , х 4 . Блок-схема представлена на рис. 4.4. Алгоритм состоит из следующих этапов: 1. Вычисление дискриминанта уравнения d. 2. Если d ≥ 0, определяются y 1 и y 2 , а иначе корней нет. 3. Если y 1 , y 2 < 0 , то корней нет. 4. Если y 1 , y 2 ≥ 0 , то вычисляются четыре корня по формулам 2 1 y , y ± ± и выводятся значения корней. 5. Если условия 3) и 4) не выполняются, то необходимо проверить знак y 1 Если y 1 ≥ 0, то вычисляются два корня по формуле 1 y ± . Если же y 2 ≥ 0, то вычисляются два корня по формуле 2 y ± . Вычисленные значения корней выводятся. Рис. 4.4. Алгоритм решения биквадратного уравнения Еще раз обратимся к алгоритмам на рис. 2.5, 4.3, 4.4. Нетрудно заметить, что если a принимает значение 0, алгоритмы не работают (ведь на 0 делить нельзя). Это – недостаток алгоритмов. Его можно избежать, если проверять значение переменной a сразу после ввода. Алгоритмы такой проверки приведены ниже. В первом случае (рис. 4.5), если введенное значение переменной a = 0, выполнение вычислительного процесса сразу же прекращается.Алгоритм, изображённый на рис. 4.6, позволяет при нулевом значении а повторить ввод переменной. Этот процесс будет продолжаться до тех пор, пока а не станет отличным от нуля. Подобные алгоритмы называются циклическими. Внимание!!! Перед вычислением значения математического выражения это выражение следует проанализировать: для всех ли значений переменных его можно вычислить. В алгоритме необходимо предусмотреть предварительную проверку переменных на значения, для которых выражение не может быть определено. Если, например, требуется вычислить корень четной степени, то нужно перед вычислением проверить подкоренное выражение - оно не должно принимать отрицательные значения, а в случае с дробью – проверить знаменатель на 0. В блок-схеме такие проверки реализуются с помощью условного блока. Отсутствие таких проверок в программе может привести к критическим ошибкам. Рис. 4.5. Проверка входных Рис. 4.6. Повторение ввода данных переменной а ПРИМЕР 4.4. Решить кубическое уравнение ax 3 +bx 2 +cx+d=0. Кубическое уравнение имеет вид 3 2 0 ax bx cx d + + + = (4.1) После деления на a уравнение (4.1) принимает канонический вид: 3 2 0 x rx sx t + + + = (4.2) где b r a = , c s a = , d t a = . В уравнении (4.2) сделаем замену 3 r x y = − и получим приведенное уравнение (4.3) 3 0 y py q + + = , (4.3) где 2 3 3 s r p − = , 3 2r q 27 3 rs t = − + Число действительных корней приведенного уравнения (4.3) зависит от знака дискриминанта 3 2 3 2 p q D = + (табл. 4.1). Табл. 4.1. Количество корней кубического уравнения Дискриминант Количество действительных корней Количество комплексных корней D≥0 1 2 D<0 3 - Корни приведенного уравнения могут быть рассчитаны по формулам Кардано (4.4). 1 2 3 3 2 2 3 2 2 y u v u v u v y i u v u v y i = + + − = − + + − = − − (4.4) где 3 3 , 2 2 q q u D v D = − + = − − При отрицательном дискриминанте уравнение (4.1) имеет 3 действительных корня, но они будут вычисляться через вспомогательные комплексные величины. Чтобы избавиться от этого, можно воспользоваться формулами (4.5) 3 1 3 2 3 3 2 cos 3 2 2 cos 3 3 4 2 cos 3 3 y y y ϕ = ρ ϕ π = ρ + ϕ π = ρ + , где 3 27 p − ρ = , cos( ) 2 q ϕ = − ρ (4.5) Таким образом, при положительном дискриминанте кубического уравнения (4.3) расчет корней будем вести по формулам (4.4), а при отрицательном – по формулам (4.5). После расчета корней приведенного уравнения (4.3) по формулам (4.4) или (4.5) необходимо по формулам , k=1,2,3 3 k k r x y = − перейти к корням заданного кубического уравнения (4.1). Блок-схемарешения кубического уравнения представлена на рис. 4.7. Описание блок-схемы.В блоке 1 вводятся коэффициенты кубического уравнения, в блоках 2-3 рассчитываются коэффициенты канонического и приведенного уравнений. Блок 4 предназначен для вычисления дискриминанта. В блоке 5 проверяется знак дискриминанта кубического уравнения. Если он отрицателен, то корни вычисляются по формулам (4.5) (блоки 6-7). При положительном значении дискриминанта расчет идет по формулам (4.4) (блок 9). Блоки 8 и 10 предназначены для вывода результатов на экран. Рис. 4.7. Блок-схема задачи решения кубического уравнения |