Laboratory work No.7.
Algorithm.
Goal:
1. To understand basic concept and features of algorithm
2. To acquire practical skills to develop block diagram
Basic concepts of an aalgorithm
Алгоритм - строго определенная последовательность действий, определяющих процесс перехода от исходных данных к искомому результату.
Свойства алгоритма
• Дискретность. Алгоритм должен представлять процесс решения задачи как последовательность выполнения простых действий (шагов, этапов).
• Детерминированность (Однозначность). Каждое действие (шаг, этап) должно быть четким, однозначным, исключающим произвольное толкование и не оставляющим места для двусмысленности.
• Результативность. Алгоритм должен приводить к решению задачи или сообщению, что задача решений не имеет за конечное число шагов.
• Конечность. Каждое отдельное действие, как и весь алгоритм должны иметь возможность реального исполнения. Поэтому алгоритм имеет предел, т. е. конечен.
• Массовость. Алгоритм разрабатывается в общем виде так, чтобы его можно было применять для класса задач, различающихся только исходными данными.
Способы записи алгоритмов
Существуют разные способы записи алгоритмов:
Ø Словесно-формульный,
Ø графический,
Ø операторный (программа на алгоритмическом языке).
а) Словесно-формульный способ. Например, требуется решить квадратное уравнение ax2+bx+c=0 в области действительных чисел. Математической моделью этой задачи является известная формула корней квадратного уравнения:
На основании этой формулы запишем алгоритм:
1. Задать значения а, b, c.
2. Вычислить дискриминант d = b2 – 4ac.
3. Сравнить дискриминант с нулем, если он больше нуля, то вычислить корни по формуле y 1,2= …, иначе сообщить «В области действительных чисел уравнение решений не имеет».
4. Записать результат: «Корни уравнения у1 и у2».
б ) Графический способ описания алгоритма иначе называют блок - схемой. В блок-схемах используются геометрические фигуры, каждая из которых изображает какую-либо операцию или действие, а также этап процесса решения задачи. Каждая фигура называется блоком. Порядок выполнения этапов показывается стрелками, соединяющими блоки. Блоки необходимо размещать сверху вниз или слева направо в порядке их выполнения.
Таблица 1. Наиболее часто употребляемые блоки
| Обозначение блока | Выполняемая функция | ||
| Начало или Конец алгоритма | ||
| Вычисляемые действия | ||
| 
| Проверка условия: выбор одного из двух направлений | |
| Ввод или Вывод данных | ||
| Организация циклических процессов | ||
 
| Направление линий потока – стрелки |
Правила построения алгоритмов на языке блок-схем
1. Блок-схема строится сверху вниз.
2. В любой блок-схеме имеется один элемент, соответствующий началу, и один элемент, соответствующий концу.
3. Должен быть хотя бы один путь из начала блок-схемы к любому элементу.
4. Должен быть хотя бы один путь от каждого элемента блок-схемы в конец блок-схемы.
в) Операторный способ (алгоритмический язык).
Алгоритм – это задание для исполнителя. Исполнитель выполняет алгоритм, т. е. делает то, что написано в алгоритме. Если исполнитель точно выполнит то, что написано в алгоритме, то он получит результат.
Для того чтобы человек и компьютер понимали друг друга, разработаны специальные языки для записей алгоритмов – алгоритмические языки. Самые доступные алгоритмические языки – это Бейсик (Basic), Паскаль (Pascal), Фортран (Fortran).
Алгоритмический язык отличается от машинного языка тем, что состоит из слов и символов, как естественный язык. Алгоритмический язык отличается от естественного языка тем, что в нем мало основных слов (обычно 30-40) и очень строгие правила составления предложений.
Типы алгоритмов
Алгоритмы бывают
Ø линейные
Ø разветвляющиеся
Ø циклические.
Линейный алгоритм – это алгоритм, в котором действия выполняются только один раз и строго в том порядке, в котором они записаны.
Пример. Составить алгоритм вычисления площади трапеции с основаниями a,b и высотой h. S =(a+b)/2 * h
Разветвляющийся алгоритм – это алгоритм, в котором то или иное действие выполняется после анализа условия. Процесс анализа условия и выбора одной из ветвей на блок-схеме показывают с помощью логического блока. Пример разветвляющейся структуры показан на рис. 1.
Процесс анализа условия и выбора одной из ветвей на блок-схеме показывают с помощью логического блока. Логический блок имеет один вход и два выхода (ветвь «да» и ветвь «нет»).
В блок-схемах разветвляющихся алгоритмов всегда есть логический блок.
Пример блок-схемы решения квадратного уравнения ax 2 +bx+c=0.
Рис. 1
Циклический алгоритм (цикл)- это алгоритм, в котором группа операторов выполняется несколько раз подряд. Блок-схема цикла обязательно содержит логический блок, ее структура показана на рис.
Выполняется циклический алгоритм так: сначала проверяется условие, если условие верно (истина), то выполняется тело цикла (действия или группа операторов) и, далее, изменяются значения параметра цикла и снова проверяется условие и т. д. На каком-то шаге условие не выполнится (ложь) и тогда происходит выход из цикла и продолжается выполнение программы.
Пример: построение блок-схем алгоритма циклической структуры.
Вычислить сумму N чисел, последовательно вводимых с клавиатур.
На рис.2 для реализации циклического процесса использованы комбинации блоков присваивания и ветвления.
Задания.
Задание 1. Представить словесно-формульный и графический вид алгоритма решения задачи.
| Вариант | Задание |
| Вариант 1. | Вычислить объем параллелепипеда со сторонами A, B, C и определить, является ли данное геометрическое тело кубом. |
| Вариант 2. | Вычислить площадь треугольника со сторонами А, В, С. Перед вычислением площади проверить условие существования треугольника с заданными сторонами. |
| Вариант 3. | Вычислить квадрат разности двух чисел. |
| Вариант 4. | Вычислить площадь прямоугольника со сторонами A и B и определить, является ли данная фигура квадратом. |
| Вариант 5. | Вычислить площадь треугольника со сторонами A, B, C. Определить, является ли треугольник равнобедренным. |
Задание 2. Разработать и нарисовать блок-схему алгоритма вычисления функции.
Задание 3. Ниже приведены блок-схемы некоторых алгоритмов (рис. 3.1 – 3.4). Который из них является блок-схемой линейной структуры?
Который из них является блок-схемой циклической структуры?
Который из них является блок-схемой разветвленной структуры?
Пояснить ответы.
Рис. 3.1 Рис. 3.2
Рис. 3.3 Рис. 3.4
