11 класс Информатика ГДЗ учебник Босова Параграф 5

1) Свойства алгоритма + примеры

Решение.

• Дискретность — выполнение по шагам. Пример: «прочитать число → прибавить 1 → вывести результат».
• Определённость (детерминированность) — каждый шаг сформулирован однозначно. Пример: «если x>0, то вывести 1, иначе 0» — нет двусмысленностей.
• Результативность (завершаемость) — за конечное число шагов получается ответ. Пример: «найти НОД(a,b) алгоритмом Евклида» — всегда заканчивается.
• Массовость (общность) — алгоритм подходит целому классу задач, а не одному значению. Пример: «сортировка выбором» для любого массива конечной длины.
• Эффективность (выполнимость) — каждый шаг реально выполним исполнителем. Пример: операции сложения/сравнения для калькулятора.

2) Почему рецепт торта — не алгоритм в строгом смысле?

Решение. В рецептах часто встречаются расплывчатые команды: «немного соли», «взбить до готовности», «выпекать до румяной корочки». Они не удовлетворяют свойству определённости. Кроме того, время/температура могут зависеть от условий и не обеспечивают гарантированного завершения за фиксированное число шагов для «исполнителя-робота».

3) Алгоритм построения перпендикуляра к прямой через заданную точку

Решение (шаги циркулем и линейкой).

1. Пусть дана прямая l и точка P вне/на прямой. Постройте окружность с центром P, которая пересечёт l в точках A и B.
2. Постройте окружности с центрами A и B одного и того же радиуса (> AB/2). Пусть они пересекутся в точках C и D.
3. Проведите прямую CD. Это перпендикуляр к l, проходящий через P (линия CD — серединный перпендикуляр к AB).

4) Песочные часы на 3 и 8 минут. Отмерить ровно 7 минут

Решение (чёткий план).

1. t=0: запустите часы на 3 и на 8 минут.
2. t=3: 3-минутные закончились — переверните их. (с этого момента можно начать приготовление)
3. t=6: 3-минутные снова закончились — переверните их (идёт новый трёхминутный цикл).
4. t=8: 8-минутные закончились. В 3-минутных осталось 1 минута до конца. Переверните 3-минутные — в них теперь будет 2 минуты песка сверху.
5. t=10: 3-минутные опорожнятся — прошло ровно 7 минут с момента t=3.

Итог: запустить приготовление в момент t=3 и остановить в t=10.

5) Исполнитель «Вычислитель»: команды +5 и −2. Сколько разных алгоритмов длины 5? Сколько из них дают одинаковый результат?

Решение.

• Любая последовательность из 5 команд («+5» или «−2») — это двоичное слово длины 5. Всего 2⁵=32 алгоритма.
• Пусть «+5» встречается k раз, а «−2» — 5−k. Итоговое изменение: Δ = 5k − 2(5−k) = 7k − 10. Следовательно, результат равен x + Δ и зависит только от k.
• Различных значений k шесть (0…5), значит разных результатов — 6. Число алгоритмов, дающих одинаковый результат, равно C(5, k):
  k=0:1; k=1:5; k=2:10; k=3:10; k=4:5; k=5:1.

6) Почему у каждого исполнителя набор допустимых действий ограничен?

Решение. Исполнитель характеризуется набором состояний и интерпретатором команд. Для корректной работы каждая команда должна быть определена (что делать, если не хватает данных, памяти, времени?). Если «разрешить всё», появятся команды, для которых поведение не определено или приводит к выходу из допустимых состояний. Следовательно, исполнитель «у которого допустимо всё» невозможен: нарушается свойство эффективности и определённости.

7) Известные способы записи алгоритмов

Решение. Текст на естественном языке (строгое пошаговое описание), блок-схема, псевдокод, таблицы переходов (для автоматов), диаграммы N-С (структурные схемы), программы на ЯП (Python/Java и т. п.).

8) Задачи и оптимальные способы записи

Решение.

• Простая одноходовая обработка данных (формула) — достаточно текстовой инструкции или псевдокода в одну строку.
• Ветвления и циклы малой глубины — лучше псевдокод (читабельнее, чем блок-схема).
• Обучающие демонстрации и контроль потоков — блок-схема помогает видеть структуру.
• Точные вычисления на компьютере — программный код (он исполним).

9) Исполнитель «Автомат» для четырёхзначного числа

Описание команд системы. Вход: число с четырьмя десятичными цифрами a b c d. Команды:

1. Вычислить суммы: s1=a+b, s2=b+c, s3=c+d.
2. Исключить одно число, которое не превышает двух других (то есть минимум из трёх; при равенстве минимумов — удалить любую из минимальных сумм).
3. Оставшиеся две суммы упорядочить по неубыванию и записать без разделителей (конкатенация).

Проверка примера 9575

Суммы: 9+5=14, 5+7=12, 7+5=12 → удаляем одну из «12», остаётся 12 и 14 → после упорядочивания и склейки получаем 1214.

Можно ли получить результаты 1610, 1010, 1019?

• 1610 — невозможно.
• 1010 — возможно. Пример: 1 1 9 1 → (2,10,10) → удаляем 2 → «10» и «10» → 1010.
• 1019 — невозможно.

Минимальное и максимальное возможные значения результата

Минимум: 1 (например, 1000 → суммы (1,0,0); удаляем 0 → остаётся 0 и 1 → «01» = 1).
Максимум: 1818 (например, 1999, 2999, …, 9999 → суммы (a+9, 18, 18); удаляем минимум a+9, остаётся 18 и 18 → «1818»).

Если результат равен 1418

Наименьшее входное число: 1599 (суммы 6,14,18 → удаляем 6 → 14 и 18 → 1418).
Наибольшее входное число: 9959 (суммы 18,14,14 → удаляем 14 → 14 и 18 → 1418).

10) Короткое сообщение об одном из основателей теории алгоритмов

Вариант: Алан Тьюринг (1912–1954). Английский математик, предложил абстрактную модель «машины Тьюринга», на которой можно формально определить вычислимость. Во время Второй мировой войны участвовал в расшифровке «Энигмы». Идеи Тьюринга заложили основу теории алгоритмов и современного программирования.

11) Шаг алгоритма и команда алгоритма — в чём разница?

Решение. Команда — тип действия (шаблон: «прибавь 1», «если … то …»). Шаг — конкретное применение команды в определённый момент выполнения. Один и тот же тип команды может выполняться много раз (много шагов).

12) Что такое сложность алгоритма? От чего она зависит?

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

13) «Столбиком»: оценить сложность перемножения двух натуральных чисел с n и m десятичными цифрами

Решение. Школьный алгоритм выполняет n·m умножений «цифра на цифру» и порядка n·m операций сложения с переносами. Ассимптотика по времени: O(n·m). Память — O(n+m) для хранения промежуточных сумм.

14) Когда алгоритм считается эффективным?

Решение. Когда при тех же входах он потребляет меньше времени/памяти при сохранении корректности. Обычно сравнивают по асимптотике: например, O(n log n) эффективнее, чем O(n²) на больших n. Важны также простота реализации и устойчивость к ошибкам/краевым случаям.

15) Эффективный алгоритм возведения x в степень n = 152

Решение (быстрое возведение в степень, «квадратирование»).

Псевдокод:

Дополнение (к п.4–5): система команд исполнителя «Колдун» и план варки эликсира

Возможные команды: Зажечь огонь, Погасить огонь, Налить ингредиент X, Перевернуть часы-3, Перевернуть часы-8, Дождаться опустошения часов-k, Начать варку, Завершить варку.

План на 7 минут: «Зажечь огонь; перевернуть часы-3 и часы-8; когда часы-3 опустеют — перевернуть их и начать варку; когда часы-3 опустеют — снова перевернуть; когда часы-8 опустеют — перевернуть часы-3; когда часы-3 опустеют — завершить варку». Это ровно 7 минут (см. п.4).