Форум » Динамическое программирование » ege23 №151 » Ответить
ege23 №151
s11kai: Всех с наступающим праздником весны! Вот задачка, на первый взгляд простая, а ответ не сходится: ege 23 № 151 (Е. Джобс) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавь 1 2. Умножь на 2 3. Сделай нечётное Первая команда увеличивает число на 1, вторая – вдвое, третья прибавляет к четному числу 1, к нечетному – 2. Сколько существует таких программ, которые исходное число 3 преобразуют в число 25 и при этом траектория вычислений программы содержит число 9 и число 17? Подскажите, пожалуйста, чего я теряю в своих умозаключениях пытаясь написать рекуррентную функцию: если n/2 => f(n) = f(n-1)+f(n-1)+f(n/2) иначе => f(n) = f(n-1)+f(n-2) Спасибо!
Ответов - 4
EugeneJobs: В формуле для четного у вас ошибка. В четное нельзя прийти третьей командой
s11kai: EugeneJobs пишет: В формуле для четного у вас ошибка. В четное нельзя прийти третьей командой В таком случае и в формуле для нечетных тоже есть ошибка, поскольку нечетное можно получить 3-мя командами, стало быть правильной будет такая функция: если n/2 => f(n) = f(n-1)+f(n/2) иначе => f(n) = f(n-1)+f(n-2)+f(n-1) возможно, что и так тоже будет правильно: если n/2 => f(n) = f(n-1)+f(n/2) иначе => f(n) = 2*f(n-1)+f(n-2) Спасибо
Поляков: [pre2] T = [0]*(25+1) T[3] = 1 for i in range(4,25+1): k = T[i-1] if i % 2 == 0: k += T[i//2] else: k += T[i-1] + T[i-2] T[ i] = k if i in [9, 17]: for j in range(i): T[j] = 0 print( T[25] )[/pre2]
s11kai: Спасибо, Константин Юрьевич! Когда смотришь на готовый код программы, вроде все понятно, что и для чего Поляков пишет: ... if i in [9, 17]: for j in range(i): T[j] = 0 Вот этого кирпичика и не хватало, "на автопилоте" обнулял все, что выше 17, как в Excel-e Поэтому, самому выстроить эти кирпичики в крепкую стену - увы, не получалось, может потому, что руки сразу тянутся к Excel фото img Может быть кому-то и эта картинка тоже поможет Еще раз, огромное спасибо
полная версия страницы