7 класс Информатика ГДЗ учебник Поляков 2 часть Параграф 32

7 класс Информатика ГДЗ учебник Поляков 2 часть Параграф 32 Оптимальные программы

Стр.58.

Ответы на вопросы

1. Да, задача для Удвоителя может решаться с помощью нескольких различных алгоритмов. Например, для преобразования числа 6 в 28 можно использовать алгоритм 122 (прибавь 1, умножь на 2, умножь на 2) или 212 (умножь на 2, прибавь 1, умножь на 2).

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

3. С помощью Удвоителя можно получить любое натуральное число, кроме тех, которые не могут быть выражены в виде суммы степеней двойки. Из нуля можно получить только числа, которые являются степенями двойки. Из отрицательных чисел Удвоитель не работает, так как операции «прибавь 1» и «умножь на 2» определены только для неотрицательных чисел.

4. Чтобы быстро построить самую короткую программу для получения некоторого числа N из нуля с помощью Удвоителя, нужно использовать метод дерева возможных вариантов, начиная с числа N и двигаясь в обратном направлении к нулю. Задача не имеет решений, если N не является степенью двойки или суммой степеней двойки.

5. Для исполнителя Калькулятор лучше перебирать варианты программ от конечного числа к начальному, так как операция «раздели на 2» является необратимой и позволяет быстро уменьшить число, приближаясь к начальному значению. Например, для преобразования числа 10 в 1 программа будет: 102 (раздели на 2, прибавь 1).

6. Выполните задания по указанию учителя в рабочей тетради.