1 of 12

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

2 of 12

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

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

3 of 12

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

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

4 of 12

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

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

5 of 12

СКИ

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

6 of 12

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

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

7 of 12

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

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

8 of 12

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

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

9 of 12

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

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

10 of 12

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

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

11 of 12

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

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

12 of 12

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

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

1915 10 110 1516 1211 316 1519 116 1515