Страница 75 - гдз по информатике 11 класс учебник Босова, Босова

1. Перечислите основные свойства алгоритмов и проиллюстрируйте их примерами.

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

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

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

Понятность. Алгоритм не должен содержать предписаний, смысл которых может восприниматься исполнителем неоднозначно, т. е. запись алгоритма должна быть настолько чёткой и полной, чтобы у исполнителя не возникло потребности в принятии каких-либо самостоятельных решений. Стоит помнить, что алгоритм всегда рассчитан на выполнение «неразмышляющим» исполнителем.

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

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

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

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

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

Проведём окружность с центром в точке А таким радиусом, чтобы она пересекла прямую а в двух точках. Назовём их В и С.

С центром в точке В проведем окружность радиусом больше половины длины отрезка ВС.

C центром в точке С этим же радиусом проведём окружность. Получим точку D.

Через точки А и D проведём прямую. Она будет являться перпендикуляром к прямой а.

4. Есть двое песочных часов: на 3 и на 8 минут. Для приготовления эликсира бессмертия его надо варить ровно 7 минут. Как это сделать?

Придумайте систему команд исполнителя Колдун. Запишите с их помощью план действий исполнителя по приготовлению эликсира.

Опрокидываем одновременно песочные часы на 3 и на 8 минут. 3-минутные часы будем запускать 5 раз, т. е. отсчитаем ими 15 минут. Варить эликсир начнем сразу же после остановки 8-минутных часов (15 — 8 = 7).

5. Исполнитель Вычислитель получает на вход целое число х и может выполнять с ним преобразования по алгоритму, состоящему из любого количества команд: 1) прибавить 5; 2) вычесть 2.

Сколько разных алгоритмов, состоящих из пяти команд, можно составить для этого исполнителя? Сколько из них будут приводить к одинаковым результатам для заданного числа x?

32 алгоритма. К одинаковому результату будут приводить 26 алгоритмов.

Алгоритмы с разными выходными данными:

1) x + 5 * 5 + 2 * 0 = x + 25

2) x + 5 * 4 — 2 * 1 = x + 18

3) x + 5 * 3 — 2 * 2 = x + 11

4) x + 5 * 2 — 2 * 3 = x + 4

5) x + 5 * 1 — 2 * 4 = x — 3

6) x + 5 * 0 — 2 * 5 = x — 10

Всего разных алгоритмов: 2⁵ = 32.

Всего алгоритмов с разными выходными данными: 6.

Значит, к одинаковым результатам будут приводить: 32-6=26 алгоритмов.

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

Например, исполнить производящих арифметические операции не сможет найти косинус числа.

7. Перечислите известные вам способы записи алгоритмов.

Словесный, графический, программный.

8. Приведите примеры задач и оптимальных способов записи алгоритмов их решения.

Алгоритм по игре в крестики-нолики, алгоритм разогревания супа.

9. Исполнитель Автомат получает на вход четырёхзначное число. Это число он преобразует по следующему алгоритму:

1) вычисляется сумма первой и второй цифр числа;

2) вычисляется сумма второй и третьей цифр числа;

3) вычисляется сумма третьей и четвёртой цифр числа;

4) из полученных трёх чисел (сумм) выбирается и отбрасывается одно — не превышающее двух других чисел;

5) оставшиеся два числа записываются друг за другом в порядке неубывания без разделителей.

Так, если исходное число 9575, то, преобразуя его, автомат создаст суммы: 9 + 5 = 14, 5 + 7 = 12, 7 + 5 = 12. Сумма, не превышающая двух других, 12. Оставшиеся суммы: 14, 12. Результат: 1214.

Опишите систему команд этого исполнителя.

Могут ли результатом работы этого исполнителя быть числа 1610, 1010, 1019?

Укажите минимальное и максимальное значения результата работы этого исполнителя.

При обработке некоторого числа х автомат выдаёт результат 1418. Укажите наименьшее и наибольшее значения х, при которых возможен такой результат.

Система команд данного исполнителя:

1) Сложить 1 и 2 цифру

2) Сложить 2 и 3 цифру

3) Сложить 3 и 4 цифру

4) Найти минимум из этих полученных сумм

5) Отсортировать оставшийся (исходя из 4 пункта) 2 суммы в порядке возрастания.

Ответ на вопрос: Могут ли результатом работы этого исполнителя быть чиста 1610, 1010, 1019?

1610 — нет (потому что 2 числа должны идти в порядке возрастания, а 610 в сумме двух чисел мы получить не сможем)

1010 — возможно. Если число будет 5555.

1019 — нет (потому что мы не можем получить в сумме 2 чисел 19 (максимум 18))

Минимальное число, которое можно получить после обработки данным алгоритмом: 1818 (9999 число до алгоритма)

Минимальное: 01 (1000 число до алгоритма)

Число после алгоритма 1418:

Минимальное число: 1599 (1->6,2->14,3->18,4->6,5->1418)

Максимальное число: 9959 (1->18,2->14,3->14,4->14,5->1418)