10 класс Информатика ГДЗ учебник Поляков 2 часть Параграф 52 Оптимальные линейные программы
Стр.135.
1. Да, задача для Удвоителя может быть решена несколькими программами одинаковой длины. Например, для получения числа 10 из 1 могут использоваться следующие программы: «прибавь 1» пять раз и «умножь на 2» один раз, или «умножь на 2» два раза и «прибавь 1» три раза.
2. Для доказательства, что программа самая короткая, нужно перебрать все возможные комбинации команд и убедиться, что ни одна из них не дает результата быстрее. Построение дерева вариантов поможет визуализировать все возможные пути и выбрать оптимальный.
3. С помощью Удвоителя можно получить все натуральные числа, так как команды «прибавь 1» и «умножь на 2» покрывают все возможные результаты. Из нуля можно получить только степени двойки и числа, полученные сложением степеней двойки. Из отрицательного числа Удвоитель не может работать, так как команды «прибавь 1» и «умножь на 2» предполагают работу с неотрицательными числами.
4. Для построения самой короткой программы нужно двигаться от конечного числа N к начальному, выполняя обратные действия: деление на 2 и вычитание 1. Задача не имеет решений, если N не является степенью двойки или их суммой, так как 0 можно умножать на 2, но нельзя прибавить 1.
5. Лучше перебирать варианты программ от конечного числа к начальному, так как деление на 2 ограничено только чётными числами. Это упрощает поиск оптимального пути, так как мы можем сразу исключить неподходящие варианты и сократить количество шагов.
| 50 | 51 | 52 | 53 | 54 |