Форум » Динамическое программирование » Задача 22. » Ответить
Задача 22.
Wally: Здравствуйте, прошу помочь мне с данной задачей. У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 3, 2. умножь на 3. Сколько есть программ, которые число 3 преобразуют в число 93? Ответ обоснуйте.
Ответов - 22, стр:
1 2 All
PSV: ВСЕ! Нашла у себя ошибку Спасибо!!!
Гость: Объясните пожалуйста, как решать задание 94) (А.Е. Гребенкин, Екатеринбург) Исполнитель U18 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера: 1. Вычесть 1 2. Вычесть 3 3. Взять остаток от деления на 4 Команда 3 выполняется только для чисел, больших, чем 4. Программа для исполнителя U18 – это последовательность команд. Сколько существует таких программ, которые исходное число 22 преобразуют в число 2? Спасибо.
MEA: Рекомендую составить таблицу: в верхней строке числа от 22 до 2, в нижней количество способов получить соответствующее число. В этой же теме выше два способа описания задач такого типа.
Гость: Мне не понятен 3 пункт "3. Взять остаток от деления на 4", что именно он делает.
Гость: Не понятна команда, берет остаток отделения, и что с ним делает?
polyakovss: Здравствуйте! Очень простой метод решения любых актуальных на данный момент задач задания 22 с пошаговым интерактивным объяснением здесь. При переходе на страницу разрешите использование Flash (Нажмите, чтобы включить плагин "Adobe Flash Player". Разрешить). Решение этим методом задачи 94: Переформулируем условие задачи так, чтобы вместо команды "Вычесть 1" была бы команда "Прибавить 1", вместо команды "Вычесть 3" была бы команда "Прибавить 3". В этом случае вопрос будет сформулирован следующим образом: "Сколько существует таких программ, которые исходное число 2 преобразуют в число 22?" А вот какой должна быть Команда_3 в переформулированном условии? Вы пишете: Не понятна команда, берет остаток от деления, и что с ним делает? В условии сказано: "Исполнитель U18 преобразует число, записанное на экране." Если на экране число 22, то Команда_3 заменяет его на число, равное остатку от деления 22 на 4, то есть на число 2. Переформулированная Команда_3: заменить число на экране на числа, которые дают остаток от деления на 4, равный исходному числу, то есть для чисел, равных остатку, нужно учесть количество команд от чисел, которые при делении на 4 дают такой остаток. Так для числа 2 только для Kоманды_3: K(2) = K(22) + K(18) + K(14) + K(10) + K(6). (22 mod 4 = 2, 18 mod 4 = 2, 14 mod 4 = 2, 10 mod 4 = 2, 6 mod 4 = 2) Для всех команд для числа 2: K(2) = K(3) + K(5) + K(22) + K(18) + K(14) + K(10) + K(6). Для числа 3 только для Команды_3: K(3) = K(19) + K(15) + K(11) + K(7). (19 mod 4 = 3, 15 mod 4 = 3, 11 mod 4 = 3, 7 mod 4 = 3) Для всех команд для числа 3: K(3) = K(4) + K(6) + K(19) + K(15) + K(11) + K(7). Поскольку Команда_3 выполняется только для чисел, больших, чем 4, а остатки от деления чисел от 22 до 5 не превышают 3, то учесть Команду_3 нужно будет только для чисел 3 и 2 (чисел 1 и 0 в задаче нет). Поэтому К(22) = 1 К(21) = К(21+1) +K(21+3) = K(22) + K(24) = 1 + 0 = 1 (чисел, больших 22, в задаче нет) К(20) = K(20+1) + K(20+3) = 1 K(19) = K(19+1) + K(19+3) = K(20) + K(22) = 1 + 1 = 2 K(18) = 3 K(17) = 4 K(16) = 6 K(15) = 9 K(14) = 13 K(13) = 19 K(12) = 28 K(11) = 41 K(10) = 60 K(9) = 88 K(8) = 129 K(7) = 189 K(6) = 277 K(5) = 406 K(4) = 595 K(3) = K(4) + K(6) + K(19) + K(15) + K(11) + K(7) = 1113 K(2) = K(3) + K(5) + K(22) + K(18) + K(14) + K(10) + K(6) = 1873 Ответ: 1873. Подробное решение задачи 93 предложенным методом можно посмотреть здесь (polyakovss Сообщение: 39).
Гость: Спасибо большое. Все понятно.
полная версия страницы