Форум » Динамическое программирование » тема 23, задача № 3097 » Ответить
тема 23, задача № 3097
aln1947: (№ 3097) У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 1 2. умножь на 1,5 Первая из них увеличивает на 1 число на экране, вторая увеличивает это число в 1,5 раза, если число чётное. К нечётным числам вторая команда неприменима. Сколько есть программ, которые число 2 преобразуют в число 22? Как подступиться к этой задаче? Если команда 2 = умножь на 1,5, то какая будет рекуррентная формула: К_n = K_n/1.5 - как это применить к ЧЕТНОМУ числу? Поясните, пожалуйста!
Ответов - 6
polyakovss: Рекурсивная программа, Python:[pre2] def nProg( x, t ): if x == t: return 1 if x > t: return 0 if x % 2 == 0: return nProg( x+1, t ) + nProg( (x//2)*3, t ) else: return nProg( x+1, t ) print(nProg(2,22)) [/pre2] Без рекурсии:[pre2] a=[0]*31 a[2]=1 for k in range(22): a[k+1] += a[k] if k % 2 == 0: a[(k//2)*3] += a[k] print(a[22]) [/pre2]
aln1947: Спасибо большое, Сергей Сергеевич! А старым способом, через таблицу можно? А.Л.Наймушин.
polyakovss: Да, Александр Львович, можно. И решается обычным способом совсем просто.
aln1947: Спасибо, Сергей Сергеевич! А нельзя для примера изобразить несколько первых столбцов в таблице решения. Когда + K_N/2 это понятно, а как будет выглядеть + K_N/1,5? Что-то нге соображу. С уважением, А.Л.
polyakovss: K(22) = 1 K(21) = K(21+1) = K(22) = 1 K(20) = K(20+1) + K((20/2)*3) = K(21) + K(30) = 1 + 0 = 1 Аналогично получаем: K(19) = 1 K(18) = 1 K(17) = 1 K(16) = 1 K(15) = 1 Далее: K(14) = K(14+1) + K((14/2)*3) = K(15) + K(21) = 1 + 1 = 2 K(13) = K(13+1) = K(14) = 2 K(12) = K(12+1) + K((12/2)*3) = K(13) + K(18) = 2 + 1 = 3 Далее аналогично: K(11) = 3 K(10) = 4 K(9) = 4 K(8) = 7 K(7) = 7 K(6) = 11 K(5) = 11 K(4) = 22 K(3) = 22 K(2) = K(2+1) + K((2/2)*3) = K(3) + K(3) = 22 + 22 = 44 Ответ: 44.
aln1947: Огромное спасибо, Сергей Сергеевич! Я про этот Ваш способ, честно сказать, забыл. С уважением, А.Л.
полная версия страницы