Алгоритмы и кго свойства

1.

1

2.

Слово «алгоритм» происходит от имени великого
среднеазиатского ученого 8–9 вв. Аль-Хорезми.
Из математических работ Аль-Хорезми до нас
дошли
только
две
–
алгебраическая
и
арифметическая. Вторая книга долгое время
считалась потерянной,
но в 1857 в библиотеке
Кембриджского университета был найден ее перевод
на латинский язык. В ней описаны четыре правила
арифметических действий, практически те же, что
используются и сейчас. Первые строки этой книги
были переведены так: «Сказал Алгоритми. Воздадим
должную хвалу Богу, нашему вождю и защитнику».
Так имя Аль-Хорезми перешло в «Алгоритми», откуда
и появилось слово «алгоритм».
2

3.

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

4. Характеристики исполнителя

1. Круг решаемых задач. Каждый исполнитель
создаётся для решения некоторого круга задач —
построения
цепочек
символов,
выполнения
вычислений, построения рисунков на плоскости и т. д.
2. Среда исполнителя. Область, обстановку,
условия, в которых действует исполнитель, принято
называть средой данного исполнителя.
3. Система команд исполнителя. Различают
команды-приказы и команды-запросы.
4. Режим работы исполнителя. Для большинства
исполнителей
предусмотрены
режимы
непосредственного
(ручного)
управления
и
программного управления.
4

5. Свойства алгоритма

Дискpетность — алгоpитм должен пpедставлять
пpоцесс pешения задачи как последовательное
выполнение пpостых шагов.
Опpеделенность
(Детерминированность)
—
каждое пpавило алгоpитма должно быть четким и
однозначным.
Понятность - исполнитель алгоритма должен
знать, как его выполнять.
Pезультативность - алгоpитм должен пpиводить к
pешению задачи за конечное число шагов.
Массовость –
алгоpитм pешения задачи
pазpабатывается в общем виде, т.е. он должен быть
пpименим
для
некотоpого
класса
задач,
pазличающихся лишь исходными данными.
5

6. Способы записи алгоритмов

словесный (запись на естественном языке);
«Вычислите Z при условии, что Z = X + Y, когда X равен
0,89, а Y равен 1,286. Полученное значение Z следует возвести в
куб и вычислить корень».
графический (изображения из графических
символов);
программный (тексты на языках
программирования).
6

7.

Блок-схема – это графическое изображение
алгоритма в виде определенным образом связанных
между собой нескольких типов блоков.
Для создания блок-схем используются следующие типы блоков:
1. Терминал — поле овальной формы, которое используется для
обозначения начала или окончания программы.
2. Данные — прямоугольник в форме параллелограмма, внутри
которого записаны входные или выходные данные.
3. Процесс — прямоугольное поле, внутри которого
программист записывает основной ход действия алгоритма или
основную логику программы.
4. Решение — прямоугольник в форме ромба, внутри которого
записаны управляющие операторы типа if, условие типа a > 0 и т.д.
Все различные типы блоков соединены друг с другом линиями
со стрелками, которые используются для отображения потока
управления.
7

8. Типы блоков

блок начала (конца)
блок ввода (вывода)
блок действия
блок условия
8

9.

9

10. Виды алгоритмов

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

11. Запись линейного алгоритма в виде блок-схемы

Запись линейного алгоритма в виде блоксхемы
начало
действие 1
…
действие n
конец
11

12.

12

13.

13

14.

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

15.

Ветвление
Полное
если <условие>
то <серия команд 1>
иначе
<серия команд 2>
Неполное
если <условие>
то <серия команд 1>
15

16. Запись полного ветвления в виде блок-схемы

да
серия команд 1
условие
нет
серия команд 2
16

17. Запись неполного ветвления в виде блок-схемы

да
условие
нет
серия команд 1
17

18.

18

19.

Условие – это высказывание, которое может быть
либо истинным, либо ложным.
Простое условие
Включает в себя одно
предложение; два числа,
две переменных или два
арифметических
выражения,
которые
сравниваются между собой
Например: Идет дождь;
5>4; x*y=3+8.
Сложное условие
Последовательность
простых
условий,
объединенных
между
собой
знаками
логических операций
И (AND), ИЛИ (OR).
Например: (10>0) AND
(8>9); (x=10) OR (x>=0).
19

20.

20

21.

Выбор - это алгоритмическая структура, в
которой выполняется одна из нескольких
последовательностей команд при истинности
соответствующего условия.
Полный выбор
при условие 1:
действия 1
при условие 2:
действия 2
............
при условие N:
действия N
иначе действия N+1
Неполный выбор
при условие 1: действия 1
при условие 2: действия 2
............
при условие N: действия N
21

22. Запись полного выбора в виде блок-схемы

да
серия команд 1
условие 1
нет
…
условие n
да
серия команд n
нет
серия команд n+1
22

23. Запись неполного выбора в виде блок-схемы

условие 1
да
серия команд 1
нет
условие 2
да
серия команд 2
нет
…
условие n
нет
да
серия команд n
23

24.

24

25.

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

26. Запись цикла с предусловием в виде блок-схемы

условие
нет
да
тело цикла
26

27. Запись цикла с постусловием в виде блок-схемы

тело цикла
нет
условие
да
27

28. Запись цикла со счетчиком в виде блок-схемы

счетчик
нет
да
тело цикла
28