Домашнее задание
- Перечислите основные свойства алгоритмов и проиллюстрируйте их примерами.
- Почему кулинарный рецепт приготовления торта нельзя считать алгоритмом? Какими свойствами алгоритма он не обладает?
- Переформулируйте описание способа проведения перпендикуляра к прямой в заданной точке так, чтобы оно стало алгоритмом.
- Есть двое песочных часов: на 3 и на 8 минут. Для приготовления эликсира бессмертия его надо варить ровно 7 минут. Как это сделать?
Придумайте систему команд исполнителя Колдун. Запишите с их помощью план действий исполнителя по приготовлению эликсира.
- Исполнитель Вычислитель получает на вход целое число х и может выполнять с ним преобразования по алгоритму, состоящему из любого количества команд: 1) прибавить 5; 2) вычесть 2.
Сколько разных алгоритмов, состоящих из пяти команд, можно составить для этого исполнителя? Сколько из них будут приводить к одинаковым результатам для заданного числа х?
- Как известно, для каждого исполнителя набор допустимых действий всегда ограничен, иначе говоря, не может существовать исполнителя, для которого любое действие является допустимым. Докажите это утверждение, предположив, что такой исполнитель существует.
- Перечислите известные вам способы записи алгоритмов.
- Приведите примеры задач и оптимальных способов записи алгоритмов их решения.
- Исполнитель Автомат получает на вход четырёхзначное число. Это число он преобразует по следующему алгоритму:
1) вычисляется сумма первой и второй цифр числа;
2) вычисляется сумма второй и третьей цифр числа;
3) вычисляется сумма третьей и четвёртой цифр числа;
4) из полученных трёх чисел (сумм) выбирается и отбрасывается одно — не превышающее двух других чисел;
5) оставшиеся два числа записываются друг за другом в порядке неубывания без разделителей.
Так, если исходное число 9575, то, преобразуя его, автомат создаст суммы: 9 + 5 = 14, 5 + 7 = 12, 7 + 5 = 12. Сумма, не превышающая двух других, 12. Оставшиеся суммы: 14, 12. Результат: 1214.
Опишите систему команд этого исполнителя.
Могут ли результатом работы этого исполнителя быть числа 1610, 1010, 1019?
Укажите минимальное и максимальное значения результата работы этого исполнителя.
При обработке некоторого числа х автомат выдаёт результат 1418. Укажите наименьшее и наибольшее значения х, при которых возможен такой результат.
- В чём отличие шага алгоритма от команды алгоритма? Приведите пример.
- Что такое сложность алгоритма? От чего она зависит в наибольшей степени?
- Подсчитайте сложность алгоритма перемножения двух натуральных чисел «столбиком» при условии, что одно из них состоит из n, а второе — из m десятичных цифр.
- Какой алгоритм считается эффективным?
- Постройте эффективный алгоритм возведения числа х в степень n = 152.
