Презентация на тему Примеры алгоритмов

заданные числа
Разделить сумму на 2
Вычислительный алгоритм
Среднее арифметическое двух чисел

техническое устройство), способный выполнять определённый набор команд.
Формальный
Неформальный
Исполнитель
Круг

Среда исполнителя

Режимы работы

Непосредственное управление

Программное управление

Область, обстановка, условия

Исполнители алгоритмов

СКИ

отношений
и действий с объектами
Определение исходных
данных и результата
Определение
последовательности
действий

Запись
последовательности
действий с помощью
команд СКИ

Алгоритм – модель деятельности исполнителя алгоритмов

Разработка алгоритма

состоит из
команд, входящих в СКИ
Команды понимаются
однозначно
Обеспечивается получение
ожидаемого

Обеспечивается решение
задач с различными исходными
данными

Дискретность

Понятность

Определённость

Результативность

Массовость

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

да

нет

Начало

Конец

x, y

a

x > y

a = x

a = y

входящих в систему команд исполнителя, т. е. из таких

Окрошка «Мясная»

1-1.5 л кваса
500 г картофеля
300 г колбасы
3 яйца
200 г редиса

300 г огурцов
зелень по вкусу
сметана
соль
перец

Картофель отварить до готовности.
Остудить, почистить. Нарезать кубиками.
Колбасу нарезать кубиками.
Яйца нарезать кубиками.
Редис тонко нарезать.
Огурцы нарезать кубиками.

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

Рецепт приготовления

которых может быть истолкован исполнителем неоднозначно; недопустимы ситуации, когда

Доехать до стадиона

Идти прямо

Алгоритм не уточняет, какое расстояние нужно пройти прямо.

В какую сторону повернуть.

В какой автобус сесть.

Повернуть

Идти прямо

Сесть в автобус

Доехать до остановки «Стадион»

результата после конечного, возможно, очень большого, числа шагов. При

Данная последовательность команд не соответствует свойству результативности. Что нужно изменить?

Взять книгу
Открыть первую страницу
Пока не конец книги выполнять следующие действия:
3.1 Прочитать текст
3.2 Перелистнуть страницу

Чтение книги

3.3 Прочитать текст
3.4 Открыть первую страницу

применения для решения любой задачи из некоторого класса задач

Алгоритм вычисления корней квадратного уравнения.

Конец

да

нет

Начало

Ввод
коэффициентов

Вычислить
дискриминант

Дискриминант
меньше 0?

Вычислить
значения корней

«Корней нет»

Вывод корней

она удовлетворяет свойствам:
дискретности - процесс нахождения простых чисел разбит

Решето Эратосфена

последовательности действий, приводящих от исходных данных к требуемому результату,

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

Процесс решения задачи представляется
в виде последовательности операций

Создается машина, способная выполнять
эти операции в указанной последовательности

Человек освобождается от рутинной работы,
выполнение которой поручается автомату

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

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

Автоматизация производства

устройство), способный выполнять определённый набор команд.
Формальный исполнитель одну и

Алгоритм - это предназначенное для конкретного исполнителя описание последовательности

предписания двух видов:
1) функциональные операторы - предписания, направленные на

рисунков
Структурограмма
Школьный алгоритмический
язык
Язык программирова-ния
Блок-схема

в виде набора высказываний на обычном разговорном языке.
Пример. Словесное

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

математические выражения и формулы.
Каждое предписание записывается с новой строки
Правила

Предписание (шаги) алгоритма нумеруются

Исполнение алгоритма происходит в порядке
возрастания номеров шагов, начиная с первого,
если нет особых указаний

Обозначить первое из заданных чисел Х, второе - Y.
3.

геометрических фигур, а последовательность выполнения шагов указывается с помощью

Блок начала или конца алгоритма

Блок ввода или вывода данных

Блок обработки данных

Блок проверки условия

Блок пояснительных записей

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

Система правил, определяющих
смысл и способ употребления
конструкций языка

Синтаксис

Семантика

Алфавит

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

смысл и
способ записи

в информатике – это отдельный информационный объект.

Постоянная
Переменная
Величина

Число

Символ

Строка

Таблица

Информационный объект

(больше)
= (не меньше)
= (равно)
И (конъюнкция)
ИЛИ (дизъюнкция)
НЕ

Операнды - объекты, над которыми выполняют операции.

Операции над величинами

символ
Строка
символов
Текстовый
ДА (ИСТИНА, TRUE, 1)
НЕТ (ЛОЖЬ, FALSE, 0)
Логический

Литерная

Типы величин

и цифра
Мнемоническое
имя
A1, B4, M2
SUMMA, PLAN
Имя величины

с помощью одного или нескольких операндов.
Логические
Арифметические
Строковые
Выражения

Операция
сцепления (+).
А=`том`
`a`+А=

X>5
X<10
X<=3

присвоено значение, она
остаётся неопределённой

Значение, присвоенное переменной, сохраняется
до следующего

Если переменной присваивается новое значение,
то предыдущее её значение теряется

литерного типа обменяются своими значениями.
Верно
Неверно
Решение
А:=В
В:=А
алг обмен

Алгоритм обмена значений переменных

!

✔

2, а волка - из клетки 2 - в

Аналогия с перемещением

1

2

3

Нужна клетка 3.

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


Дни недели
Табель
успеваемости

объект (число, символ, строка, таблица и др.).
Величины делятся на:

объект (число, символ, строка, таблица и др.).
Переменная
Постоянная
Величина

Целый

Вещественный

Символьный

Литерный

Текстовый

Числовой

Логический

Тип величины

основных алгоритмических конструкций:
следования,
ветвления,
Повторения.
(Э. Дейкстра)
Эдсгер Вибе Дейкстра

порядок действий.
Алгоритмы, в которых используется только структура «следование»,

Действие 1

Действие 2

Алгоритмическая структура «следование»

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

помощью операции mod - остаток.
Целочисленная арифметика
13 : 4 =

8 : 3 = 2 (ост.2)

7 : 3 = 2 (ост.1)

8 : 3 = 2 (ост.2)

11 : 4 = 2 (ост.3)

10: 3 = 3 (ост.1)

13 div 4 = 3

8 div 3 = 2

7 div 3 = 2

8 div 3 = 2

11 div 4 = 2

10 div 3 = 3

13 mod 4 = 1

8 mod 3 = 2

7 mod 3 = 1

8 mod 3 = 2

11 mod 4 = 3

10 mod 3 = 1

наименьшим количеством банкнот по 500 (k500), 100 (k100), 50

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

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

алгоритмических конструкций (структур): следования, ветвления, повторения.
Следование - алгоритмическая конструкция,

порядок действий.
Алгоритмы, в которых используется только структура «следование»,

Действие 1

Действие 2

от результата проверки условия («да» или «нет») предусмотрен выбор

Алгоритмы, в основе которых лежит структура «ветвление», называют разветвляющимися.

иначе
все

сборы на прогулку
нач
если на улице дождь

операции сравнения. Составные условия получаются из простых с помощью

Пример. Алгоритм определения принадлежности точки Х отрезку [A; B].

Ответ: Принадлежит

A=2

X=4

B=6

Ответ: Не принадлежит

B=4

X=6

A
B >Y
C >Y
Y = B
Наибольшая из 3-х

Переменной Y присваивается значение большей из трёх величин A, B и C.

Ответ: Y = 30

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

б

если слева стена
то вправо
все

алгоритмических конструкций (структур): следования, ветвления, повторения.
Ветвление - алгоритмическая конструкция,

зависимости от результата проверки условия (да или нет) предусмотрен

Полная форма ветвления

Сокращённая форма ветвления

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

Пока есть кирпич
Ровно 100 кирпичей
Пока не наступит ночь

с предусловием)
нц пока

пока есть кирпичи
взять один кирпич

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

(Да)
7 > 5 (Да)
2 > 5 (Нет)

с постусловием)

Запись на алгоритмическом языке:
нц

алг четверостишие
нач
нц

(Нет)
8 = 8 (Да)
1
1
2
2
4
4
8
8
1
1
3
7
7
15
3

км; каждый следующий день увеличивать на 10% от нормы

параметром)

Запись на алгоритмическом языке:

нц для i

нц для i от 1 до 5

(Да)
3

повторений реализуется с помощью следующей конструкции:
нц

людей,
проживающих в каждом из домов. Составим алгоритм подсчёта
жителей населённого

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

алгоритмических конструкций (структур): следования, ветвления, повторения.
Повторение - алгоритмическая конструкция,

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

Тип цикла

Цикл - ПОКА

Цикл - ДО

Цикл - ДЛЯ

всё умею!

простые части
Решение каждой части задачи формулируется
в отдельной команде (предписании)
Предписания,

Не могу решить поставленную задачу!?

Робот находится в некоторой клетке горизонтального коридора. Ни одна

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

коридора левее исходной
2. Возвращение в исходное положение
3. Закраска всех

4. Возвращение в исходное положение

5. Закраска исходной клетки

Начало

Конец

плана действий Робота
влево
нц пока сверху стена и снизу стена

Положение Робота после выполнения этого алгоритма:

вправо
нц пока клетка закрашена
вправо
кц
Детализация плана действий Робота
Положение

пока сверху стена и снизу стена
закрасить; вправо
кц
Детализация

Положение Робота после выполнения этого алгоритма:

пока клетка закрашена
влево
кц
5. По команде закрасить Робот

Детализация плана действий Робота

и снизу стена
закрасить; влево
кц

Программа для Робота

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

- целое число, a 0.

Обозначим алгоритм возведения числа в степень st(a, n, y).
Это вспомогательный алгоритм.

По определению степени с целым показателем:

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

Формальные и фактические параметры

для любого вещественного числа а, представленный в виде рекурсивного

Рекурсивный алгоритм

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

называется снежинкой Коха. Шаг процедуры построения состоит в замене

С каждым шагом фигура становится всё причудливее. Граница снежинки Коха - положение кривой после выполнения бесконечного числа шагов.

Начальное положение

Первый шаг

Второй шаг

Третий шаг

на несколько частей, каждая из которых проще всей задачи,

основных методов конструирования алгоритмов.
Упрощение команд
постановки задачи
Задачу разбивают на более

Решение каждой части задачи формулируют
в отдельной команде

Предписания, выходящие за пределы возможностей
исполнителя, представляют в виде более простых команд

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

объект; осуществляется для организации функционирования объекта по заданной программе.
Норберт

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

Управление движением автомашин (объект управления) на перекрёстке с помощью

управляющей системы на объект управления в зависимости от состояния

Кибернетическая модель управления

Управляющий объект

Управляющее

воздействие

Обратная связь

Объект управления

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

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