Примеры алгоритмов

1.

Примеры алгоритмов
Оплата через терминал
На
экране
появится
окно
«сумма
оплаты».
Ввести
Для
совершения
номер
в
окно
счёта.
«сумма
оплаты,
оплаты»
необходимо
число,
указанное
выбрать нужную
на квитанции.
опцию
Выбрать
пункт
«Оплатить
услуги»
Вносить
с купюроприемник,
пока
не получится
число,
Нажать
кнопку
«оплатить»
и дождаться
распечатки
чека.
На
Если
наэкране
экране
всёкупюры
правильно,
появится
терминала.
окно
то нажать
выбора
кнопку
суммы
«далее».
оплаты.
равное введенной ранее в окне выбора суммы оплаты.

2.

Примеры алгоритмов
Нарисовать лошадь

3.

Примеры алгоритмов
Вычислительный алгоритм
Среднее арифметическое двух чисел
1. Задать два числа
2. Сложить заданные числа
3. Разделить сумму на 2
Общая схема работы алгоритма
Исходные данные
Алгоритм
Результат

4.

Исполнитель алгоритма
Исполнитель - это некоторый объект (человек, животное,
техническое
устройство),
способный
выполнять
определённый набор команд.
Исполнитель
Формальный
Неформальный
Круг решаемых задач
Среда исполнителя
Область, обстановка, условия
СКИ
Непосредственное управление
Режимы работы
Программное управление
Исполнители алгоритмов

5.

Разработка алгоритма
Разработка алгоритма
Определение объектов,
указанных в задаче
Установление свойств
объектов, отношений
и действий с объектами
Определение исходных
данных и результата
Определение
последовательности
действий
Запись
последовательности
действий с помощью
команд СКИ
Алгоритм – модель деятельности исполнителя алгоритмов

6.

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

7.

Дискретность (от лат. discretus – разделенный,
прерывистый) указывает, что любой алгоритм должен
состоять
из
конкретных
действий,
следующих
в
определенном порядке. Образованная структура алгоритма
оказывается дискретной: только выполнив одну команду,
исполнитель сможет приступить к выполнению следующей.
Начало
x, y
нет
да
x>y
a=x
a=y
a
Конец

8.

Понятность означает, что алгоритм состоит только из
команд, входящих в систему команд исполнителя, т. е. из
таких команд, которые исполнитель может воспринять и по
которым может выполнить требуемые действия.
Окрошка «Мясная»
1-1.5 л кваса
500 г картофеля
300 г колбасы
3 яйца
200 г редиса
300 г огурцов
зелень по вкусу
сметана
соль
перец
Рецепт приготовления
Картофель отварить до готовности.
Остудить, почистить.
Нарезать кубиками.
Колбасу нарезать кубиками.
Яйца нарезать кубиками.
Редис тонко нарезать.
Огурцы нарезать кубиками.
Смешать картофель, колбасу, яйца,
редис, огурцы.
Посолить, поперчить.
Выложить в тарелки.
Залить квасом, посыпать зеленью.
Подавать со сметаной.

9.

Определённость означает, что в алгоритме нет команд,
смысл которых может быть истолкован исполнителем
неоднозначно;
недопустимы
ситуации,
когда
после
выполнения очередной команды исполнителю неясно, какую
команду выполнять на следующем шаге.
Доехать до стадиона
1. Идти прямо
2. Повернуть
3. Идти прямо
4. Сесть в автобус
5. Доехать до остановки «Стадион»
Алгоритм не уточняет, какое расстояние нужно пройти прямо.
В какую сторону повернуть.
В какой автобус сесть.

10.

Результативность означает, что алгоритм должен
обеспечивать возможность получения результата после
конечного, возможно, очень большого, числа шагов. При этом
результатом считается не только обусловленный постановкой
задачи ответ, но и вывод о невозможности продолжения по
какой-либо причине решения данной задачи.
Чтение книги
1. Взять книгу
2. Открыть первую страницу
3. Пока не конец книги выполнять
следующие действия:
3.1 Прочитать текст
3.2 Перелистнуть страницу
3.3 Прочитать текст
3.4 Открыть первую страницу
Данная последовательность команд не соответствует
свойству результативности. Что нужно изменить?

11.

Массовость означает, что алгоритм должен обеспечивать
возможность его применения для решения любой задачи из
некоторого класса задач с различными исходными данными.
Алгоритм вычисления корней квадратного уравнения.
Начало
b b 4ac
2a
2
x1, 2
Ввод
коэффициентов
Вычислить
дискриминант
Дискриминант
меньше 0?
да
нет
Вычислить
значения корней
Вывод корней
Конец
«Корней нет»

12.

Решето Эратосфена
Решето Эратосфена
Рассмотренная последовательность действий является
алгоритмом, так как она удовлетворяет свойствам:
• дискретности - процесс нахождения простых чисел
разбит на шаги;
• понятности - каждая команда понятна ученику 9 класса,
выполняющему этот алгоритм;
• определённости - каждая команда трактуется и
выполняется исполнителем однозначно; имеются указания
об очерёдности выполнения команд;
• результативности - через некоторое число шагов
достигается результат;
• массовости - последовательность действий применима
для любого натурального n.

13.

Алгоритм - это предназначенное для
конкретного
исполнителя
описание
последовательности действий, приводящих от
исходных данных к требуемому результату,
которое обладает свойствами:
• дискретности
• понятности
• определённости
• результативности
• массовости

14.

Возможности автоматизации
деятельности человека
Решение задачи по готовому алгоритму требует от
исполнителя
только
строгого
следования
заданным
предписаниям.
Формального
исполнения
алгоритма
обеспечивает
возможность автоматизации деятельности человека
Процесс решения задачи представляется
в виде последовательности операций
Создается машина, способная выполнять
эти операции в указанной последовательности
Человек освобождается от рутинной работы,
выполнение которой поручается автомату

15.

Автоматизация деятельности человека
Автоматизация
Автоматизация
торговли.
гостиниц.
Роботизированная
сборки,
управляемая
Автоматизация
Профессиональная
услуг влиния
система
сфере
торговли
«UCS-Shelter».
делает скорость работы
компьютером
и запрограммированная
на
производство
Автоматизация
производства
персонала
Автоматизированы
значительно
такие
выше,
процессы
поднимаеткак
уровень
бронирование,
сварных
швов
на корпусеработа
каждого
обслуживания
поселение,
выселение,
покупателей,
позволяет
соавтомобиля
счетами
вести учет
гостей.
товара.

16.

Самое главное
Исполнитель - некоторый объект (человек, животное,
техническое устройство), способный выполнять определённый
набор команд.
Формальный исполнитель одну и ту же команду всегда
выполняет одинаково. Для каждого формального исполнителя
можно указать: круг решаемых задач, среду, систему команд и
режим работы.
Алгоритм - предназначенное для конкретного исполнителя
описание последовательности действий, приводящих от
исходных данных к требуемому результату, которое обладает
свойствами дискретности, понятности, определённости,
результативности и массовости.
Способность
исполнителя
действовать
формально
обеспечивает возможность автоматизации деятельности
человека.

17.

Опорный конспект
Алгоритм - это предназначенное для конкретного исполнителя
описание последовательности действий, приводящих от исходных
данных к требуемому результату, которое обладает свойствами
дискретности,
понятности,
определённости,
результативности и массовости.
Свойства алгоритма
Дискретность
Понятность
Определённость
Результативность
Массовость

18.

Марков А.А. (1903—1979) установил, что
алгоритмы должны содержать предписания
двух видов:
1) функциональные операторы
направленные
на
непосредственное
информации;
-
предписания,
преобразование
2)
логические
операторы
предписания,
определяющие дальнейшее направление действий.
Именно эти операторы положены в основу большинства
способов записи алгоритмов.

19.

Основные способы записи
алгоритма
Словесные
Графические
На алгоритмических
языках
Словесное
описание
Последовательность рисунков
Школьный
алгоритмический
язык
Построчная
запись
Структурограмма
Язык
программирования
Блок-схема

20.

Словесное описание
Словесное описание - самая простая запись алгоритма в
виде набора высказываний на обычном разговорном языке.
Пример. Словесное описание алгоритма
нахождения наибольшего общего делителя
(НОД) пары целых чисел (алгоритм
Евклида).
Чтобы найти НОД двух чисел, составьте
таблицу из двух столбцов и назовите
столбцы X и Y. Запишите первое из
заданных чисел в столбец Х, а второе - в
столбец Y. Если данные числа не равны,
замените большее из них на результат
вычитания из большего числа меньшего.
Повторяйте такие замены до тех пор,
пока числа не окажутся равными, после чего
число из столбца Х считайте искомым
результатом.

21.

Построчная запись
Правила построчной записи алгоритма
Каждое предписание записывается с новой строки
Предписание (шаги) алгоритма нумеруются
Исполнение алгоритма происходит в порядке
возрастания номеров шагов, начиная с первого,
если нет особых указаний
Кроме слов естественного языка предписания могут
содержать математические выражения и формулы.

22.

Построчная запись алгоритма
Евклида
Построчная запись алгоритма Евклида
1. Начало.
2. Обозначить первое из заданных чисел Х, второе - Y.
3. Если Х = Y то перейти к п. 9.
4. Если X >Y , то перейти к п. 5, иначе перейти к п. 7.
5. Заменить X на X-Y.
6. Перейти к п. 3.
7. Заменить Y на Y-X
8. Перейти к п. 3.
9. Считать Х искомым результатом.
10. Конец.

23.

Графические способы
Структурограмма
Последовательные картинки

24.

Блок-схемы
В блок-схеме предписания изображаются с помощью
различных геометрических фигур, а последовательность
выполнения шагов указывается с помощью линий.
Блок начала или конца алгоритма
Блок ввода или вывода данных
Блок обработки данных
Блок проверки условия
Блок пояснительных записей

25.

Запись алгоритма Евклида с помощью
блок-схемы
Начало
Ввод значений X и Y
X,Y
Да
Нет
X:=Y
Да
X:=X-Y
НОД:=Х
НОД
Конец
Проверка равенства X и Y
X<Y
Нет
Y:=Y-X
Определение большего
из X и Y
Уменьшение большего числа
на величину меньшего
Определение НОД
Вывод НОД

26.

Алгоритмические языки
Алгоритмические
языки
формальные
предназначенные для записи алгоритмов.
языки,
Характеристики алгоритмического языка
Алфавит
Набор используемых символов
Синтаксис
Система правил образования
конструкций языка
Семантика
Система правил, определяющих
смысл и способ употребления
конструкций языка

27.

Самое главное
Существуют различные способы записи алгоритмов:
• словесное описание
• построчная запись
• блок-схема
• школьный алгоритмический язык и другие.
Каждый
из
этих
способов
достоинствами и недостатками.
обладает
своими

28.

Опорный конспект
Способы записи алгоритмов
Словесный
Блок-схема
Алгоритмический
язык
Обычный
разговорный
язык
Геометрические
фигуры
Слова имеют
заданный смысл и
способ записи

29.

Величины
Алгоритмы описывают последовательность действий над
некоторыми информационными объектами.
Величина
в
информатике
информационный объект.
–
это
отдельный
Информационный объект
Число
Символ
Строка
Величина
Постоянная
Переменная
Таблица

30.

Операции над величинами
Операции над величинами
Арифметические
Отношения
+ (сложение)
- (вычитание)
* (умножение)
/ (деление)
< (меньше)
> (больше)
<= (не больше)
>= (не меньше)
= (равно)
Логические
И (конъюнкция)
ИЛИ (дизъюнкция)
НЕ (инверсия)
Операнды - объекты, над которыми выполняют операции.

31.

Типы величин
Тип величины в алгоритме
Целая
Числовой
Вещественная
Текстовый
Символьная
Литерная
Логический
ДА (ИСТИНА, TRUE, 1)
НЕТ (ЛОЖЬ, FALSE, 0)
Один
символ
Строка
символов

32.

Имя величины
Имя величины в алгоритме
Латинская
буква
A, B, M, AP
Латинская
буква и цифра
A1, B4, M2
Мнемоническое
имя
SUMMA, PLAN

33.

Выражения
Выражение - языковая конструкция для вычисления
значения с помощью одного или нескольких операндов.
Выражения
Арифметические
2 x 3
sqrt ( x )
Строковые
Операция
сцепления (+).
А=`том`
`a`+А= `атом`
Логические
X>5
X<10
X<=3

34.

Команда присваивания
<имя переменной>:= <выражение>
Свойства присваивания
Пока переменной не присвоено значение, она
остаётся неопределённой
Значение, присвоенное переменной, сохраняется
до следующего присваивания
Если переменной присваивается новое значение,
то предыдущее её значение теряется

35.

Алгоритм обмена значений переменных
Алгоритм, в результате которого переменные А и В
литерного типа обменяются своими значениями.
Решение
!
Неверно
А:=В
В:=А
Верно
алг обмен значениями (лит А, В)
арг А, В
рез А, В
нач лит М
М:=А
А:=В
В:=М
кон

36.

Аналогия с перемещением
Алгоритм перемещения зайца из клетки 1 в клетку 2, а
волка - из клетки 2 - в клетку 1. Нужна клетка 3.
1
2
3

37.

Табличные величины
В
практической
деятельности
используются всевозможные таблицы.
человека
Таблица
Линейная
Прямоугольная
Одномерный
массив
Двумерный
массив
Дни недели
Табель
успеваемости
часто

38.

Примеры линейных таблиц
1 Понедельник
2 Вторник
Васечкин
1
2
3
4
5
6
6
1
0
0
3 Среда
4 Четверг
5 Пятница
6 Суббота
7 Воскресенье
Дни недели
Количество пропущенных
учеником уроков

39.

Пример прямоугольной таблицы
1
2
3
4
5
1
Васечкин
6
6
1
0
0
2
Ионов
0
0
0
0
6
3
Радугина
0
0
1
0
0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0
0
0
0
0
19 Чабанюк
Количество уроков, пропущенных учениками класса

40.

Самое главное
Величина в информатике – это отдельный информационный
объект (число, символ, строка, таблица и др.).
Величины делятся на:
постоянные - значения указываются в тексте алгоритма и не
меняются в процессе его исполнения
переменные - значения меняются в процессе исполнения
алгоритма.
Тип величины: целый, вещественный, логический, символьный и
литерный.
Для ссылок на величины используют их имена (идентификаторы).
Имя величины может состоять из одной или нескольких латинских
букв, из латинских букв и цифр.
Таблица (массив) - набор некоторого числа однотипных элементов,
которым присвоено одно имя. Положение элемента в таблице
однозначно определяется его индексами.

41.

Опорный конспект
Величина в информатике – это отдельный информационный
объект (число, символ, строка, таблица и др.).
Величина
Постоянная
Переменная
Тип величины
Числовой
Целый
Логический
Вещественный
Текстовый
Символьный
Литерный

42.

Опорный конспект
Выражения
Арифметические
Строковые
Логические
Команда присваивания
<имя переменной>:= <выражение>

43.

Опорный конспект
Таблица
Линейная
Одномерный
массив
Прямоугольная
Двумерный
массив

44.

Основные алгоритмические конструкции
Для записи любого алгоритма достаточно трёх основных
алгоритмических конструкций:
следования,
ветвления,
Повторения.
(Э. Дейкстра)
Эдсгер Вибе Дейкстра (1930–2002).
Выдающийся нидерландский учёный,
идеи которого оказали огромное
влияние на развитие компьютерной
индустрии.

45.

Следование
Следование - алгоритмическая конструкция, отображающая
естественный, последовательный порядок действий.
Алгоритмы, в которых используется только структура
«следование», называются линейными алгоритмами.
Действие 1
Действие 2
Алгоритмическая структура «следование»

46.

Линейный алгоритм
приготовления отвара шиповника
Начало
Столовую ложку сушёных плодов
шиповника измельчить в ступке
Залить стаканом кипячёной воды
Кипятить 10 минут на слабом огне
Охладить
Процедить
Конец

47.

Вычисления по алгоритму
Алгоритм
х:=2
у:=х*х
у:=у*у
х:=у*х
s:=x+y
Шаг
алгоритм
а
Переменные
x
y
s
1
2
-
-
2
2
4
3
2
16
-
4
32
16
-
5
32
16
48
Ответ: s = 48

48.

Целочисленная арифметика
С помощью операции div вычисляется целое частное, с
помощью операции mod - остаток.
7 : 3 = 2 (ост.1)
7 div 3 = 2
7 mod 3 = 1
8 : 3 = 2 (ост.2)
8 div 3 = 2
8 mod 3 = 2
10: 3 = 3 (ост.1)
10 div 3 = 3
10 mod 3 = 1
13 : 4 = 3 (ост.1)
13 div 4 = 3
13 mod 4 = 1
11 : 4 = 2 (ост.3)
11 div 4 = 2
11 mod 4 = 3
8 : 3 = 2 (ост.2)
8 div 3 = 2
8 mod 3 = 2

49.

Алгоритм работы кассира
Алгоритм работы кассира, выдающего покупателю сдачу
(s) наименьшим количеством банкнот по 500 (k500), 100
(k100), 50 (k50) и 10 (k10) рублей.
k500:=s div 500
s:=s mod 500
k100:=s div 100
s:=s mod 100
k50:=s div 50
s:=s mod 50
k10:=s div 10
Линейный алгоритм

50.

Самое главное
Для записи любого алгоритма достаточно трёх
основных алгоритмических конструкций (структур):
следования, ветвления, повторения.
Следование
алгоритмическая
конструкция,
отображающая
естественный,
последовательный
порядок действий.
Алгоритмы, в которых используется только структура
«следование», называются линейными.

51.

Опорный конспект
Следование
алгоритмическая
конструкция,
отображающая естественный, последовательный порядок
действий.
Алгоритмы, в которых используется только структура
«следование», называются линейными.
Действие 1
Действие 2

52.

Ветвление
Ветвление - алгоритмическая конструкция, в которой в
зависимости от результата проверки условия («да» или «нет»)
предусмотрен выбор одной из двух последовательностей
действий (ветвей).
Алгоритмы,
в
основе
которых
лежит
структура
«ветвление», называют разветвляющимися.

53.

Полная форма ветвления
если <условие>
то <действия 1>
иначе <действия 2>
все
Условие
Действие 1
Пример
алг правописание частиц НЕ, НИ
нач
если частица под ударением
то писать НЕ
иначе писать НИ
все
кон
Действие 2

54.

Сокращённая форма ветвления
если <условие>
то <действия 1>
все
Условие
Действие 1
Пример:
алг сборы на прогулку
нач
если на улице дождь
то взять зонтик
все
кон

55.

Операции сравнения
A<B
A <= B
А меньше В
А меньше или равно В
A=B
А равно В
A>B
А больше В
A >= B
А больше или равно В
A <> B
А не равно В

56.

Вычисление функции f(x)=|x|
Начало
Список данных
X, Y -вещ
Х
да
Х>0
Y:=X
нет
Y:=-X
Y
Конец

57.

Простые и составные условия
Простые условия состоят из одной операции сравнения.
Составные условия получаются из простых с помощью
логических связок and (и), or (или), not (не).
Пример. Алгоритм определения принадлежности точки Х
отрезку [A; B].
A, B, X
да
(X>=A) and (X<=B)
ДА
нет
НЕТ
Ответ:
Ответ:Не
Принадлежит
принадлежит
A=2
X=4
B=4
B=6
X=6

58.

Наибольшая из 3-х величин
Переменной Y присваивается значение большей из трёх
величин A, B и C.
YC
B= =
Y
>Y
AB
Шаг
Y:=A
да
B>Y
нет
Y:=B
1
Константы
А
В
С
10
30
20
Переменная
Y
10
2
да
Y:=C
C>Y
30 > 10 (Да)
нет
3
Условие
30
4
20 > 30 (Нет)
Ответ: Y = 30

59.

Решение линейного уравнения ax + b = 0
Список данных
a, b, x - вещ
a, b
да
x:=-b/a
нет
a<>0
да
Корней нет
b<>0
нет
Любое число

60.

Разветвляющийся алгоритм для Робота
В какую клетку переместится Робот после выполнения
следующего фрагмента алгоритма.
если справа свободно
или снизу свободно
то закрасить
все
если справа стена
то влево
все
если
слева стена
то вправо
все
б а

61.

Самое главное
Для записи любого алгоритма достаточно трёх
основных алгоритмических конструкций (структур):
следования, ветвления, повторения.
Ветвление - алгоритмическая конструкция, в которой
в зависимости от результата проверки условия (да или
нет)
предусмотрен
выбор
одной
из
двух
последовательностей действий (ветвей).
Алгоритмы, в основе которых лежит структура
«ветвление», называют разветвляющимися.

62.

Опорный конспект
Ветвление - алгоритмическая конструкция, в которой в
зависимости от результата проверки условия (да или нет)
предусмотрен выбор одной из двух последовательностей действий
(ветвей).
Алгоритмы, в основе которых лежит структура «ветвление»,
называют разветвляющимися.
Условие
Действие 1
Действие 2
Полная форма ветвления
Условие
Действие 1
Сокращённая форма ветвления

63.

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

64.

Типы циклов
Могут быть
Заданы условия
продолжения работы
Заданы условия
окончания работы
Пока есть кирпич
Задано число
повторений
Ровно 100 кирпичей
Пока не наступит
ночь

65.

Цикл с заданным условием продолжения
работы
(цикл-ПОКА, цикл с предусловием)
нц пока <условие>
<тело цикла
(последовательность
действий)>
кц
нет
Условие
да
Тело цикла

66.

Погрузка кирпичей
алг погрузка
нач
нц пока есть
кирпичи
взять один
кирпич
если кирпич
целый
то положить
кирпич в машину
иначе отложить
кирпич в сторону
все
кц
кон

67.

Робот в коридоре
Правее Робота расположен коридор неизвестной длины.
Необходимо, чтобы Робот закрасил все клетки этого
коридора.
нц пока справа
свободно
вправо
закрась
кц

68.

Частное и остаток
Начало
Список данных
x, y, r, q - цел
x, y
r:=x
q:=0
r >=y
да
r:= r - y
q:= q +1
r, y
Конец
нет

69.

Таблица значений переменных
Шаг
алгоритма
Операция
Переменная
x
y
r
q
1
Ввод x
17
2
Ввод
17
5
3
r := x
17
5
17
4
q := 0
17
5
17
5
r >=y
6
r := r – y
17
5
12
0
7
q := q +1
17
5
12
1
8
r >=y
9
r := r – y
17
5
7
1
10
q := q +1
17
5
7
2
11
r >=y
12
r := r – y
17
5
2
2
13
q := q +1
17
5
2
3
17
r >=y
18
Вывод r
19
Вывод q
y
Условие
r >= y
0
17 > 5 (Да)
12 > 5 (Да)
7 > 5 (Да)
2 > 5 (Нет)
2
3

70.

Цикл с заданным условием окончания работы
(цикл-ДО, цикл с постусловием)
Тело цикла
Условие
да
нет
Запись на алгоритмическом языке:
нц
<тело_цикла
(последовательность действий)>
кц при <условие>

71.

Цикл с постусловием
Пример. Алгоритм по выучиванию наизусть четверостишия.
алг четверостишие
нач
нц
прочитать четверостишие
по книге 1 раз
рассказать
четверостишие
кц при не сделал ошибку
кон

72.

Вычисление переменной b
Начало
Список данных
a, b - цел
a := 1
b := 1
a := a *2
b := b +a
a=8
да
b
нет
Конец

73.

Таблица значений переменных
Шаг
алгоритма
Операция
Переменные
1
a := 1
1
2
b := 1
1
1
3
a := a * 2
2
1
4
b := b+a
2
3
5
a=8
6
a := a * 2
4
3
7
b := b+a
4
7
8
a=8
9
a := a * 2
8
7
10
b := b+a
8
15
11
a=8
a
Условие
b
a=8
2 = 8 (Нет)
4 = 8 (Нет)
8 = 8 (Да)

74.

Задача о тренировках
Начало
В 1-й день - пробежать 10 км;
каждый
следующий
день
увеличивать на 10% от нормы
предыдущего дня. Как только
достигнет или превысит 25 км,
необходимо
прекратить
увеличение и пробегать 25 км.
Начиная
с
какого
дня
спортсмен будет пробегать 25
км?
Пусть
x — количество
километров, которое спортсмен
пробежит в некоторый i-й день.
Тогда в следующий (i + 1)-й
день он пробежит x + 0,1x
километров (0,1x — это 10% от
x).
Список данных
i – цел
x- вещ
i := 1
x := 10
i := i +1
x := x +0,1x
x>= 25
да
i
нет
Конец

75.

Цикл с заданным числом повторений
(цикл-ДЛЯ, цикл с параметром)
i = i1, i2
Тело цикла
Запись на алгоритмическом языке:
нц для i от i1 до i2
<тело_цикла
(последовательность действий)>
кц

76.

Цикл с заданным числом
повторений
алг переправа
нач
нц для i от 1 до 5
два мальчика
переправляются на
противоположный берег
один мальчик
высаживается на берег, другой
плывёт обратно
солдат переправляется
через реку
мальчик возвращается на

77.

Вычисление степени
Начало
Список данных
i, n – цел
a, y- вещ
a, n
y := 1
i = 1, n
y := y * a
y
Конец

78.

Таблица значений переменных
Шаг
алгоритма
Операция
Переменная
a
n
y
Условие
i
1
Ввод a, n
4
3
2
y := 1
4
3
1
3
i := 1
4
3
1
4
i <= n
5
y := y * a
4
3
4
1
6
i := i + 1
4
3
4
2
7
i <= n
8
y := y * a
4
3
16
2
9
i := i + 1
4
3
16
3
10
i <= n
11
y := y * a
4
3
64
3
12
i := i + 1
4
3
64
4
13
i <= n
i <= n
1
1 <= 3 (Да)
2 <= 3 (Да)
3 <= 3 (Да)
4 <= 3 (Нет)

79.

Повторение
Пример. Для исполнителя Робот цикл с известным числом
повторений реализуется с помощью следующей конструкции:
нц <число повторений> раз
<тело цикла>
кц
Так, если правее Робота не встретится препятствий, то,
выполнив приведённый ниже алгоритм, он переместится на
пять клеток вправо и закрасит эти клетки:
алг
нач
нц 5 раз
вправо; закрасить
кц
кон

80.

Повторение
Пример. В населённом пункте N домов. Известно количество людей,
проживающих в каждом из домов. Составим алгоритм подсчёта
жителей населённого пункта.
Исходные данные
(количество жильцов)
представим с помощью
линейной таблицы А,
содержащей N элементов:
A[1] — количество жильцов
дома 1, …, A[N]—количество
жильцов дома N.
В общем случае А[i] –
количество жильцов дома i,
где i принимает все значения
от 1 до n (i =1,n).
Результат работы алгоритма
обозначим через s.
Начало
n, a[i] = 1, n
s:= 0
i = 1, n
s := s + a[i]
s
Конец

81.

Самое главное
Для записи любого алгоритма достаточно трёх основных
алгоритмических конструкций (структур): следования, ветвления,
повторения.
Повторение - алгоритмическая конструкция, представляющая
собой последовательность действий, выполняемых многократно.
Алгоритмы, содержащие конструкцию «повторение», называют
циклическими или циклами.
Последовательность действий, многократно повторяющаяся в
процессе выполнения цикла, называется телом цикла.
В зависимости от способа организации повторений различают три
типа циклов:
1) цикл с заданным условием продолжения работы;
2) цикл с заданным условием окончания работы;
3) цикл с заданным числом повторений.

82.

Опорный конспект
Повторение - алгоритмическая конструкция, представляющая
собой последовательность действий, выполняемых многократно.
Алгоритмы, содержащие конструкцию «повторение», называют
циклическими или циклами.
Последовательность действий, многократно повторяющаяся в
процессе выполнения цикла, называется телом цикла.
Тип цикла
С заданным
условием
продолжения
работы
С заданным
условием
окончания
работы
С заданным
числом
повторений
Цикл - ПОКА
Цикл - ДО
Цикл - ДЛЯ

83.

Последовательное построение
алгоритма
Начало
Исходные
данные
Постановка
задачи
Результат
Конец
Я совершенный
исполнитель: всё знаю и
всё умею!

84.

Последовательное построение
алгоритма
Не могу решить
поставленную задачу!?
Упрощение команд
постановки задачи
Задача разбивается на более простые части
Решение каждой части задачи формулируется
в отдельной команде (предписании)
Предписания, выходящие за пределы
возможностей исполнителя, представляют
в виде более простых команд

85.

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

86.

Укрупнённый план действий Робота
Начало
1. Закраска всех клеток коридора левее исходной
2. Возвращение в исходное положение
3. Закраска всех клеток коридора правее исходной
4. Возвращение в исходное положение
5. Закраска исходной клетки
Конец

87.

Детализация плана действий Робота
1. Закраска всех клеток коридора, находящихся левее Робота:
влево
нц пока сверху стена и
снизу стена
закрасить; влево
кц
Положение Робота после выполнения этого алгоритма:

88.

Детализация плана действий Робота
2. Возвращение Робота в коридор в исходную точку:
вправо
нц пока клетка
закрашена
вправо
кц
Положение Робота после выполнения этого алгоритма:

89.

Детализация плана действий Робота
3. Закраска всех клеток коридора, находящихся правее
Робота:
вправо
нц пока сверху стена и
снизу стена
закрасить; вправо
кц
Положение Робота после выполнения этого алгоритма:

90.

Детализация плана действий Робота
4.Возвращение Робота в коридор в исходную точку:
влево
нц пока клетка
закрашена
влево
кц
5. По команде
исходную точку.
закрасить
Робот
закрашивает

91.

Программа для Робота
алг
нач
влево
нц пока сверху стена и
снизу стена
закрасить; влево
кц
вправо
нц пока клетка
закрашена
вправо
кц
вправо
нц пока сверху стена и
снизу стена
закрасить; вправо
кц
влево
нц пока клетка
закрашена
влево

92.

Вспомогательный алгоритм
Вспомогательный алгоритм - алгоритм,
используемый в составе другого алгоритма.
целиком
Блок «предопределённый процесс»
Вспомогательный алгоритм делает структуру алгоритма
более простой и понятной.

93.

Алгоритм вычисления степени
y = ax, где x - целое число, a 0.
По определению степени с целым показателем:
a 0 1, a 0;
a n 1 / a n , a 0, n N
1
1
a x a
1 при x = 0
ax xпри x >0,
x
y=
1
a при x <0.
Обозначим алгоритм возведения числа в степень st(a, n, y).
Это вспомогательный алгоритм.

94.

Блок-схема решения задачи:
Начало
a, x
да
y := 1
нет
x=0
да
st (a, x, y)
y
Конец
x>0
нет
st (1/a, x, y)

95.

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

96.

Схема вызова вспомогательного
алгоритма
Основной алгоритм
Имя вспомогательного
алгоритма (список
фактических параметров)
…
Вспомогательный алгоритм
Формальные аргументы
Формальные аргументы
…

97.

Рекурсивный алгоритм
Алгоритм, в котором прямо или косвенно содержится ссылка на него
же как на вспомогательный алгоритм, называют рекурсивным.
Начало
Пример. Алгоритм вычисления
степени с натуральным
показателем n для любого
вещественного числа а,
представленный в виде
рекурсивного алгоритма
a, n
st (a, n-1,y)
y :=a*y
y
Конец

98.

Снежинка Коха
Пример.
Рассмотрим
алгоритм
построения
геометрической фигуры, которая называется снежинкой
Коха. Шаг процедуры построения состоит в замене средней
трети каждого из имеющихся отрезков двумя новыми той же
длины.
Начальное
Первый
Второй
Третийположение
шаг
шаг
шаг
С каждым шагом фигура становится всё причудливее.
Граница снежинки Коха - положение кривой после
выполнения бесконечного числа шагов.

99.

Самое главное
Метод последовательного построения алгоритма:
• исходная задача разбивается на несколько частей, каждая
из которых проще всей задачи, и решение каждой части
формулируется в отдельной команде;
• если получаются команды, выходящие за пределы
возможностей исполнителя, то они представляются в виде
совокупности ещё более простых предписаний;
• процесс продолжается до тех пор, пока все предписания не
будут понятны исполнителю.
Вспомогательный алгоритм - алгоритм, целиком
используемый в составе другого алгоритма.
Алгоритм, в котором прямо или косвенно содержится ссылка
на него же как на вспомогательный алгоритм, называют
рекурсивным.

100.

Опорный конспект
Метод последовательного построения алгоритма один из основных методов конструирования алгоритмов.
Упрощение команд
постановки задачи
Задачу разбивают на более простые
Решение каждой части задачи формулируют
в отдельной команде
Предписания, выходящие за пределы возможностей
исполнителя, представляют в виде более простых команд
Вспомогательный алгоритм - алгоритм, целиком
используемый в составе другого алгоритма.

101.

Управление
Управление
это
процесс
целенаправленного
воздействия на объект; осуществляется для организации
функционирования объекта по заданной программе.
Норберт Винер (1894—1964),
основоположник кибернетики
- науки об управлении.

102.

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

103.

Информация и управление
Информация для
управляющего объекта
Цель действий
Способы
достижения цели
Пример. Управление движением
автомашин (объект управления) на
перекрёстке с помощью светофора
(управляющий объект).
Управляющее воздействие зависит от
заложенной в управляющем объекте
исходной информации.

104.

Обратная связь
Обратная связь - это процесс передачи информации о
состоянии объекта управления в управляющую систему.
Обратная
связь
позволяет
корректировать
управляющие
воздействия управляющей системы
на
объект
управления
в
зависимости от состояния объекта
управления.
Кибернетическая модель управления
Управляющий объект
Управляющее
воздействие
Обратная связь
Объект управления

105.

Самое главное
Управление
воздействия
процесс
на
объект;
целенаправленного
осуществляется
для
организации функционирования объекта по заданной
программе.
Последовательность
команд
по
управлению
объектом, приводящая к заранее поставленной цели,
называется алгоритмом управления.

106.

Опорный конспект
Управление - это процесс целенаправленного воздействия на
объект; осуществляется для организации функционирования
объекта по заданной программе.
Информация для
управляющего объекта
Цель действий
Способы
достижения цели
Последовательность команд по управлению объектом,
приводящая к заранее поставленной цели, называется
алгоритмом управления.
Обратная связь - это процесс передачи информации о
состоянии объекта управления в управляющую систему.