Презентация на тему: "Презентация к уроку 8 класс. Алгоритмы и исполнители"

Алгоритмы и исполнители

Понятие алгоритма
Алгоритм – это описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов.

Мухаммед бен Муса ал-Хорезм
Появление алгоритмов связывают с зарождением математики. Более 1000 лет назад (в 825 году) ученый из города Хорезма Абдулла (или Абу Джафар) Мухаммед бен Муса аль-Хорезми создал книгу по математике, в которой описал способы выполнения арифметических действий над многозначными числами. Само слово «алгоритм» возникло в Европе после перевода на латынь книги этого математика.

Исполнитель алгоритма
Исполнитель алгоритма – объект, который выполняет алгоритм.
СКИ (система команд исполнителя) - совокупность команд, которые данный исполнитель умеет выполнить.
Каждый исполнитель может выполнять команды только из некоторого строго заданного списка.

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

Вы можете выполнить шаг только после выполнения предыдущего. Например, в алгоритме вычисления 8*3+2 (без скобок) вы сперва выполните умножение(по правилу), и только затем прибавите 2. Иначе ответ неверен.

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

Вы не можете разделить 8 на 3, если Вам ясно сказано: умножьте. Определенность - это четкое прописывание условия задачи.

Свойства алгоритма
3. Результативность (конечность) - процесс решения задачи должен прекратиться за конечное число шагов и при этом должен быть получен ответ задачи.



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

Свойства алгоритма
Пример 1. Дан угол. Необходимо провести биссектрису. (Есть способ, как, пользуясь линейкой и циркулем, можно решить эту задачу.)
Пример 2. Даны два целых числа. Необходимо найти их разность. (Имеется правило, в котором ясно изложен весь порядок действий с цифрами данных чисел.)
Правила вычитания формулируются для любых многоразрядных чисел, а не для каких-то конкретных двух. Инструкция проведения биссектрисы тоже такова, что, пользуясь ею, можно разделить пополам любой угол.


4. Массовость - один и тот же алгоритм применим для решения целого класса однотипных задач.

Свойства алгоритма
5. Понятность - алгоритм составляется в расчете на конкретного исполнителя, поэтому все команды должны быть понятны исполнителю.

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

Формы представления алгоритма:
естественный язык (словесная форма);
графическое изображение;
блок-схемы (графическое представление алгоритма);
учебный алгоритмический язык;
язык программирования.

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

Словесная форма

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

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

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

Таблица основных условных обозначений в блок-схемах

Блок-схема
Начало
Определить температуру воздуха
Температура ниже 0?
да
нет
Надеть шубу
Надеть куртку
Конец

Учебный
алгоритмический язык
Учебный алгоритмический язык – это псевдокоды, т.е. полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.

Запись
на алгоритмическом языке
Пример. Алгоритм нахождения максимального из двух неравных введенных чисел
Начало
Ввод числа х
Ввод числа у
Если х>у
То Вывод х
Иначе Вывод у
Все
Конец

Язык программирования
Пример. Определение четности введенного числа
На языке Pascal:

write (‘Введите целое число X’);
readln (x)
if X mod 2=0 then
writeln (‘число X четное’) else
writeln (‘число X не четное’)
end.

Решение задач
Практическая работа

Задание
1. Цепочка из трех бусин формируется по следующему правилу:
На первом месте в цепочке стоит одна из бусин А, Б, В. На втором – одна из бусин Б, В, Г. На третьем месте – одна из бусин А, В, Г, не стоящая в цепочке на первом или втором месте.
Какая из следующих цепочек создана по этому правилу:
1) АГБ2)ВАГ3) БГГ4) ББГ

Задание
3. У исполнителя Утроитель две команды, которым присвоены номера:
1. вычти 1
2. умножь на 3
Первая из них уменьшает число на экране на 1, вторая – увеличивает его в три раза. Запишите порядок команд в программе получения из числа 3 числа 16, содержащей не более 5 команд, указывая лишь номера команд.

Задание
(Например, программа 21211 это программа
умножь на 3
вычти 1
умножь на 3
вычти 1
вычти 1
которая преобразует число 1 в 4.)

Задание
5. Некоторый алгоритм из одной цепочки символов получает новую цепочку следующим образом. Сначала записывается исходная цепочка символов, после нее записывается исходная цепочка символов в обратном порядке, затем записывается буква, следующая в русском алфавите за той буквой, которая в исходной цепочке стояла на первом месте. Получившаяся цепочка является результатом работы алгоритма. Например, если исходная цепочка символов была ЛЕС, то результатом работы алгоритма будет цепочка ЛЕССЕЛМ.
Дана цепочка символов ГО. Какая цепочка символов получится, если к данной цепочке применить алгоритм дважды (то есть к данной цепочке применить алгоритм, а затем к результату его работы еще раз применить алгоритм)?

Задание
Чертёжнику был дан для исполнения следующий алгоритм:
Повтори 3 раз
Сместиться на (-2, -1) Сместиться на (3, 2) Сместиться на (2, 1)
Конец
Какую единственную команду надо выполнить Чертёжнику, чтобы вернуться в исходную точку, из которой он начал движение?
1) Сместиться на (9, 6)
2) Сместиться на (-6, -9)
3) Сместиться на (6, 9)
4) Сместиться на (-9, -6)

Задание
9. Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существуют две команды:
Вперед n (где n - целое число), вызывающая передвижение Черепашки на n шагов в направлении движения.
Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке.
Запись Повтори 5 [Команда1 Команда2] означает, что последовательность команд в скобках повторится 5 раз.

Черепашке был дан для исполнения следующий алгоритм:
Повтори 6 [Вперед 10 Направо 72]
Какая фигура появится на экране?
1) незамкнутая ломаная линия
2) квадрат
3) правильный пятиугольник
4) правильный шестиугольник

Задание
10. Автомат получает на вход трёхзначное десятичное число. По полученному числу строится новое десятичное число по следующим правилам:
1. Вычисляются два числа – сумма старшего и среднего разрядов, а также сумма среднего и младшего разрядов заданного числа.
2. Полученные два числа записываются друг за другом в порядке невозрастания (без разделителей).
Пример. Исходное число: 277. Поразрядные суммы: 9, 14. Результат: 149.
Определите, сколько из приведённых ниже чисел могут получиться в результате работы автомата:
1616 169 163 1916 1619 316 916 116
В ответе запишите только количество чисел.

Спасибо за внимание!