Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Линейный алгоритм — это такой, в котором все операции выполняются последовательно одна за другой (рис. 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.4. Алгоритмы разветвленной структуры

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

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

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

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

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

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

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

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

   (1.1)

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

(1.2)

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

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

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

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

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

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

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

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

   (1.3)

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

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

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

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

© 2008 п. Подгорный, г. Майкоп, Республика Адыгея

Биквадратное уравнение в блок схеме

Название работы: Решение биквадратного уравнения в EXCEL

Категория: Конспект урока

Предметная область: Педагогика и дидактика

Описание: Здесь предусмотрены все пять случаев, которые могут встретиться при решении биквадратного уравнения, изложенных подробно в разделе: Алгоритм решения биквадратного уравнения. На рисунке выше коэффициенты указанных уравнений введены в таблицу Excel.

Дата добавления: 2014-06-15

Размер файла: 76 KB

Работу скачали: 28 чел.

Урок . Решение биквадратного уравнения в EXCEL.

Уравнение вида: ax 4 + bx 2 + c = 0, где a, b, c — любые действительные числа, называется биквадратным.

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

1. Прежде всего сделаем замену y = x 2 . Получим квадратное уравнение ay 2 + by + c = 0.
   Решим полученную систему квадратных уравнений.
   y = x 2
   ay 2 + by + c = 0.
   Начнем с решения квадратного уравнения.
   Далее в зависимости от значения переменной y будем решать второе уравнение y=x 2 и находить значения переменной x .
2. вычислим дискриминант квадратного уравнения: d = b 2 — 4ac.
   Далее в зависимости от значения дискриминанта d и от значений переменной y могут встретиться следующие случаи:
3. Случай 1: Если d
4. Если d>=0, то вычислим
   
5. Случай 2: Если d>=0 и y 1 2
6. Случай 3: Если d>=0 и y 1 >=0 и y 2 >=0, то получим 4 решения биквадратного уравнения:
   
7. Случай 4: Если d>=0 и y 1 >=0 и y 2
8. Случай 5: Если d>=0 и y 2 >=0 и y 1

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

3. Проект решения биквадратного уравнения в Excel.

1. В ячейку A1 записать наименование задачи: Решение биквадратного уравнения ax 4 + bx 2 + c = 0.
2. Вторую строку пропустить.
3. В третьей строке указать заголовки столбцов: № п/п; a= ; b= ; c= ; d= ; y 1 ; y 2 ; x 1 = ; x 2 = ; x 3 = ; x 4 = ;
4. Начиная с 4-ой строки, будем располагать матрицу с числовыми значениями коэффициентов a, b, c исходной задачи и необходимые формулы для вычисления значений расчетных величин: d, y 1 , y 2 , x 1 , x 2 , x 3 , x 4 :
5. В ячейку E4 поместить формулу для вычисления d
   =C4*C4 — 4B4*D4 и нажать клавишу Enter.
6. В ячейку F4 поместить формулу для вычисления y 1
   =ЕСЛИ(E4 и нажать клавишу Enter.
7. В ячейку G4 поместить формулу для вычисления y 2
   =ЕСЛИ(E4 и нажать клавишу Enter.
8. В ячейку H4 поместить формулу для вычисления x 1
   =ЕСЛИ(E4 =0;G4>=0);-КОРЕНЬ(F4);
   ЕСЛИ(И(F4>=0;G4 и нажать клавишу Enter.
9. В ячейку I4 поместить формулу для вычисления x 2
   =ЕСЛИ(E4 =0;G4>=0);+КОРЕНЬ(F4);
   ЕСЛИ(И(F4>=0;G4 и нажать клавишу Enter.
10. В ячейку J4 поместить формулу для вычисления x 3
    =ЕСЛИ(E4 =0;G4>=0);-КОРЕНЬ(G4);
    ЕСЛИ(И(F4>=0;G4 и нажать клавишу Enter.
11. В ячейку K4 поместить формулу для вычисления x 4
    =ЕСЛИ(E4 =0;G4>=0);+КОРЕНЬ(G4);
    ЕСЛИ(И(F4>=0;G4 и нажать клавишу Enter.
12. Проект решения задачи вычисления корней биквадратного уравнения ax 4 + bx 2 + c = 0 получен.
    Остается опробовать его или, как говорят программисты, отладить полученный проект.
    Поместим в таблицу Excel матрицу с коэффициентами a, b, c следующих пяти исходных биквадратных уравнений:

8x 4 — 6x 2 + 200 = 0
x 4 + 5x 2 + 6 = 0
x 4 — 5x 2 + 6 = 0
x 4 + x 2 — 6 = 0
x 4 — x 2 — 6 = 0

Здесь предусмотрены все пять случаев, которые могут встретиться при решении биквадратного уравнения, изложенных подробно в разделе: «Алгоритм решения биквадратного уравнения». На рисунке выше коэффициенты указанных уравнений введены в таблицу Excel. Их Вы видите в соответствующих столбцах «a=», «b=», «c=» названной таблицы.
Остается выравнять по длине документа название проекта, данное в ячейке A1 первой строки: «Решение биквадратного уравнения ax 4 + bx 2 + c = 0». Это можно сделать, если вначале выделить данное название по длине документа и затем нажать кнопку с буквой «а» посередине и стрелками справа, слева, сверху и снизу:
Помимо того, нужно четко показать столбцы и строки таблицы. Воспользуйтесь для этого командами выделения границ, представленными ниже нарисунке:

.

Биквадратное уравнение в блок схеме

var a,b,c,d,x1,x2,x3,x4,t1,t2: real ;

writeln( ‘Программа для решения биквадратного уравнения вида ax^4+bx^2+c’ );

write( ‘ введите a= ‘ );

write( ‘ введите b= ‘ );

write( ‘ введите c= ‘ );

if d 0 then writeln( ‘Уравнение не имеет действительных корней’ )

if (t1 0 ) then writeln( ‘x1 и x2 не действительные корни’ )

if (t2 0 ) then writeln( ‘x3 и x4 не действительные корни’ )