АЛГОРИТМЫ

1. АЛГОРИТМ

Алгоритм должен быть определен настолько четко,
чтобы его указаниям мог следовать даже
компьютер.
Дональд Э. Кнут
АЛГОРИТМ
.

2. Схема презентации:

Понятие алгортима
Историческая справка
Свойства алгоритма
Формы записи алгоритма
Базовые структуры алгоритма
Следование
Ветвление
Цикл

3. Понятие АЛГОРИТМ

Алгоритм - заранее заданное
понятное и точное пpедписание
исполнителю совеpшить
определенную последовательность
действий для получения решения
задачи за конечное число шагов.

4. Историческая справка

Название "алгоритм" произошло от латинской
формы имени величайшего среднеазиатского
математика Мухаммеда ибн Муса альХорезми (Alhorithmi), жившего в 783—850 гг. В
своей книге "Об индийском счете" он изложил
правила записи натуральных чисел с помощью
арабских цифр и правила действий над ним
"столбиком",
знакомые
теперь
каждому
школьнику. В XII веке эта книга была переведена
на латынь и получила широкое распространение в
Европе.

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

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

6. В какой форме записываются алгоритмы?

На практике наиболее распространены следующие формы
представления алгоритмов:
словесная (запись на естественном языке);
графическая (изображения из графических символов);
псевдокоды (полуформализованные описания алгоритмов
на условном алгоритмическом языке, включающие в себя
как элементы языка программирования, так и фразы
естественного языка, общепринятые математические
обозначения и др.);
программная (тексты на языках программирования).

7. Базовые структуры алгоритма

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

8. Линейная структура

Образуется последовательностью действий,
следующих одно за другим:

9.

Блок-схема линейного алгоритма
начало
блок «начало»
ввод a, b
блок «ввод»
c = a + b
блок «процесс»
вывод c
блок «вывод»
конец
блок «конец»
9

10. Структура ВЕТВЛЕНИЕ

Обеспечивает в зависимости от результата проверки условия
(да или нет) выбор одного из альтернативных путей работы
алгоритма. Каждый из путей ведет к общему выходу, так что
работа алгоритма будет продолжаться независимо от того,
какой путь будет выбран.
Структура ветвление бывает
полное, неполное

11. ПОЛНОЕ ВЕТВЛЕНИЕ

ЕСЛИ условие
ТО
действие1
ИНАЧЕ действие2
ЕСЛИ будет хорошая погода
ТО пойду гулять
ИНАЧЕ буду читать книгу

12. НЕПОЛНОЕ ВЕТВЛЕНИЕ

ЕСЛИ условие
ТО
действие1
ЕСЛИ правило не выучено
ТО буду учить дальше

13.

Вариант 1. Блок-схема
блок
«решение»
начало
ввод a,b
да
a > b?
max = a
полная
форма
ветвления
нет
max = b
вывод max
конец
? Если a = b?
13

14.

Вариант 2. Блок-схема
начало
ввод a,b
max = a
да
b > a?
нет
неполная
форма
ветвления
max = b
вывод max
конец
14

15.

Сложные условия
Задача. Фирма набирает сотрудников от 25 до 40 лет
включительно. Ввести возраст человека и определить,
подходит ли он фирме (вывести ответ «подходит» или
«не подходит»).
Особенность: надо проверить, выполняются ли два
условия одновременно.
? Можно ли решить известными методами?
15

16.

Вариант 1. Алгоритм
начало
ввод x
да
да
'подходит'
x <= 40?
x >= 25?
нет
нет
'не подходит'
'не подходит'
конец
16

17. Структура ЦИКЛ

Обеспечивает многократное выполнение
некоторой совокупности действий, которая
называется телом цикла.
Основные разновидности циклов:
с параметром
с предусловием
с постусловием

18. ЦИКЛ с параметром

Девиз: Делай ровно столько раз, сколько задано!
Заранее известно количество повторений.
ПОВТОРИ N Раз
действия
КОНЕЦ цикла
ПОВТОРИ 5 раз
приседание
КОНЕЦ цикла

19. ЦИКЛ с предусловием

Девиз: Сначала проверь, потом сделай!
Заранее неизвестно количество повторений.
Цикл может не выполниться ни разу.
ПОКА условие
действия
КОНЕЦ цикла
ПОКА есть силы?
бегу
КОНЕЦ цикла

20. ЦИКЛ с постусловием

Девиз: Сначала сделай, потом проверь!
Заранее неизвестно количество повторений.
Цикл выполниться хотя бы один раз.
ПОВТОРЯТЬ
действия
ПОКА условие
ПОВТОРЯТЬ
бег
ПОКА есть силы

21. Контрольные вопросы.

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Что такое алгоритм?
Что такое исполнитель?
Каким свойствам должен удовлетворять алгоритм?
Какие существуют способы изображения алгоритма?
Что такое блок-схема?
Используя комбинации каких базовых структур алгоритма можно
решить задачу?
Какие бывают виды ветвления?
Какие бывают виды циклического алгоритма?
Какой цикл будет выполнять определенное количество раз?
Какой цикл при определенных условиях не выполнится ни разу?