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

Понятие алгоритма

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

​

Аль-Хорезми́

• Слово алгоритм произошло�от латинского написания�имени одного из крупней-�ших учёных IX века, матема-�тика, астронома, географа�и историка аль-Хорезмú, который сфор-мулировал правила вычислений (сложения и вычитания чисел) в позиционной десятичной системе счисления.

Понятие алгоритма

• Алгоритм — это последовательность действий (шагов), приводящих к конечному результату.
• Исполнитель — это объект, способный выполнять опре-�деленный набор команд.

СКИ

• Команда — это указание исполнителю выполнить действие.
• СКИ (система команд�исполнителя) — это команды, которые понимает и может выполнять конкретный исполнитель. 

Исполнитель Перевозчик

• Как перевезти�через реку волка,�козу и капусту?
• В лодке может поместиться, кроме перевозчика, только или волк, или коза, или капуста. Если оставить без присмотра волка с козой, то волк съест козу; если козу с капустой — коза съест капусту.

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

1. Дискретность — алгоритм состоит из отдельных команд.
2. Понятность — алгоритм содержит только команды, входящие в СКИ.
3. Определённость (точность) — каждая команда однозначно определяет действие исполнителя.

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

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

​

Исполнитель Вычислитель

• Задача 1. Система команд исполнителя Вычислитель:�1 — прибавить 1;�2 — умножить на 2.
• Число 1 преобразовано по алгоритму 12211. Какое число получили?
• Запишите алгоритм получения числа 47 из числа 5.

Исполнитель Вычислитель

• Задача 2. Система команд исполнителя Вычислитель:�1 — вычти 1;�2 — умножь на 3.
• Число 1 преобразовано по алгоритму 21212. Какое число получили?
• Запишите алгоритм получения числа 16 из числа 3, содержащий не более �5 команд.

Исполнитель Цепочка

• Задача 3. Некоторый алгоритм из одной цепочки символов получает новую цепочку следующим образом:
• Сначала вычисляется длина исходной цепочки символов, если она чётна, то в начало цепочки символов добавляется символ А, а если нечётна, то последний символ цепочки удаляется.
• В полученной цепочке символов каждая буква заменяется буквой, следую-щей за ней в русском алфавите (А — на Б, Б — на В и т. д., а Я — на А). Получившаяся цепочка является результатом работы алгоритма.
• Например, если исходной была цепочка СОН, то результатом работы алгоритма будет цепочка ТП, а если исходной была цепочка УМ, то результатом работы алгоритма будет цепочка БФН.
• Дана цепочка символов ЛУВР. Какая цепочка символов получится, если к данной цепочке применить описанный алгоритм дважды (т. е. применить алгоритм к данной цепочке, а затем к результату вновь применить алгоритм)?
• Русский алфавит: АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ.

Исполнитель Автомат

• Задача 4. Автомат получает на вход четырехзначное десятичное число. По полученному числу строится новое десятичное число по следующим правилам:
• Вычисляются два числа — сумма первой и второй цифр и сумма третьей и четвёртой цифр заданного числа.
• Полученные два числа записываются друг за другом в порядке невозрастания (без разделителей).
• Пример. Исходное число: 2177. Поразрядные суммы: 3 и 14. Результат: 143.
• Определите, сколько из приведённых ниже чисел могут получиться в результате работы автомата.

1915 10 110 1516 1211 316 1519 116 1515