Форум » Динамическое программирование » Задача 22. » Ответить

Задача 22.

Wally: Здравствуйте, прошу помочь мне с данной задачей. У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 3, 2. умножь на 3. Сколько есть программ, которые число 3 преобразуют в число 93? Ответ обоснуйте.

Ответов - 22 новых, стр: 1 2 All

polyakovss: Здравствуйте, Wally! Очень простой метод решения всех задач задания 22 с пошаговым интерактивным объяснением здесь. При переходе на страницу разрешите использование Flash (Нажмите, чтобы включить плагин "Adobe Flash Player". Разрешить). Посмотрев только материал вкладки "Суть метода: задача 1", Вы легко решите свою задачу самостоятельно. Если что-нибудь не получится, спрашивайте.

Wally: Получается, что по Вашему методу мне нужно от 93 до 3 "пройти"? Но на ЕГЭ у меня времени столько не будет. Все почему-то разбирают задачи, в которых "маленькая" траектория: от 1 до 22, от 5 до 20 и так далее. Как же мне решить задачу с большой траекторией: от 3 до 93, например?

MEA: По сути это задание ничем не отличается от "сколько дорог из пункта А в пункт К"... тот же граф те же стрелки, (и от 23 после построения стрелок, если решать методом отображений), и рекурсия. Рисовать не обязательно. Достаточно таблицу в две строки - верхний ряд числа, в которые можем попасть, нижний ряд - сколько способов. В первом ставим 1 и далее просто вписываем числа. "Писанины" будет меньше. При заполнении чисел в которые можно попасть следует заметить, что в этом задании можно прийти только в кратные 3. т.е. нужны числа от 3, 6, 9, ..., 93. Можем изменить задание из 1 попадать в 31, только действия *3 и +1 Далее следует для сокращения количества записей заметить, что важны только те из которых можно "выйти" двумя способами, т.е. при умножении на 3 не выйдем за пределы 31 (все числа от 1 до 10), а после 10 важны те, в которые можно попасть двумя способами, т.е. кратные 3 - это числа 12, 15, 18, ... 30 и последнее 31 для порядка.


Wally: Вы не могли бы привести пример решения для задания, которое я написал? Не очень понятно, что Вы написали... Спасибо.

MEA: https://yadi.sk/i/wzUT8C6207PTXw Два варианта заполнения. Выше с переходом к командам +1 и *3 Ниже без перехода как в задании Под каждой таблицей указала какие команды могут привести в это число. В первой клетке ставим 1 - это означает, что это число "достижимо" с помощью пустой программы. В остальные клетки (узлы) попадаем иногда только с командой +1 иногда двумя способами +1 и *3 - в клетку пишем сумму чисел откуда попали. На практике эти строки можно не писать. Точно такое же оформление можно использовать для задания с рекурсией. Считаю, что по смыслу четыре задания ЕГЭ: логика (23), количество дорог, рекурсия и это задание очень близки друг другу, только предварительный анализ отличается.

Wally: А почему получается из 1->31 двадцать восемь команд и из 3->93 такое же количество?

MEA: Wally пишет: А почему получается из 1->31 двадцать восемь команд и из 3->93 такое же количество? А почему должно быть другое? Иначе я бы не советовала замену. Команды то совпадают, можете рассматривать +1 как добавить одну тройку.

Wally: А почему Вы заполняете вторую таблицу цифрами 3, 6, 9, 12 и так далее, а первую сначала от 1 до 10, затем 12, 15 и т.д.? С Восьмым марта Вас!

MEA: Спасибо :). Потому, что во второй таблице прибавляя 3 к числу кратному трем или умножая, никогда не попасть на число не кратное 3, тогда зачем их писать, если в них прийти нельзя, а значит и выйти из них тоже. И в первой и во второй таблице записаны только те числа, которые повлияют на ответ - из которых можно сделав команду еще остаться в диапазоне, и те в которые можно прийти из двумя способами (т.е. кратные трем в первой таблице)

Wally: Поможите мне с 23 заданием? Я его решил, но ответ на единицу меньше...

MEA: Да, можно на почту писать mironch-elena@yandex.ru. можно в соответствующем разделе тему создать.

Wally: Спасибо, я чуть позже напишу.

PSV: Не могу решить! Исполнитель R17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавить 1 2. Прибавить 3 3. Умножить на 2 Программа для исполнителя R17 – это последовательность команд. Сколько существует таких программ, которые исходное число 3 преобразуют в число 20 и при этом траектория вычислений программы содержит число 9 и число 12? Ответ: 234 (мой ответ:198)

polyakovss: Здравствуйте! Очень простой метод решения любых актуальных на данный момент задач задания 22 с пошаговым интерактивным объяснением здесь. При переходе на страницу разрешите использование Flash (Нажмите, чтобы включить плагин "Adobe Flash Player". Разрешить). Этим методом рассматриваемая задача решается так: N(20) = 1 N(19) = N(19+1) + N(19+3) + N(19*2) = N(20) + N(22) + N(38) = 1 + 0 + 0 = 1 (чисел, больших 20, в задаче нет) N(18) = N(18+1) + N(18+3) + N(18*2) = N(19) = 1 N(17) = N(18) + N(20) = 2 N(16) = N(17) + N(19) = 3 N(15) = N(16) + N(18) = 4 N(14) = N(15) + N(17) = 6 N(13) = N(14) + N(16) = 9 N(12) = N(13) + N(15) = 13 N(11) = N(12) + N(14) + N(22) = N(12) + 0 + 0 = 13 (теперь чисел, больших 12, в задаче нет) N(10) = N(11) = 13 N(9) = N(10) + N(12) = 26 N(8) = N(9) = 26 (теперь чисел, больших 9, в задаче нет) N(7) = N(8) = 26 N(6) = N(7) + N(9) = 52 N(5) = N(6) + N(8) = 78 N(4) = N(5) + N(7) + N(8) = 130 N(3) = N(4) + N(6) + N(6) = 130 + 52 + 52 = 234 Ответ: 234. В предложенном по ссылке материале всё очень подробно объясняется.

PSV: Спасибо! В методе разобралась. Но, никак не могу найти ошибку у себя в прямом пути решения.



полная версия страницы