Как правильно решить информатику У исполнителя Калькулятор - три команды, которым присвоены номера:
1. прибавь 1
2. сделай чётное
3. сделай нечётное
4. умножь на 10
Первая из них увеличивает на 1 число на экране, вторая умножает это число на 2, третья переводит число x в число 2x + 1, четвертая умножает на 10. Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21. Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 15?Иммерсивное средство чтения
Как правильно решить информатику У исполнителя Калькулятор - три команды, которым присвоены номера:
1. прибавь 1
2. сделай чётное
3. сделай нечётное
4. умножь на 10
Первая из них увеличивает на 1 число на экране, вторая умножает это число на 2, третья переводит число x в число 2x + 1, четвертая умножает на 10. Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21. Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 15?Иммерсивное средство чтения
1. прибавь 1
2. сделай чётное
3. сделай нечётное
4. умножь на 10
Первая из них увеличивает на 1 число на экране, вторая умножает это число на 2, третья переводит число x в число 2x + 1, четвертая умножает на 10. Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21. Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 15?Иммерсивное средство чтения
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Для решения этой задачи можно воспользоваться методом динамического программирования.
Обозначим через dp[i] количество способов получить число i.
Инициализируем dp[1] = 1, так как из числа 1 можно получить только число 2 (выполнив команду "прибавь 1").
Далее перебираем все возможные числа j от 2 до 15 и для каждого числа j пересчитываем dp[j] следующим образом:
dp[j] = dp[j - 1] (увеличиваем на 1)если j четное, то dp[j] += dp[j / 2] (делаем четное)если j нечетное, то dp[j] += dp[(j - 1) / 2] (делаем нечетное)dp[j] += dp[j / 10] (умножаем на 10)В итоге, после выполнения всех операций, dp[15] будет содержать количество всевозможных программ, которые преобразуют число 1 в число 15.