Форум » Динамическое программирование » статград 4.03.2020 номер 22 » Ответить
статград 4.03.2020 номер 22
recdoc: Подскажите, пожалуйста, как составить алгоритм? Исполнитель РазДва преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя РазДва – это последовательность команд. Укажите наименьшее натуральное число, которое нельзя получить из исходного числа 1, выполнив программу исполнителя РазДва, содержащую не более пяти команд.
Ответов - 3
Поляков: Можно дерево построить. А можно в таблице отмечать новые достижимые значения после каждого хода. Например, наименьшее число, недостижимое за 4 хода - 11. На рисунке показаны достижимые позиции после каждого из четырёх ходов. А для 5 ходов аналогично получается 15. Следующим ходом достижимы 11 (из 10), 13 (из 12), 14 (из 7), ...
iZOL: Добрый день. Столкнулся с такой задачей. У меня 4 действия. Мне не совсем понятно - что имеется в виду под наименьшим недостижимым числом? Я выписал 16 возможных программ. Они дают числа 5, 6, 7, 8, 9, 10, 12, 16. Возьмем число 2. Оно натуральное и его нельзя получить в 4 действия, ровно как и числа 3 и 4. Или тут имеется в виду, что в процессе выполнения программы это число тоже не должно получаться ,как промежуточный результат между действиями? Подскажите пожалуйста.
Поляков: iZOL пишет: Или тут имеется в виду, что в процессе выполнения программы это число тоже не должно получаться ,как промежуточный результат между действиями? Да. См. объяснение выше.
полная версия страницы