Автор | Сообщение |
|
Отправлено: 06.03.22 04:20. Заголовок: ege23 №151
Всех с наступающим праздником весны! Вот задачка, на первый взгляд простая, а ответ не сходится: 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
[только новые]
|
|
|
Отправлено: 06.03.22 12:58. Заголовок: В формуле для четног..
В формуле для четного у вас ошибка. В четное нельзя прийти третьей командой
|
|
|
|
Отправлено: 07.03.22 02:07. Заголовок: EugeneJobs пишет: В..
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) Спасибо
|
|
|
|
| Администратор
|
Сообщение: 3361
|
|
Отправлено: 07.03.22 11:25. Заголовок: T = *(25+1) T = 1 f..
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] )
|
|
|
|
Отправлено: 08.03.22 01:06. Заголовок: Спасибо, Константин ..
Спасибо, Константин Юрьевич! Когда смотришь на готовый код программы, вроде все понятно, что и для чего Поляков пишет: цитата: | ... if i in [9, 17]: for j in range(i): T[j] = 0 |
| Вот этого кирпичика и не хватало, "на автопилоте" обнулял все, что выше 17, как в Excel-e Поэтому, самому выстроить эти кирпичики в крепкую стену - увы, не получалось, может потому, что руки сразу тянутся к Excel фото img Может быть кому-то и эта картинка тоже поможет Еще раз, огромное спасибо
|
|
|
|